Sudoku solver

Sudoku solver

[Jon Harrop]

Here is a little OCaml program to solve Sudoku puzzles:

  http://www.ffconsultancy.com/free/sudoku/

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Sudoku solver

[Alain Frisch]

Jon Harrop wrote:
> Here is a little OCaml program to solve Sudoku puzzles:
> 
>   http://www.ffconsultancy.com/free/sudoku/
> 

Funny. My father told me about the game last sunday and I was willing to
write a solver too :-)

Here it is:
http://www.eleves.ens.fr/home/frisch/info/af-sudoku-brute.ml
http://www.eleves.ens.fr/home/frisch/info/af-sudoku.ml

It is faster than yours. E.g., when displaying all the solutions (there
are 247 solutions for the example):

$ cat puzzle
001005300050490000
000102064
000000750
600000001
035000000
060903000
000020090
003600100

$ time ./sudoku < puzzle > /dev/null
4.89s user 0.00s system 98% cpu 4.944 total

$ time ./af-sudoku-brute < puzzle > /dev/null
0.02s user 0.00s system 30% cpu 0.068 total

$ time ./af-sudoku < puzzle > /dev/null
0.03s user 0.00s system 37% cpu 0.074 total

(all of them are compiled with ocamlopt without any special option)

I guess your choice of a functional data structure explains the 100x
slow-down... Hint: copying an array of 81 integers is fast.


The -brute version is a simple-minded brute force search. There other
one tries to use the constraint "each digit must appear in each bloc"
(where a bloc is a line, a column, or a 3x3 sub-bloc) to place digits.
It also chooses a cell with a minimal number of remaining choices when
branching. Interestingly, disabling these optimizations does not seem to
change the performance significantly.


-- Alain

Re: [Caml-list] Sudoku solver

[Diego Olivier Fernandez Pons]

    Bonjour,

> The -brute version is a simple-minded brute force search. There other
> one tries to use the constraint "each digit must appear in each bloc"
> (where a bloc is a line, a column, or a 3x3 sub-bloc) to place digits.
> It also chooses a cell with a minimal number of remaining choices when
> branching. Interestingly, disabling these optimizations does not seem to
> change the performance significantly.

The constraint "a single digit by block" is named "all different"  in
combinatorial optimization literature. The problem is that your
implementation is too naive : the "optimal" version (in the sense it can
ensure you always make a choice that has at least one solution for the
'alldiff' constraint) needs a matching algorithm and some graph theory.

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

Re: [Caml-list] Sudoku solver

[Pascal Brisset]

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

Re: [Caml-list] Sudoku solver

[Diego Olivier Fernandez Pons]

     Bonjour,

> The "optimal algorithm" is not enough; some grids require more (for
> example a "shaving" technique as described by Helmut).

What I understood in Helmut's paper is that most of the Sudoku instances
were backtrack-free when a combination of matching constraints was used
(same with card, cardinality matrix, etc.)

When shaving is allowed, forward checking or just bound consistency closes
almost all the instances without backtracking. That might be a better
advice for "ad hoc" solvers like Frisch's since he seems to be already
doing forward checking.

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

It shouldn't be difficult to add a simple search (generate) is it ?

        Diego Olivier

Re: [Caml-list] Sudoku solver

[Pascal Brisset]

Diego Olivier Fernandez Pons wrote:

>>where search is not included. So it does not solve all the instances:
> 
> 
> It shouldn't be difficult to add a simple search (generate) is it ?

  Yes, just add one line (before printing):
	
	Goals.solve (Goals.Array.forall Goals.Array.labeling v);

--Pascal

Re: [Caml-list] Sudoku solver

[Christophe Raffalli]

And what about a sudoko generator with a pertinent notion of level for a 
human ? Would be nice if you could choose the cases that are filled from 
start ...


a start for level for problems with a unique solution :

- negative level -n : number of times where you have to do deep 
reasonning (guesses) because you do not have an immediate choice.

- positive level n : minimum of the number of cases that can be filled
by an immediate choice on all branch ?

These are not formal definition ... yet, but using a representation of 
the problem as a set of close, I think we can do something with the 
complexity of the proof search ...

just for fun ...



-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Caml-list] Sudoku solver

[Diego Olivier Fernandez Pons]

    Bonjour,

> And what about a sudoko generator with a pertinent notion of level for a
> human ? Would be nice if you could choose the cases that are filled from
> start ...

Actually that is what Helmut Simonis was trying to do with his paper.
He considers :
- difficulty (= level of "complexity" of the filtering algorithm needed to
solve the problem without backtracking)
- minimality (= number of non-redundant information for each deduction)

> These are not formal definition ... yet, but using a representation of
> the problem as a set of close, I think we can do something with the
> complexity of the proof search ...

Constraint programming is has a higher-level representation but I guess
the same could be achieved in SAT.

        Diego Olivier

Re: [Caml-list] Sudoku solver

[David Thomas]

Mostly to teach myself Ocaml and Tk, I put together a
simple Sudoku game.  If anyone wants to play with it,
modify it, etc, feel free.  

http://people.ucsc.edu/~dlthomas/sudoku.ml

The puzzle generation at present is entirely
braindead, but if someone produces a nice solution,
I'd love to see it included.



--- Christophe Raffalli
<christophe.raffalli@univ-savoie.fr> wrote:

> 
> And what about a sudoko generator with a pertinent
notion of 
> level for a human ? Would be nice if you could
choose the cases
> that are filled from start ...
> 
> 
> a start for level for problems with a unique
solution :
> 
> - negative level -n : number of times where you have
to do deep 
> reasonning (guesses) because you do not have an
immediate 
> choice.
> 
> - positive level n : minimum of the number of cases
that can be 
> filled by an immediate choice on all branch ?
> 
> These are not formal definition ... yet, but using a
> representation of the problem as a set of close, I
think we can 
> do something with the complexity of the proof search
...
> 
> just for fun ...
> 
> 
> 
> -- 
> Christophe Raffalli
> Université de Savoie
> Batiment Le Chablais, bureau 21
> 73376 Le Bourget-du-Lac Cedex
> 
> tél: (33) 4 79 75 81 03
> fax: (33) 4 79 75 87 42
> mail: Christophe.Raffalli@univ-savoie.fr
> www: http://www.lama.univ-savoie.fr/~RAFFALLI
> ---------------------------------------------
> IMPORTANT: this mail is signed using PGP/MIME
> At least Enigmail/Mozilla, mutt or evolution
> can check this signature. The public key is
> stored on www.keyserver.net
> ---------------------------------------------
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 



		
__________________________________ 
Yahoo! FareChase: Search multiple travel sites in one click.
http://farechase.yahoo.com

Re: [Caml-list] Sudoku solver

[Karl Zilles]

Jon Harrop wrote:
 > Here is a little OCaml program to solve Sudoku puzzles:
 >
 >   http://www.ffconsultancy.com/free/sudoku/
 >

Heh.  My parents showed me a Sudoku puzzle when I last visited them.  I 
solved one just to get a feel for them, then wrote a simple 
constraint/brute force solver in OCaml for fun.  Looks like a lot of us 
have.

Re: [Caml-list] Sudoku solver

[Jon Harrop]

On Tuesday 15 November 2005 08:55, Alain Frisch wrote:
> Funny. My father told me about the game last sunday and I was willing to
> write a solver too :-)

On Tuesday 15 November 2005 20:56, Karl Zilles wrote:
> Heh.  My parents showed me a Sudoku puzzle when I last visited them.  I
> solved one just to get a feel for them, then wrote a simple
> constraint/brute force solver in OCaml for fun.  Looks like a lot of us
> have.

LOL. It seems that everyone on the caml-list just discovered and solved 
them. :-)

> Here it is:
> http://www.eleves.ens.fr/home/frisch/info/af-sudoku-brute.ml
> http://www.eleves.ens.fr/home/frisch/info/af-sudoku.ml

I'll add links from my page to everyone else's OCaml Sudoku solvers, if that's 
ok. :-)

> It is faster than yours.

:-p

> E.g., when displaying all the solutions (there are 247 solutions for the
> example): 

I found the 1905-solution "Sky blunder" to be a good example (warning: 6' 
penis):

  http://www.sudoku.org.uk/blunder.htm

> I guess your choice of a functional data structure explains the 100x
> slow-down... Hint: copying an array of 81 integers is fast.

I'd be surprised if the functional data structure was responsible for a 100x 
slowdown, 10x maybe. I was going to optimise it but, because it solves 
puzzles in <1sec anyway, I decided to concentrate on making it concise 
instead.

> The -brute version is a simple-minded brute force search. There other
> one tries to use the constraint "each digit must appear in each bloc"
> (where a bloc is a line, a column, or a 3x3 sub-bloc) to place digits.
> It also chooses a cell with a minimal number of remaining choices when
> branching.

My program uses bitfields to keep track of which digits are valid. That may 
make it asymptotically faster than a brute force approach. I haven't thought 
about it much though (obviously not as much as Pascal!).

> Interestingly, disabling these optimizations does not seem to 
> change the performance significantly.

On real Sudoku puzzles?

I found a brute force solver written in Lisp on the net. My implementation was 
much slower for valid Sudoku puzzles but just as fast for Sky's erroneous one 
and much faster at finding any solution from a blank board. Of course, I may 
well have been measuring nothing more than language start-up time...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Sudoku solver

[Alain Frisch]

Jon Harrop wrote:
> I'll add links from my page to everyone else's OCaml Sudoku solvers, if that's 
> ok. :-)

No problem for me.

> I found the 1905-solution "Sky blunder" to be a good example (warning: 6' 
> penis):
> 
>   http://www.sudoku.org.uk/blunder.htm

$ time ./sudoku < sky > /dev/null
14.40s user 0.01s system 98% cpu 14.630 total
$ time ./af-sudoku-brute < sky > /dev/null
0.05s user 0.00s system 74% cpu 0.068 total
$ time ./af-sudoku < sky > /dev/null
0.14s user 0.01s system 87% cpu 0.168 total

>>I guess your choice of a functional data structure explains the 100x
>>slow-down... Hint: copying an array of 81 integers is fast.
> 
> 
> I'd be surprised if the functional data structure was responsible for a 100x 
> slowdown, 10x maybe. I was going to optimise it but, because it solves 
> puzzles in <1sec anyway, I decided to concentrate on making it concise 
> instead.

Using this compare function:

let compare (x1,y1) (x2,y2) = if x1 = x2 then y1 - y2 else x1 - x2

already doubles the speed of your program. In general, the built-in
polymorphic comparisons are a bad idea as soon as effiency matters.

>>Interestingly, disabling these optimizations does not seem to 
>> change the performance significantly.
> On real Sudoku puzzles?

Hard to tell, I'd need to find a slower machine ;-)  For today's puzzle
from http://www.sudoku.org.uk/daily.asp:

$ time ./sudoku < daily > /dev/null
0.25s user 0.00s system 86% cpu 0.291 total
$ time ./af-sudoku < daily > /dev/null
0.00s user 0.00s system 76% cpu 0.001 total
$ time ./af-sudoku-brute < daily > /dev/null
0.00s user 0.00s system 81% cpu 0.001 total


> I found a brute force solver written in Lisp on the net. My implementation was 
> much slower for valid Sudoku puzzles but just as fast for Sky's erroneous one 
> and much faster at finding any solution from a blank board. Of course, I may 
> well have been measuring nothing more than language start-up time...

Again, my solvers give the first solution in 0.00s from a blank board ;-)

I'm not yet convinced that for solving 9x9 grids, complex resolution
techniques from constraint solving bring much. They do probably for
larger grids and maybe for problem generation...

-- Alain

Re: [Caml-list] Sudoku solver

[Oliver Bandel]

On Tue, Nov 15, 2005 at 12:56:17PM -0800, Karl Zilles wrote:
> Jon Harrop wrote:                    
> > Here is a little OCaml program to solve Sudoku puzzles:                                                          
> >                                          
> >   http://www.ffconsultancy.com/free/sudoku/
> >
>                            
> Heh.  My parents showed me a Sudoku puzzle when I last visited them.  I
> solved one just to get a feel for them, then wrote a simple
> constraint/brute force solver in OCaml for fun.  Looks like a lot of us
> have.                                  


Well, yesterday was the first time I had contact to Sudoku at all.
I looked for pTeX, the japanese descendant of TeX and found this page:

  http://www.users.waitrose.com/~nihilist/sudoku.html

After I read that I thought, maybe to rewrite it in OCaml.

But it seems this work was already done.


Ciao,
   Oliver

Re: [Caml-list] Sudoku solver

[Alain Frisch]

Oliver Bandel wrote:
> Well, yesterday was the first time I had contact to Sudoku at all.
> I looked for pTeX, the japanese descendant of TeX and found this page:
> 
>   http://www.users.waitrose.com/~nihilist/sudoku.html

Cool, the page shows a "difficult" puzzle. My non-brute force version
finds a solution in 0.00s ;-) and my brute force version takes 45s.

Next task: compute the number of solutions for this puzzle.

Ok, I think we're off-topic...

-- Alain