by **pjdowney** » Mon Aug 29, 2005 4:35 am

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