>Pretty cool!
>
>
http://www.vsj.co.uk/articles/display.asp?id=540Done already. The following I've written over the past few months. It should solve about any sudoku puzzle.
Walter,
LPARAMETERS cPuzzle
LOCAL nFound, nFoundByBlock, nFoundByCol, nFoundByRow
PRIVATE nTotal
nTotal = 0
nAttempt = 0
nCalled = 0
DIMENSION aResult[9,9]
STORE "." TO aResult
_SCREEN.FontName = "Courier New"
=SYS(3055, 400)
SET TALK OFF
CLEAR
SET ENGINEBEHAVIOR 70
SET DELETED ON
** Make a table of all possible combinations (Each 81 cells have numbers 1 to 9 := 729 records)
CREATE CURSOR Comb (Row C(1), Col C(1), blk C(1), Num C(1), Attempt int, ID int)
nX = 0
FOR nRow = 1 TO 9
FOR nCol = 1 TO 9
FOR nNum = 1 TO 9
nBlk = INT((nCol-1)/3)+1 + 3*INT((nRow-1)/3)
INSERT INTO Comb VALUES(STR(nRow,1), STR(nCol,1), STR(nBlk,1), STR(nNum,1), 0, nX)
NX = NX + 1
ENDFOR
ENDFOR
ENDFOR
** Use indexes for speeding up eliminations by using rushmore
INDEX ON Num+row TAG row
INDEX ON Num+col TAG col
INDEX ON Num+blk TAG blk
INDEX ON row+col TAG Num
INDEX ON Col TAG Col2
*INDEX ON Num TAG Num2
INDEX ON row TAG row2
INDEX ON Row+Col+Num TAG rowcolnum
SET ORDER TO 0
SELECT 0
CREATE CURSOR xx (row C(1))
INSERT INTO xx VALUES ("1")
INSERT INTO xx VALUES ("2")
INSERT INTO xx VALUES ("3")
INSERT INTO xx VALUES ("4")
INSERT INTO xx VALUES ("5")
INSERT INTO xx VALUES ("6")
INSERT INTO xx VALUES ("7")
INSERT INTO xx VALUES ("8")
INSERT INTO xx VALUES ("9")
SELECT x1.Row as col, X2.Row, " " as num FROM xx X1, xx X2 INTO CURSOR xy
* Set the known numbers (and eliminate possible combinations)
nSec = SECONDS()
IF EMPTY(cPuzzle)
*** cPuzzle = "6...4...3.1.....7...5...8.....5.2...3...9...2...1.3.....8...9...7.....5.2...3...4"
TEXT TO cPuzzle PRETEXT 3
8 . 2|. . .|. 4 3
6 . .|. 4 .|. . .
. 4 9|3 . .|. . 1
-----+-----+-----
4 . 1|2 . 7|. . .
. . .|. 5 .|. . .
. . .|9 . 4|3 . 2
-----+-----+-----
1 . .|. . 6|5 8 .
. . .|. 9 .|. . 7
9 5 .|. . .|1 . 4
ENDTEXT
ENDIF
nRow = 1
cString = CHRTRAN(cPuzzle,"+-| "+CHR(13)+CHR(10)+CHR(9),"")
FOR nT = 1 TO 81
IF ISDIGIT(SUBSTR(cString, nT,1))
SetNumber(STR(INT((nt-1)/9)+1,1), STR(((nT-1)%9)+1,1), SUBSTR(cString, nT,1))
ENDIF
ENDFOR
nFound = 1
nX = 0
lSolvable = .t.
*SET COVERAGE TO Log.txt
? nTotal
DO SolvePuzzle WITH nTotal, 0, 0
? SECONDS() - nSec
*SET COVERAGE TO
*MODIFY FILE Log.txt
** Display result
*SET PRINTER ON
*SET PRINTER FONT "courier New",24
?
? "Total: = "+ALLTRIM(STR(nTotal)), nX, nCalled
DO displaymap
CREATE CURSOR Resx (Row N(1), Col N(1), Pos C(18), Num N(1))
FOR nRow = 1 TO 9
FOR nCol = 1 TO 9
IF ISDIGIT(aResult[nRow, nCol])
INSERT INTO Resx VALUES (nRow, nCol, "", VAL(aResult[nRow, nCol]))
ELSE
cString = " "+CHR(13)+" "+CHR(13)+" "
SELECT Comb
SCAN FOR Row = STR(nRow, 1) AND Col = STR(nCol,1)
nNum = VAL(Num)
cString = STUFF(cString, nNum+INT((nNum-1)/ 3), 1, Num)
ENDSCAN
INSERT INTO Resx VALUES (nRow, nCol, cString, 0)
ENDIF
ENDFOR
ENDFOR
FUNCTION DisplayMap
?
FOR nRow = 1 TO 9
?
FOR nCol = 1 TO 9
?? aResult[nRow, nCol]+ IIF(INLIST(nCol,3,6),"|"," ")
ENDFOR
IF INLIST(nRow,3,6)
? "-----+-----+-----"
ENDIF
ENDFOR
*SET PRINTER OFF
*SET PRINTER TO
RETURN
*-
FUNCTION SolvePuzzle
PARAMETERS nTotal, nAttempt, nRecno
LOCAL aRes2[9,9], nTot, nTotSave, nX, nT, nFound
nX = 0
nFound = nTotal
STORE 0 TO nFoundByBlock, nFoundByCol, nFoundByRow
DO WHILE nFound > 0 AND nX < 800 AND nTotal < 81
nFound = 0
nFoundByRowCol = 0
SELECT *, CNT(*) as Cnt FROM Comb GROUP BY Row, Col INTO CURSOR X
IF RECCOUNT("X") + nTotal < 81
?? "Not solvable [a position ran out of candidates]"
EXIT
ELSE
COUNT FOR cnt = 1 AND SetNumber(Row, Col, Num) TO nFoundByRowCol
ENDIF
** eliminate combinations by 3x3 blocks
SELECT * FROM Comb GROUP BY Num, blk HAVING CNT(*) = 1 INTO CURSOR X
COUNT FOR SetNumber(Row, Col, Num) TO nFoundByBlock
** eliminate combinations by columns
SELECT * FROM Comb GROUP BY Num, Col HAVING CNT(*) = 1 INTO CURSOR X
COUNT FOR SetNumber(Row, Col, Num) TO nFoundByCol
** eliminate combinations by rows
SELECT * FROM Comb GROUP BY Num, Row HAVING CNT(*) = 1 INTO CURSOR X
COUNT FOR SetNumber(Row, Col, Num) TO nFoundByRow
nFound = nFoundByBlock + nFoundByCol + nFoundByRow + nFoundByRowCol
IF nFound = 0 AND nTotal < 81
SELECT Row, Num, blk FROM Comb GROUP BY 1,2 HAVING MIN(blk) = MAX(blk) INTO CURSOR x
SCAN
DELETE FOR Num+Blk = x.Num+x.Blk AND Row <> x.Row IN Comb
nFound= nFound+ _Tally
ENDSCAN
SELECT Col, Num, blk FROM Comb GROUP BY 1,2 HAVING MIN(blk) = MAX(blk) INTO CURSOR x
SCAN
DELETE FOR Num+Blk = x.Num+x.Blk AND Col <> x.Col IN Comb
nFound= nFound+ _Tally
ENDSCAN
SELECT MIN(row), MAX(row), MIN(col), MAX(Col), Num, blk, Count(*) as cnt ;
FROM Comb GROUP BY blk, Num ;
HAVING (CNT(*) = 2 OR cnt(*) = 3) AND (MIN(row) = MAX(row) OR MIN(col) = MAX(Col)) INTO CURSOR x
SCAN
DO CASE
CASE x.Min_row = x.Max_row
DELETE FOR Num+Row = x.Num+x.Min_Row AND blk <> x.Blk IN Comb
CASE x.Min_Col = x.Max_Col
DELETE FOR Num+Col = x.Num+x.Min_Col AND blk <> x.Blk AND Num = x.Num IN Comb
ENDCASE
nFound= nFound+ _Tally
ENDSCAN
** Row chain analysis
IF nFound = 0 AND nAttempt = 0
SELECT Col, Row, Num FROM Comb ;
UNION ALL ;
SELECT col, row, num FROM xy WHERE NOT EXISTS (SELECT 1 FROM Comb WHERE Col = xy.col AND Row = Xy.Row) ;
ORDER BY 2,1 ;
INTO CURSOR z
SELECT XX.Row, x1.Num as Col1, X2.Num as Col2, X3.Num as Col3, X4.Num as Col4, X5.Num as Col5, X6.Num as Col6, ;
X7.Num as Col7, X8.Num as Col8, X9.Num as Col9 ;
FROM xx ;
INNER JOIN Z X1 ON X1.Col = "1" AND X1.Row = XX.Row ;
INNER JOIN Z X2 ON X2.Col = "2" AND X2.Row = XX.Row AND (X2.Num =" " OR X2.Num NOT IN (NVL(X1.Num,"X"))) ;
INNER JOIN Z X3 ON X3.Col = "3" AND X3.Row = XX.Row AND (X3.Num =" " OR X3.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"))) ;
INNER JOIN Z X4 ON X4.Col = "4" AND X4.Row = XX.Row AND (X4.Num =" " OR X4.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"))) ;
INNER JOIN Z X5 ON X5.Col = "5" AND X5.Row = XX.Row AND (X5.Num =" " OR X5.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"))) ;
INNER JOIN Z X6 ON X6.Col = "6" AND X6.Row = XX.Row AND (X6.Num =" " OR X6.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"))) ;
INNER JOIN Z X7 ON X7.Col = "7" AND X7.Row = XX.Row AND (X7.Num =" " OR X7.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"), NVL(X6.Num,"X"))) ;
INNER JOIN Z X8 ON X8.Col = "8" AND X8.Row = XX.Row AND (X8.Num =" " OR X8.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"), NVL(X6.Num,"X"), NVL(X7.Num,"X"))) ;
INNER JOIN Z X9 ON X9.Col = "9" AND X9.Row = XX.Row AND (X9.Num =" " OR X9.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"), NVL(X6.Num,"X"), NVL(X7.Num,"X"), NVL(X8.Num,"X"))) ;
INTO CURSOR x
SELECT * FROM Comb C ;
WHERE (Col = "1" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col1 AND row = c.Row)) OR ;
(Col = "2" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col2 AND row = c.Row)) OR ;
(Col = "3" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col3 AND row = c.Row)) OR ;
(Col = "4" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col4 AND row = c.Row)) OR ;
(Col = "5" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col5 AND row = c.Row)) OR ;
(Col = "6" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col6 AND row = c.Row)) OR ;
(Col = "7" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col7 AND row = c.Row)) OR ;
(Col = "8" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col8 AND row = c.Row)) OR ;
(Col = "9" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Col9 AND row = c.Row)) ;
INTO CURSOR Y
nFound = _Tally
SCAN
DELETE FOR Row+Col+Num = Y.Row+Y.Col+Y.Num IN Comb
ENDSCAN
SELECT XX.Row as col, x1.Num as Row1, X2.Num as Row2, X3.Num as Row3, X4.Num as Row4, X5.Num as Row5, X6.Num as Row6, ;
X7.Num as Row7, X8.Num as Row8, X9.Num as Row9 ;
FROM xx ;
INNER JOIN Z X1 ON X1.Row = "1" AND X1.Col = XX.Row ;
INNER JOIN Z X2 ON X2.Row = "2" AND X2.Col = XX.Row AND (X2.Num =" " OR X2.Num NOT IN (NVL(X1.Num,"X"))) ;
INNER JOIN Z X3 ON X3.Row = "3" AND X3.Col = XX.Row AND (X3.Num =" " OR X3.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"))) ;
INNER JOIN Z X4 ON X4.Row = "4" AND X4.Col = XX.Row AND (X4.Num =" " OR X4.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"))) ;
INNER JOIN Z X5 ON X5.Row = "5" AND X5.Col = XX.Row AND (X5.Num =" " OR X5.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"))) ;
INNER JOIN Z X6 ON X6.Row = "6" AND X6.Col = XX.Row AND (X6.Num =" " OR X6.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"))) ;
INNER JOIN Z X7 ON X7.Row = "7" AND X7.Col = XX.Row AND (X7.Num =" " OR X7.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"), NVL(X6.Num,"X"))) ;
INNER JOIN Z X8 ON X8.Row = "8" AND X8.Col = XX.Row AND (X8.Num =" " OR X8.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"), NVL(X6.Num,"X"), NVL(X7.Num,"X"))) ;
INNER JOIN Z X9 ON X9.Row = "9" AND X9.Col = XX.Row AND (X9.Num =" " OR X9.Num NOT IN (NVL(X1.Num,"X"), NVL(X2.Num,"X"), NVL(X3.Num,"X"), NVL(X4.Num,"X"), NVL(X5.Num,"X"), NVL(X6.Num,"X"), NVL(X7.Num,"X"), NVL(X8.Num,"X"))) ;
INTO CURSOR x
SELECT * FROM Comb C ;
WHERE (Row = "1" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row1 AND Col = c.Col)) OR ;
(Row = "2" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row2 AND Col = c.Col)) OR ;
(Row = "3" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row3 AND Col = c.Col)) OR ;
(Row = "4" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row4 AND Col = c.Col)) OR ;
(Row = "5" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row5 AND Col = c.Col)) OR ;
(Row = "6" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row6 AND Col = c.Col)) OR ;
(Row = "7" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row7 AND Col = c.Col)) OR ;
(Row = "8" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row8 AND Col = c.Col)) OR ;
(Row = "9" AND !EXIST(SELECT 1 FROM X WHERE C.Num = Row9 AND Col = c.Col)) ;
INTO CURSOR Y
nFound = _Tally
SCAN
DELETE FOR Row+Col+Num = Y.Row+Y.Col+Y.Num IN Comb
ENDSCAN
ENDIF
IF nFound= 0
SELECT Comb
IF nAttempt = 0 AND TAGNO("del") = 0
INDEX ON DELETED() TAG Del
ENDIF
&& hmmm not getting much progress here, We obviously deal with a more difficult puzzle
&& Just find a cell where only two (or three) values are possible, choose one and try.
&& If not succesfull try the next
nTotSave = nTotal
ACOPY(aResult, aRes2)
IF TYPE("aTcx[nRecno,1]") = "C"
nRecno = nRecno + 1
DO WHILE ALEN(aTcx,1) >= nRecno AND ISDIGIT(aResult[VAL(aTcx[nRecno,1]), VAL(aTcx[nRecno,2])])
nRecno = nRecno + 1
ENDDO
ENDIF
IF TYPE("aTcx[nRecno,1]") <> "C" OR aTcx[nRecno,7] > 2
PRIVATE aTcx
DIMENSION aTcx[1,7]
nRecno = 1
SELECT row, col, blk, cnt(*) as cnt , MIN(num) as Num1, MAX(num) as num2 ;
FROM Comb GROUP BY 1, 2 HAVING COUNT(*) = 2 ORDER BY 4 INTO CURSOR y
IF _Tally = 0
SELECT row, col, blk, cnt(*) as cnt , MIN(num) as Num1, MAX(num) as num2 ;
FROM Comb GROUP BY 1, 2 HAVING COUNT(*) = 3 ORDER BY 4 INTO CURSOR y
ENDIF
nCnt = cnt
DO CASE
CASE _Tally = 0
? "Not solvable ..."
CASE ncnt = 2
SELECT *, Num2 as Num3 FROM y ;
UNION ALL ;
SELECT row, col, blk, cnt , Num1 as Num2, Num2 as Num1, Num2 as Num3 FROM y WHERE cnt = ncnt ;
INTO CURSOR x
OTHERWISE
SELECT y.row, y.col, y.blk, y.cnt , Num1, num2, MIN(Num) as Num3 ;
FROM Comb Z INNER JOIN Y ON z.row = y.row AND Y.col = z.col ;
WHERE NOT INLIST(num, Num1, Num2) ;
GROUP BY y.row, y.col ;
INTO CURSOR x
ENDCASE
IF _Tally > 0
SELECT x.row, x.col, x.blk, x.num1, x.num2, x.Num3, cnt, ;
GetMin(sum(IIF(x.blk = y.blk,1,0)), sum(IIF(x.row = y.row,1,0)), sum(IIF(x.col = y.col,1,0))), ;
sum(IIF(x.blk = y.blk,1,0)) + sum(IIF(x.row = y.row,1,0)) + sum(IIF(x.col = y.col,1,0)) ;
FROM x ;
INNER JOIN comb y ON num = num1 AND (x.row <> y.row OR x.col <> y.col) AND ;
(x.row = y.row OR x.col = y.col OR x.blk = y.blk) ;
GROUP BY 1,2,3,4 ;
ORDER BY 8, 9 ;
INTO ARRAY aTcX
ENDIF
ENDIF
IF TYPE("aTcx[nRecno,1]") = "C"
FOR nT = 1 TO aTcx[nRecno, 7]
REPLACE ALL Attempt WITH nAttempt+1 IN Comb
? GETWORDNUM("1ts 2nd 3rd", nT) + " try: "+atcx[nRecno,1]+", "+;
atcx[nRecno,2]+":= "+atcx[nRecno,3+nT]+": Level "+STR(nAttempt), nTotal
SetNumber(atcx[nRecno,1], atcx[nRecno,2], atcx[nRecno,3+nT])
nTotal = SolvePuzzle(nTotal, nAttempt+1, nRecno)
IF nTotal = 81
EXIT
ENDIF
RECALL ALL FOR Attempt > nAttempt IN Comb
nTotal = nTotSave
ACOPY(aRes2, aResult)
ENDFOR
ENDIF
ENDIF
ENDIF
*!* ? ntotal
*!* DO displaymap
*!* WAIT window
nX = nX + 1
ENDDO
RETURN nTotal
*-
FUNCTION setNumber (cRow, cCol, cNum)
** Store the found number and position
IF SEEK(cRow+cCol+cNum,"Comb","rowcolnum")
aResult[VAL(cRow), VAL(cCol)] = cNum
nTotal = nTotal + 1
** Delete combinations that are now that this number has been found.
cBlk = cNum + STR(INT((VAL(cCol)-1)/3)+1 + 3*INT((VAL(cRow)-1)/3),1)
DELETE FOR Row+Col = cRow+cCol OR Num+Col = cNum+cCol OR Num+Row = cNum+cRow OR Num+Blk = cBlk IN Comb
ENDIF
RETURN
*-
FUNCTION GetMin(n1, n2, n3)
nCalled = nCalled + 1
RETURN MIN(n1, n2, n3)
