The New Sudoku Players' Forum

[WallyB]

Hi All

I have written a small DOS sudoku solving program which managed to solve all the problems I encountered easily. It tackles the puzzle directly ("This cell must be 7 because ..") , as would be done manually, and this solves all the simple problems almost instantly. The more difficult puzzles cannot be fully solved in this way so the approach is to tackle the puzzle first directly and then apply trial / error, in an optomised order, to complete the solution. The solution shows those cells determined directly and those obtained by trial and error. It seemed to manage even the difficult problems in a flash until I encountered the following puzzle -

002 | 090 | 107
038 | 600 | 000
400 | 000 | 000
----+-----+----
000 | 005 | 000
009 | 010 | 300
000 | 400 | 000
----+-----+----
000 | 000 | 004
000 | 007 | 920
806 | 030 | 700

- contributed by Addlan under "Favourite Puzzles" on the Solving Techniques Forum on this website. Instead of a result in less than a second the program took several minutes (admittedly on an old P2 computer) and not a single cell was solved directly. There is a re-calculation option which reverses the order in which digits are tried and it confirmed that the solution was unique.

I had thought that a second level of direct processing could reduce the time taken to reach a solution but with such a difficult puzzle I now feel that trial / error is the only practical approach. The time taken to produce the trial / error result is largely determined by the optimisation method used but with solution of all previously encountered problems down to a second or less it seemed hardly justified. I thought a better challenge was to find the most difficult puzzle. This puzzle has changed my thinking and I intend to re-visit my optimisation method.

Any thoughts on this? Is this really the most difficult puzzle?

Wally

[paulc]

I slolved this "Hardest Ever" puzzle in about 20 minutes with my Excel Spreadsheet Solver (Version 2) and a tree of 22 educated guesses.

My Spreadsheet Solver is at www.paulcweb.com/sudoku or www.paulcweb.com/sudoku/sudoku.xls .

The solution to this puzzle is at www.paulcweb.com/sudoku/he.xls . If you bring up this solution and hit the "back" key until you get the puzzle input, you can follow my solution tree and see how I arrived at the solution. Initially, and after entering each "guess" you must hit the "SOLVE" button.

The solution tree is at www.paulcweb.com/sudoku/hetree.xls .

I now need to automate the logic I used to select my trials.

[Oudeis]

I have written a small DOS sudoku solving program which managed to solve all the problems I encountered easily.
002 | 090 | 107
038 | 600 | 000
400 | 000 | 000
----+-----+----
000 | 005 | 000
009 | 010 | 300
000 | 400 | 000
----+-----+----
000 | 000 | 004
000 | 007 | 920
806 | 030 | 700

Any thoughts on this? Is this really the most difficult puzzle?

My java solver, which I wrote yesterday immediately after learning the game, solves it in an instant. I feel quite certain that it would be possible to construct more demanding 9x9-sodukus, and I did in fact succeed in building puzzles which are more difficult for my solver (all of them so far are also solved instantly, but the number of nodes visited during the search is higher for some of them).
One example of such a problem is the following position:

000000000
000000374
000009860
000000000
004010007
060048900
071580020
040000000
500730001

Regards,
Oudeis

[WallyB]

Hi Oudeis

Perhaps you would like to share with us the approach you used in writing your solver which produces instant results for every puzzle.

Wally

[Yves]

...but the number of nodes visited during the search is higher for some of them).
One example of such a problem is the following position:

000000000
000000374
000009860
000000000
004010007
060048900
071580020
040000000
500730001

My solver had to guess for three cells. It's nearly instantaneous, too.
You can find it online at
http://nyctergatis.com/sqr/n-sudoku.sqrcgi

Regards,

Yves

[WallyB]

Hi Yves

I tried your solver on the puzzle at the head of this thread and it gave me a result of "multiple solutions". I know this is not the case.

Wally

[pjdowney]

562893147
738641592
491752683
287365419
649218375
153479268
975126834
314587926
826934751

I got this solution with the Quickbasic 4.5 program I wrote.
It took .021 seconds using. I could make the program faster and
search for multiple solutions when I get some time. /PJD

[squeak]

**4*59*2*
***1*****
*****7*3*
7*26**3*9
**5***8**
1*8**57*2
*7*5*****
*9***2***
*5*87*2**[/b][/i]

[squeak]

**4*59*2*
***1*****
*****7*3*
7*26**3*9
**5***8**
1*8**57*2
*7*5*****
*9***2***
*5*87*2**
[solve please][/img][/list][/code]

[pjdowney]

Squeak,

684359127
327146985
519287634
742618359
935724816
168935742
271593468
893462571
456871293

I did not get around to changing my program to check for multiple solutions. This is the first that came up. It is an easy change. When I was a kid everybody programmed in some version of basic. I can dumb down the code so it will run on just about any computer. The program works by first--- forming a constraint array, c(81,24). It should be obvious that every square can not be the same number as the 8 squares in the same row and 8 squares in the same column and 8 squares in the 3 by 3 box. There is some duplication in the 3 by 3 box and the rows and columns but fixing this would have taken more coding time and only slows the program maybe 10 %. Next I run 81 loops, like FOR...NEXT loops using a loop pointer P. The B(81,2) array holds the start and finish values for each of the 81 loops. For anyone wishing to code like this (which is alot smarter than writing out 81 loops) remember it is imperative that you do not just jump out of any loop without an exit loop or close the loop somehow because each loop stuffs an address in the stack. This program will check EVERY possible solution. Now yes I am aware of the hugh numbers involved but if you you know by box (n) that the matrix is illegal then don't waste time computing A(n+1),A(n+2)....
Anybody out there interested cracking high order prime number cyphers using N-space techniques?????