| debruyck@gmail.com 2007-05-27, 7:06 pm |
| Ok, it's been ages since I've programmed Prolog, but here are some
hints on how to set something like this up:
* When programming prolog,
- the first rule is: be correct, then try to be smart. The simplest
algorithm is backtracking based on try and error
- the second rule is to store information as much as possible in
predicates and not lists.
* You should try to create a data structure that allows you to have
the Prolog engine bind variables in it. I don't know exactly anymore
how you can achieve it, but the basis to start from is to create
something like
rows(
row(_,_,_,_,_,_,_,_,_),
row(_,_,_,_,_,_,_,_,_),
....
row(_,_,_,_,_,_,_,_,_),
)
(where each of the _ is a DIFFERENT unbound variable) (maybe you can
ask the input sudoku this way i.e. with the given numbers already
bound?)
This is the row-view on the sudoku. You can create multiple views
(e.g. the column and box views) on the same sudoku, by using the same
unbound variable in other data structures like this.
* add the given numbers as absolute truths, these bind some of the
variables without an alternative being available to backtrack on.
* create the rules to:
1. bind unbound variables (simplest rule is to try 1, then 2, then
3 ... up to 9) ,
2. check if the resulting sudoku is correct (i.e. the 9 horizontal, 9
vertical and 9 box constraints
* ask Prolog for the solution. (Since this is a very simple approach,
it may/will take a while so test it on a nearly complete sudoku).
Optimisations:
* make the rules "1. bind unbound variables" smarter:
- don't choose a digit that already appears in the row, column or box
- ... (add any strategies that are CORRECT here). (remember: better
correct and slower than fast and wrong)
* create multiple views on your sudoku e.g. the column view and box
view. This is achieved by taking the unbound variables and put them
in other data structures (next to the ones they are already in). Once
the prolog engine binds one of these unbound variables it'll be bound
in all 'views' you created.
- writing some rules will become a lot easier if you have multiple
views on your sudoku. E.g. column rules are easier to express on the
column view than on the row view.
- multiple views will also allow you to more easily program more
complex strategies in "1. bind unbound variables".
Just my 2 cents,
|