The New Sudoku Players' Forum

[Guest]

An elegant way to solve these kind of problems is to use logic programming
and constraints over finite domains. There are various languages which
support these techniques, for example 'gprolog' ,see http://pauillac.inria.fr/~diaz/gnu-prolog/

Using gprolog, a Sudoku solver is as simple as the following
(ellipsis used to save space)

/* Array of variables */

Array = [ A_1_1 ... A_9_9 ],

/* All variables are in the range 1...9 */

fd_domain(Array,1,9),

/* Rows are all different */

fd_all_different([ A_1_1, ... A_9_1]),
fd_all_different([ A_1_2, ... A_9_2]),
fd_all_different([ A_1_3, ... A_9_3]),
fd_all_different([ A_1_4, ... A_9_4]),
fd_all_different([ A_1_5, .... A_9_5]),
fd_all_different([ A_1_6, ... A_9_6]),
fd_all_different([ A_1_7, .... A_9_7]),
fd_all_different([ A_1_8, .... A_9_8]),
fd_all_different([ A_1_9, .... A_9_9]),

/* Columns are all different */

fd_all_different([ A_1_1, ... A_1_9]),
fd_all_different([ A_2_1, ... A_2_9]),
fd_all_different([ A_3_1, ... A_3_9]),
fd_all_different([ A_4_1, ... A_4_9]),
fd_all_different([ A_5_1, ... A_5_9]),
fd_all_different([ A_6_1, .... A_6_9]),
fd_all_different([ A_7_1, .... A_7_9]),
fd_all_different([ A_8_1, .... A_8_9]),
fd_all_different([ A_9_1, .... A_9_9]),

/* Boxes are all different */

fd_all_different([ A_1_1, ... A_3_3 ]),
fd_all_different([ A_1_4, ... A_3_6 ]),
fd_all_different([ A_1_7, ... , A_3_9 ]),
fd_all_different([ A_4_1, ... A_6_3 ]),
fd_all_different([ A_4_4, ... A_6_6 ]),
fd_all_different([ A_4_7, ... A_6_9 ]),
fd_all_different([ A_7_1, ... A_9_3 ]),
fd_all_different([ A_7_4, ... A_9_6 ]),
fd_all_different([ A_7_7, ... A_9_9 ]),

/* Assign the ones that we know */
/* Times apr 8 2005 Fiendish */

Array = [
_, _, _, _, 3, 8, _, _, _,
_, 9, 5, 6, _, _, _, 3, _,
_, _, _, _, 1, _, _, _, 6,

_, _, 2, 4, _, _, 1, _, 5,
_, _, _, _, _, _, _, _, _,
6, _, 4, _, _, 2, 9, _, _,

3, _, _, _, 9, _, _, _, _,
_, 8, _, _, _, 3, 7, 9, _,
_, _, _, 1, 2, _, _, _, _
],

/* Now search */

fd_labeling(Array),

/* and print answer /

format("~p\n",[[A_1_1, ...A_9_1]]),
format("~p\n",[[A_1_2, ...A_9_2]]),
format("~p\n",[[A_1_3, ...A_9_3]]),

format("~p\n",[[A_1_4, ...A_9_4]]),
format("~p\n",[[A_1_5, ... A_9_5]]),
format("~p\n",[[A_1_6, ... A_9_6]]),

format("~p\n",[[A_1_7, ... A_9_7]]),
format("~p\n",[[A_1_8, ... A_9_8]]),
format("~p\n",[[A_1_9, ... A_9_9]]).

[simes]

so what does "fd_labeling(Array), " do?

And can it print out a list of reasons as to why a particular number must be in a particular cell?

[Guest]

>> so what does "fd_labeling(Array), " do?

It's a built-in function in gprolog. It does a search for values of the variables
in Array, so after this call, the elements in Array should all have values.
While it searches, it takes the constraints into account, i.e. the domain
constraint ( each variable is in 1..9 ) and the all_different constraints which
say each row is a permutation, etc. The implementation is, I believe, much
the same as other people on this list have done, i.e. each variable keeps a
list of its possible values, which gets updated whenever any variable gets
a value. It's an exhaustive, backtrackable search, so its guaranteed to find
all solutions. It's also pretty fast.
See the gprolog webpage for details.

>> And can it print out a list of reasons as to why a particular number
>> must be in a particular cell?

No, I dont think so, although there may be some trace option
which shows how constrained variables get their values. It would be possible to do, but would require more programming in prolog.