[Jprogramming] Hard sudoku

[Roger Hui]

That there are exactly 1905 solutions is based on the way
the solver is written.  I feel I have every right to make 
that statement as it is described in the Sudoku article.

I am not familiar with Knuth's Dancing Links Algorithm,
and I don't have time to follow it up.  The "simple but
effective strategy" is to exhaust all forced moves based
on two categories, then make all possible guesses for
a cell with the smallest number of candidates.  Repeat.



----- Original Message ----- 
From: "R.E. Boss" <r.e.boss at planet.nl>
To: "'Programming forum'" <programming at jsoftware.com>
Sent: Wednesday, November 30, 2005 10:45 AM
Subject: RE: [Jprogramming] Hard sudoku

Thanks for the link. Although I could not find there that a single solution
is required.

Repeating a statement does not prove it.
Unless you do so, or at least make it probable, I'll stick to what appears
to be true:  1905 <: # solutions.

Is the "simple but effective strategy" your Sudoku solver uses, the Dancing
Links Algorithm of Knuth?

R.E. Boss


-----Oorspronkelijk bericht-----
Van: programming-bounces at jsoftware.com
[mailto:programming-bounces at jsoftware.com] Namens Roger Hui
Verzonden: woensdag 30 november 2005 18:20
Aan: Programming forum
Onderwerp: Re: [Jprogramming] Hard sudoku

It shows that there are exactly 1905 solutions.

Additional Sudoku lore can be found in the Wikipedia
http://en.wikipedia.org/wiki/Sudoku



----- Original Message ----- 
From: "R.E. Boss" <r.e.boss at planet.nl>
To: "'Programming forum'" <programming at jsoftware.com>
Sent: Wednesday, November 30, 2005 8:45 AM
Subject: RE: [Jprogramming] Hard sudoku

OK. I am not "in Sudoku" but helped a friend with applying your solver. So
was not aware that a Sudoku should have a single solution.

Apart from that, your solver shows there at least 1905 solutions. 

R.E. Boss



-----Oorspronkelijk bericht-----
Van: programming-bounces at jsoftware.com
[mailto:programming-bounces at jsoftware.com] Namens Roger Hui
Verzonden: woensdag 30 november 2005 17:27
Aan: Programming forum
Onderwerp: Re: [Jprogramming] Hard sudoku

The reason it takes so long and so much space is that
the particular puzzle has 1905 solutions, and the solver
found them all.  If you evaluate  sudoku 9 9$0  it would
take even more time and more space, because the program 
would attempt to find all legal Sudoku configurations.

A Sudoku puzzle is usually designed to have a single 
solution, and the "require no more" comment was made 
on that basis.



----- Original Message ----- 
From: "R.E. Boss" <r.e.boss at planet.nl>
To: "'Programming forum'" <programming at jsoftware.com>
Sent: Wednesday, November 30, 2005 3:23 AM
Subject: [Jprogramming] Hard sudoku

In  <http://www.jsoftware.com/jwiki/Essays/Sudoku>
http://www.jsoftware.com/jwiki/Essays/Sudoku Hui writes " Even puzzles rated
as "very hard" require no more than 15 milliseconds and 30 Kbytes on a 500
MHz Pentium 3 computer" 

However on my machine (Win XP 64 bits on 2.2 Ghz dual core AMD with 2Gb)
this sudoku 

x=: , 0&".;._2 (0 : 0)
5 0 6 0 2 0 9 0 3
0 0 8 0 0 0 5 0 0
0 0 0 0 0 0 0 0 0
6 0 0 2 8 5 0 0 9
0 0 0 9 0 3 0 0 0
8 0 0 7 6 1 0 0 4
0 0 0 0 0 0 0 0 0
0 0 4 0 0 0 3 0 0
2 0 1 0 5 0 6 0 7
)

produces 

   ts'sudoku x'
2.6851779 11799104