Sudoku Players' Forum (clone)

=============================================

After reading P.J. Downey's claims about his Soduko solving algorithm,
I was eager to give it a try, especially since it was so compact.
Once able to understand the "big idea", its simplicity and directness
(not to mention effectiveness) struct me as quite beautiful.

Solving Soduko puzzles by hand is a matter of elimination. One strives
to make eliminations and deductions with 100% confidence. Only when
stuck does one "guess" and hope to be on the right path.

Mr. Downey's computer algorithm, on the other hand, is 100% guess, with
the full knowledge that subsequent contradictions and backtracking will
eventually lead to the solution.

I did give Mr. Downey's algorithm a try and even made a modest improvement
(not that a few milli-seconds really make any difference). His algorithm attacks
grid cells in order, starting with cell 1 and ending with cell 81.

My idea is to pre-compute the order in which cells are attacked:

1. Choose the cells for which a value is known.
Make a list of the remaining cell positions.
2. From the remaining cell positions, choose the position most likely
to cause a conflict; that is, choose the position whose associated
constraint array references the most known grid positions.
Suppose we choose grid cell `k'.
3. Deleted position `k' from the list.
Subsequently, treat grid cell `k' as if it were known.
4. Go to step 2, as long as any positions remain.

My program is written in "C++" and run on my home computer,
using an Intel 2.26GHz Pentium 4 Processor.

Timing Comparisons:
Downey Original = .134 seconds / solution
Downey Modified = .065 seconds / solution (to include the
overhead of pre-computing the attack order)

Michael A. Deverin
[url=mailto:devfam47@vtisp.com]devfam47@vtisp.com[/url]
2005.09.03

===============================================

Thanks for the words. Great idea to vary the attack cell order. Any one else have any suggestions ???

Mr. Downey: Thats a great program - when I saw how good it is I thought that Sudoku needs to be canceled. It solves any puzzle, doesn't care if puzzle is easy or hard, and if multiple solutions exist it finds them all!???(understanding those are non-true Sudokus).

Thanks for sharing the program. It was fun seeing how it works. So now I set out to make a puzzle that is specifically difficult for your program. As your program works from left to right and top to bottom, checking all grids (and smartly bypassing non-valid regions), I came up with the following features of a difficult puzzle:

- the puzzle has small number of clues (17 in this case)
- clues are bunched near the bottom (in this case the top row has no clues at all)
- this puzzle has one more unusual feature but I won't say, it would be too good of a clue to anyone trying to solve it.

Here is the puzzle:
--- --- ---
--- --3 -85
--1 -2- ---

--- 5-7 ---
--4 --- 1--
-9- --- ---

5-- --- -73
--2 -1- ---
--- -4- --9

I entered this puzzle to your program, started dinner, took a shower, ate dinner, read some of todays paper, then checked for a solution. Not yet. I'm not mult-tasking so I aborted the program to post this message. I'll run again tonight (and I think it will have answer based on progress I saw so far)

But no doubt - your program is still groundbreaking. A true mathematical work of art.

Its also encouraging to hear that you may attempt to learn the total number of Sudoku grids that exist. If you make progress please keep us informed. We all know its a lot, but no one has seen a proof or demonstration what that number may be.

Thanks for the program. It has made me think that Sudoku programs are more of a puzzle, and the Sudoku puzzle itself is just incidental!

oysterkite wrote:- this puzzle has one more unusual feature but I won't say, it would be too good of a clue to anyone trying to solve it.

LOL

Foxglove, your distribution of how many cells you can fill in at a given point in the puzzle depends entirely what techniques you use. It certainly holds if you only use hidden and naked singles. if you apply some other techniques you can get this distribution: 5 11 12 6 6 10 13 1

oysterkite wrote:Its also encouraging to hear that you may attempt to learn the total number of Sudoku grids that exist. If you make progress please keep us informed. We all know its a lot, but no one has seen a proof or demonstration what that number may be.

Have you looked here oysterkite:
http://en.wikipedia.org/wiki/Sudoku

ab wrote:Foxglove, your distribution of how many cells you can fill in at a given point in the puzzle depends entirely what techniques you use.

That's why they are green. Some other technique would be a red bar pointing down. The harder the deeper te red bar.

ab wrote:Foxglove, your distribution of how many cells you can fill in at a given point in the puzzle depends entirely what techniques you use.

That's why they are green. Some other technique would be a red bar pointing down. The harder the deeper te red bar.

Thanks foxglove for showing me that puzzle is easy (I assume that chart means easier than average, and takes moderate time to solve).

I agree the puzzle is easy when solving sudokus with normal logic (like humans do, or programs that simulate human methods).

Mr. Downeys program solves puzzles by brute force. Even though something like 6.6 x 10^21 final grids exist, his program will essentially check every grid if necessary to find the answer for a given puzzle. His program is amazingly efficient because of very clever arrays he set-up before making the sweep. The "easy" puzzle I submitted is near the "very end" of his search routine (I believe). On my slow PC (133MHz) it ran several hours and gave no solution, then I ran it overnight, and the correct solution was provided (somewhere between 3-9 hours?).

But I tested his program on puzzles which were regarded as the most difficult known (i.e. top1465#77) and it solved it in less than a second!

To me its very interesting to see the difference between logical solvers and brute force solvers.

Honestly, I think Mr. Downeys program is the best I have ever seen. By brute force it guarantees a solution to every puzzle. The time required is not related to the difficulty of the puzzle - Its related to processor speed and where the answer lies among the range of "all known final grids". Also, the brute force method cannot have much screen output while solving - it would cripple the program. Best to have minimal output or just a black screen and wait for the answer.

Also, AB, thanks for refernce to # of final grids. I'll visit wikepedia to see what it says.

Hello friends,
I wrote this program pretty much off the cuff in about an hour a few months ago. Today I came back on site and took a look at the code. I can see how to make this program run somewhere in the order of 10 to the 6th times faster (best guess or perhaps wishful thing). Here is how and I think this solver will blow anything in the world away. I will not have the time to code it till april and it will probabily take an hour or two for me. If someone wants to do it here goes.....
The original code effectively sets up nested loops on cells 1 to 81 with resultant rapid pruning due to logical constraints. In other words you loop on level i when a illogical constraint is apparent on level i. Now there is no reason that the cell loops must be nested 1,2,3,4....81. Obviously the given cells can be immediately fixed and the choice of cell loop order can then be chosen intelligently and not in just rote order. My initial feeling is to define a one dimensional matrix of each cells number of constraints, sort in descending order and then use this as the loop order. Let me explain. Lets say cell 1 has 6 filled cells in it's constraint group of 20. Cell 2 has 4, ....The outer loops should be obviously be on the most constrained cells. I can see a few other methods of improvement but this should be surprising. Thanks /pjd.

I transcribed the basic to C. As a sanity check would you run this puzzle, #1 from the top1465, through your solver, and report the solution time?
thanks

Code: Select all

4...3....
...6..8..
........1
....5..9.
.8....6..
.7.2.....
...1.27..
5.3....4.
9........


468931527
751624839
392578461
134756298
289413675
675289314
846192753
513867942
927345186

One solution. I ran it on my kid's computer, mine was donated to the local school. This computer has 57 running processes and 2377 modules on it so a good speed measure is difficult. Took 5minutes and 25 seconds. I have a concept for a far superior engine.

pjdowney wrote:One solution. I ran it on my kid's computer, mine was donated to the local school. This computer has 57 running processes and 2377 modules on it so a good speed measure is difficult. Took 5minutes and 25 seconds. I have a concept for a far superior engine.

your basic transcribed to C took 8 sec on a 2.8 Ghz pentium4
there's room for improvement
for the top1465 the C version of your solver took 8m21.95s for a rate of 1/sec/Ghz
the fastest backtrack solvers rate 700/sec/Ghz to 1200/sec/Ghz for the top1465
for random puzzle collections the fastest backtrack solvers range from 700/sec/Ghz to 10000/sec/Ghz depending on puzzle difficulty
see http://www.setbb.com/sudoku/viewtopic.php?p=5030&mforum=sudoku#5030
the first suggestion would be "use bitmasks"

Here is an update of the pjdowney program. Let me explain what it is about. It is a program that will find all solutions to a sudoku array with mathematical certainity. It will not miss any solutions and if no solution exists it will tell you. It is essentially 81 nested loops for the 81 cells in the array and anytime sudoku illegality is detected the rest of the inner loops are bypassed. The program has been changed to fix a few minor logic errors in the code ( the old program still worked 100% of the time) and display the array as the program works (fun to look at and only adds 1% to the overhead by displaying every 30,000 loops). It has been called a brute force utilitarian program and I agree. Attempts have been made to produce arrays that run longer with this program and you can by understanding what the program does but no attempt to make a single or multi-solution array that can't be solved has been successful. The program will always find all solutions time permitting. I hope this tool may be of assistance. /pjd

'Written by Paul J. Downey, Version 2
'pjdowney@peoplepc.com
'this program will find all Sudoku solutions
'for the array entered in the data section
DEFINT A-Z
'defint makes the program alot faster
CLS : SL = 0
'SL is the solution number
DIM A(81), B(81, 2), C(81, 24), Z(81)
'A(81) is the main Sudoku array
'B(81,2) is the loops limit array. The program effectively
'runs 81 nexted for..next type loops using a variable pointer
'for example a variable loop pointer effrectively does
'FOR A(1)=B(1,1) TO B(1,2)
'FOR A(2)=B(2,1) TO B(2,2)...
'FOR A(81)=B(81,1) TO B(81,2)
'C(81,24) is the constraint array.
'C(n,1...8) are the other numbers in the same row as n
'C(n,9...16) are the other numbers in the same column as n
'C(n,17...24) are the other numbers in the same box as n
'where n is expressed as 1 to 81, the 9x9 in linear form.
'C(n,1...24) is then cleaned up to C(n,1...20) to avoid
'box duplication with rows and colums
'Z(n) tell you if location n has been given to you
'Z(n)=1 means location n was defined with a value in the
'sudoku puzzle else 0
FOR I = 1 TO 81: T = 0
FOR J = 1 TO 9
S = INT((I - 1) / 9) * 9 + J
IF S <> I THEN
T = T + 1
C(I, T) = S
END IF
NEXT J
T = 8
FOR J = 1 TO 9
S = I - INT((I - 1) / 9) * 9 + (J - 1) * 9
IF S <> I THEN
T = T + 1
C(I, T) = S
END IF
NEXT J
T = 16
I1 = INT(INT((I - 1) / 9) / 3)
J1 = INT((I - INT((I - 1) / 9) * 9 - 1) / 3)
FOR I2 = 0 TO 2
FOR J2 = 0 TO 2
S = I1 * 27 + I2 * 9 + J1 * 3 + J2 + 1
IF S <> I THEN
T = T + 1
C(I, T) = S
END IF
NEXT J2
NEXT I2
NEXT I
FOR I = 1 TO 81
T = 17
FOR J = 17 TO 24: L = 0
FOR K = 1 TO 16
IF C(I, J) = C(I, K) THEN L = 1
NEXT K
IF L = 0 THEN
C(I, T) = C(I, J)
T = T + 1
END IF
NEXT J
NEXT I
'all the above code does is make the constraint array
FOR I = 1 TO 81: PRINT "CELL #"; I: INPUT A(I)
IF A(I) = 0 THEN
B(I, 1) = 1
B(I, 2) = 9
Z(I) = 0
ELSE
B(I, 1) = A(I)
B(I, 2) = A(I)
Z(I) = 1
END IF
NEXT I
'the above code fills the upper and lower limits of the loops
'P is the variable pointer. The program is actually 81 nested
'loops with legality checks on each loop. The actual amount of
'calculation is actually very small to solve for every solution
'because immediately if non-suduku legality is detected the rest
'of the array looping is pruned.
'the next 30 lines or so is the actual solving routine, followed
'by a print routine
'I wrote this program in about an hour for quickbasic. If there
'is interest I can write it in a very generic form of basic that
'will run on anything. I think it will find all sudoku solutions
'quite quickly. People have e-mailed me that they are blown away
'by the search routine but couldn't figure out the code. I hope
'this helps.
TMR1& = TIMER: CLS : PC = 0
P = 1: A(1) = B(1, 1)
TOP: PC = PC + 1
IF PC = 30000 THEN
FOR I = 0 TO 8: FOR J = 1 TO 9: LOCATE I + 1, J * 3: PRINT A(I * 9 + J); : NEXT J: NEXT I
PC = 0
END IF
IF Z(P) = 1 THEN GOTO LGL
L = 1
FOR I = 1 TO 20
IF A(P) = A(C(P, I)) THEN
L = 0
EXIT FOR
END IF
NEXT I
IF L = 0 THEN GOTO NLGL
LGL: P = P + 1
IF P = 82 THEN
GOSUB PRTMAT
P = P - 1
GOTO NLGL
END IF
A(P) = B(P, 1)
GOTO TOP
NLGL: A(P) = A(P) + 1
IF A(P) <= B(P, 2) GOTO TOP
IF Z(P) = 1 THEN
A(P) = B(P, 1)
ELSE
A(P) = 0
END IF
P = P - 1
IF P = 0 THEN
PRINT "END OF SEARCH"
INPUT Z
STOP
END IF
GOTO NLGL
PRTMAT: SL = SL + 1
CLS
FOR P1 = 0 TO 8: FOR P2 = 1 TO 9
PRINT A(P1 * 9 + P2);
NEXT P2: PRINT : NEXT P1
PRINT "SOLUTION #=", SL
TMR2& = TIMER: PRINT "EXECUTION SECONDS= "; TMR2& - TMR1&
INPUT Y
CLS
RETURN

Get the solution in 0.01 seconds :

http://www.kinabaloo.com/relax/sudoku.html

You can paste in the text representation below the sudoku grid.

Jo