The New Sudoku Players' Forum

[pjdowney]

DEFINT A-Z
CLS : IP = 0
DIM A(81), B(81, 2), C(81, 24), Z(81)
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: READ 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
P = 1: A(1) = B(1, 1)
TOP: L = 1: GOSUB PRTMAT
FOR I = 1 TO 24
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
IP = 999
GOSUB PRTMAT
PRINT "SOLUTION"
INPUT Z
STOP
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
GOTO NLGL
PRTMAT: IP = IP + 1
IF IP = 1000 THEN
CLS
FOR P1 = 0 TO 8: FOR P2 = 1 TO 9
PRINT A(P1 * 9 + P2);
NEXT P2: PRINT : NEXT P1
IP = 0
END IF
RETURN

DATA 1,0,0,2,8,7,0,0,0
DATA 0,0,0,0,0,0,0,0,3
DATA 9,0,0,6,3,0,0,0,1
DATA 0,0,0,0,7,0,0,0,6
DATA 7,9,5,0,6,1,2,0,0
DATA 8,3,0,5,0,0,0,0,0
DATA 3,0,0,0,0,0,0,0,0
DATA 0,0,7,0,0,9,0,0,5
DATA 2,0,1,7,0,0,6,0,4



Folks, program works good. Just put the initial puzzle in the data area.
The program was written in quick basic 4.5 in about an hour and a half.
The first portion creates the constraint array and the second part uses a variable pointer to simulate 81 nested loops. It solves on my hyper threading machine in about .02 seconds any puzzle. I would be happy to provide tech assistance. I have a background in physics and cryptography. I hope it does not take the fun out of it. /PJD

[pjdowney]

My the way, it shows the array as it works towards a solution for those with slower computers. The solution will say solution after the array when it is done. It was a quick up coding job. Have fun. /PJD

[PaulIQ164]

You know, there's a forum specifically for Solver Programs. But I guess it's too lake now. Still, y'know, for reference and all.

[pjdowney]

I've had people e-mail me saying they are blown away by how fast this program will solve any array and would I please comment the code to explain how it works. I changed it to give all solutions if any....

'Written by Paul J. Downey
'pjdowne@attg.net
'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 nested 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
FOR K = 1 TO 16
IF A(J) = A(K) THEN
A(T) = A(J)
T = T + 1
EXIT FOR
END IF
NEXT K
NEXT J
NEXT I
'all the above code does is make the constraint array
FOR I = 1 TO 81: READ 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.
P = 1: A(1) = B(1, 1)
TOP: L = 1
FOR I = 1 TO 24
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
RETURN

DATA 0,0,1,0,0,0,0,2,0
DATA 3,0,0,0,4,0,5,0,0
DATA 4,0,0,0,6,2,1,0,0
DATA 0,3,0,1,0,6,0,7,0
DATA 0,5,0,0,0,0,0,8,0
DATA 0,2,0,9,0,3,0,4,0
DATA 0,0,3,4,7,0,0,0,9
DATA 0,0,6,0,1,0,0,0,3
DATA 0,8,0,0,0,0,2,0,0

[ovaltrade]

I would be curious to know the processor speed of yout HT machine...

The idea is to convert your timing into a rough number of machine cycles.
This then allows to compare the speed of algorithms executed on processors with different clock speed.

[pjdowney]

OT,
That's a good question. I have one of these new Dell Desktop machines and I think it's running in the mid 3 ghz. I use it isolated from the internet. The program I wrote was a quick code up job that seems to solve any matrix in something about .02 seconds on this machine. Another gentleman improved the routine on another thread. I was hoping to solve the number of legal sudoku matricies by fixing the top row as 1 thru 9 and setting 10 thru 81 as 0 thus cutting the number of solutions by 9! The program would then solve for the number of solutions. btw... the number of solutions, sl, needed to be a double precision value because of it's large value. The program was solving 75,000 matricies a minute. At this stage it was obvious that even if the program was sped up by a factor of 10 or 100 it was not fast enough. I need to get off the brute force and do more analysis. I am starting to consider monte carlo techniques to approximate the number of sudoku legal matricies. Any mathematicans want to jump in and lend a hand? The program I wrote is in basic which is pretty generic and it runs fast because it eliminates virtually all possibilities very rapidly and actually does very little work. It will find all solutions (time permitting) or tell you none exist. I think the program could be written maybe 100x faster in an assembly language for the core program section BUT I think more analysis of the problem would pay off better results. /pjd

[pjdowney]

Numerous people have e-mailed me asking how to run this program. I have made an executable file, sud15.exe. The exact source code is below and I will try to attach the exe file to this post. The code was re-written and it asks for the original array in numbers from 1 to 81. For example, the first 9 numbers asked for are row 1 etc. You put in 0 (zero not oh) if the value is not specified and the number if it is specified in the original array.
Here is the source code, the exe file is 36178 bytes.

Written by Paul J. Downey
'pjdowne@attg.net
'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
FOR K = 1 TO 16
IF a(J) = a(K) THEN
a(T) = a(J)
T = T + 1
EXIT FOR
END IF
NEXT K
NEXT J
NEXT i
'all the above code does is make the constraint array
FOR i = 1 TO 81: PRINT 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.
P = 1: a(1) = B(1, 1)
TOP: L = 1
FOR i = 1 TO 24
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
RETURN

I can't seem to attach the exe to this post. Anybody know where I can post a copy of the exe file to this code ??? Maybe a shareware site ???

[ovaltrade]

Let's compare notes...

My "solver" is embedded into a 32-bit DLL Sudoku.dll called by a small VB main program Sudoku.exe.

This Sudoku.exe program is not designed for general public pressure but simply to test the speed of the solver. By example, it does not validate the Grid before sending it to the embedded solver. You may download into a temporary test directory on your machines the 2 files zipped at http://ovaltrade.com/sudoku/ovaltrade/sudoku.zip

As long as the DLL is in the same directory as the EXE, eveything should work ok (use a shortcut with its "start in" directory set to the location of the DLL).

To alter the grid, clic on any square, enter 1 to 9 or 0 or a space...

If you provide a Grid which requires too much time to solve, crash the program by closing it or use Task Manager to get rid of it.

If you want, I can add your compiled program into my web server so everybody else can download it as well. Just send it to me attached to a standard email at jack@ovaltrade.com...[/url]

[pjdowney]

Thanks OT,
I sent the exe to you. /pjd

[ovaltrade]

Your program is now accessible at http://ovaltrade.com/sudoku/pjdowney/sud15.exe.

To time exactly your program, you would need to instrument it by inserting a call to a small function which in turn will execute the RDTSC machine instruction. This will return the current machine cycles consumed since power up. By calling it at the start of the function, then at the moment the 1rst solution is found, you subtract both values to obtain the exact amount of cycles consumed by the so-instrumented function.

Unfortunately, while your function is running, it may be interrupted by the OS for quantum end, network activities or other invisible background activity in your machine. This extra CPU time will be part of the differential. So, to obtain a better count, you "time" your function in a loop, say 5000 times, then you calculate the average or keep the smallest value.

I guess your program is 16-bit (let me check...) Yes it is. I may provide you later (now I must go back to work) with a small 16-bit .obj you could add to the link process of your program. This will allow you to call the RDTSC instruction to retrieve the Time Stamp Counter.

[pjdowney]

I've had people e-mail me about using this program to find the number of legal sudoku arrays. My search engine method has been modified and improved alot since written a while back and if you fill the 9x9 data block with zeros (undefined values) you will get the number. Of course the number is very large and pre-analysis is required so the cpu does not have to do such heavy lifting. For example, the first 9 boxes should obviously be 1 to 9 to thus cutting down the work by 9 factorial. I think a combination of analysis and grid computational power is the easiest methodology. I'm sorry guys but I haven't had time to work this problem. If the solution is not attained in a month or so, I'll give it a good try. /pjd

[oysterkite]

To set your program to count the total number of legal sudoku grids, setting the top row to 1-9 will help as you say. Total grids would then be 9! (362,880) times as many solutions your program finds.

You can also take into account the fact that rows can be moved within 3x9 blocks (6 permutations) to get different variations of the same puzzle.
The same applies to columns, and also to 3x9 vertical and 3x9 horizontal blocks within the 9x9 grid. This is 8 cases of 6 variations each, or 6^8 (1,679,616). Then the puzzle can also be transposed (another factor of 2).

So, you can constrain the initial grid as shown and then count solutions:

123------
4561-----
789---1--
-1-------
----1----
-------1-
--1------
-----1---
--------1

Then the total number of legal sudoku grids would be 9! x 6^8 x 2 = 362,880 x 1,679,616 x 2 times the number of solutions that your program would find. Please post if anyone notices mistake in my math.

Mr. Downeys program combined with big horsepower processor might be one way that the total number of legal sudoku grids can be counted. In fact, I don't know of any other way to do it.

Thanks again PJD for your clever program.

VR

[ab]

Mr. Downeys program combined with big horsepower processor might be one way that the total number of legal sudoku grids can be counted. In fact, I don't know of any other way to do it.


VR

hve a look here:
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_all_possible_Sudoku_solutions

[SHuisman]

I must say, i'm very impressed by the code, and i see the code working only. I translated into vb, vb is _slow_ it took 9.133 seconds to find 19 solutions of in visual basic itself. I brought it down to 9.0 -> 8.4 -> 8.3 -> 7.8 with some modifications.

Code: Select all

600319007000204000000000000180000069700060001040000075000000000000408000900703006


I found a sudoku that takes AGES to find using this algorith, because it starts to guess at box1, then 2, then 3 etc.:

Code: Select all

000000000000003085001020000000507000004000100090000000500000073002010000000040009

Anyone any suggestions ?