Home     About     Download     Resources     Contact us

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Browse thread
Sudoku solver
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2005-11-15 (12:56) From: Pascal Brisset Subject: Re: [Caml-list] Sudoku solver
The "optimal algorithm" is not enough; some grids require more (for example a
"shaving" technique as described by Helmut).

Using FaCiLe (http://www.recherche.enac.fr/opti/facile/), a naive solution
could look like:

--8<-----------------------
open Facile
open Easy

(** THE All Different constraint **)
let cards = Array.init 9 (fun i -> Fd.int 1, (i+1))
let ad = fun a -> Cstr.post (Gcc.cstr ~level:Gcc.High a cards)

let solve grille =
(** The matrix of variables **)
let v = Array.init 9 (fun _ -> Fd.array 9 1 9) in

(** Preset values **)
Array.iteri
(fun i vi ->
Array.iteri
(fun j vij ->
let c = grille i j in
if c <> '.' then
Fd.unify vij (Char.code c - Char.code '0'))
vi)
v;

(** Lines **)
Array.iter ad v;

(** Columns **)
for i = 0 to 8 do
ad (Array.init 9 (fun j -> v.(j).(i)))
done;

(** Regions **)
for i = 0 to 2 do
for j = 0 to 2 do
ad (Array.init 9 (fun k -> v.(3*i+k/3).(3*j+k mod 3)))
done
done;

(** Print **)
Array.iter (fun vi -> Fd.fprint_array stdout vi; print_newline ()) v;
print_newline ()

(** Solving all the grids from a file (one per line) **)
let _ =
let f = open_in Sys.argv.(1) in
try
while true do
let l = input_line f in
solve (fun i j -> l.[9*i+j])
done
with
End_of_file -> ()
--8<-----------------------

where search is not included. So it does not solve all the instances:

% cat grids.txt
............87.26..1.6.2..8...1..8.446.....973.1..4...8..2.7.4..49.16............
.18...7.....3..2...7...........71...6......4.3........4..5....3.2..8...........6.
% ./sudoku grids.txt
[|6; 8; 2; 9; 4; 5; 7; 1; 3|]
[|5; 3; 4; 8; 7; 1; 2; 6; 9|]
[|9; 1; 7; 6; 3; 2; 4; 5; 8|]
[|2; 7; 5; 1; 6; 9; 8; 3; 4|]
[|4; 6; 8; 5; 2; 3; 1; 9; 7|]
[|3; 9; 1; 7; 8; 4; 6; 2; 5|]
[|8; 5; 6; 2; 9; 7; 3; 4; 1|]
[|7; 4; 9; 3; 1; 6; 5; 8; 2|]
[|1; 2; 3; 4; 5; 8; 9; 7; 6|]

[|_81[2;5;9]; 1; 8; _84[2;4;6;9]; _85[2;4-6;9]; _86[2;4-6;9]; 7; 3; _89[4-6;9]|]
[|_90[5;9]; 6; 4; 3; _94[1;5;9]; 7; 2; 8; _98[1;5;9]|]
[|_99[2;5;9]; 7; 3; _102[1-2;4;6;8-9]; _103[1-2;4-6;9]; _104[2;4-6;8-9];
_105[1;4-6;9]; _106[1;5;9]; _107[1;4-6;9]|]
[|8; _109[4-5;9]; 2; _111[4;6;9]; 7; 1; 3; _115[5;9]; _116[5-6;9]|]
[|6; _118[5;9]; _119[1;7]; _120[2;8-9]; 3; _122[2;5;8-9]; _123[1;5;9]; 4;
_125[7-8]|]
[|3; _127[4-5;9]; _128[1;7]; _129[4;6;8-9]; _130[4-6;9]; _131[4-6;8-9];
_132[1;5-6;9]; 2; _134[7-8]|]
[|4; 8; _137[6;9]; 5; _139[1-2;6;9]; _140[2;6;9]; _141[1;9]; 7; 3|]
[|_144[1;7]; 2; _146[6;9]; _147[1;4;6-7;9]; 8; 3; _150[1;4-5;9]; _151[1;5;9];
_152[1;4-5;9]|]
[|_153[1;7]; 3; 5; _156[1;4;7;9]; _157[1;4;9]; _158[4;9]; 8; 6; 2|]

For the second instance, the remaining possible values for each number are
displayed. Inferences taking into account several constraints (line, column or
region) in the same time are required to do more.

--Pascal

Diego Olivier Fernandez Pons wrote:
> There is a nice paper by Helmut Simonis "Sudoku as a constraint problem"
> with reference to the relevant paper for the algorithms.
>
>     http://www.icparc.ic.ac.uk/~hs/
>
> You could also try to write a solver with FaCiLe (which actually contains
> the optimal algorithm for "alldiff" constraints)
>
>
>         Diego Olivier