Re: [Caml-list] Sudoku solver

[Pascal Brisset <pascal.brisset@enac.fr>]

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