jchd

Fast Sudoku solver (insane) in pure SQL[ite]

5 posts in this topic

Slightly adapted from a clever SQLite solution by Edzard Pasma and uses Peter Norvig's method. Requires a recent version of the SQLite3 DLL since it uses recursive CTEs (Common Table Expression).

Norvig's algorithm goes like this:

--   . from given Sudoku problem, generate an array with each cell of the
       sudoku being a string with all remaining possibilites
--   . define as "neighbors" of a cell, all cells which must not have the
       same piece as this cells, (there are 20 neighbors to each cell)
--   . then analyse the cell (the string) have the less remaining
       solutions, but more than 1,
--        .. for a given sudoku position, "play" only on the first cell you
              found with the less possibilities, and try each of them,
--           ... replace in this cell the string by the possible piece you
                  want to try,
--           ... remove the piece you played from the neighbors cells own
                 possibilities (as it's no more a possibility for them)
--           ... when removing a possibility to a neighbor, if it leave
                  him only on possibility, "play" it immediately,
--           ... if you remove all the solutions from a neighbor, than
                 you're not on the sudoku solution path, stop this track.

Run this from Scite in UTF-8 (Unicode characters inside) and use a fixed-pitch font for console display. I'm too lazy at time of posting to make a nice GUI for it (MsgBox uses a proportional font which renders the output unreadable).

#include <SQLite.au3>
;~ #include <SQLite.dll.au3>    ; download the most recent suitable DLL once and comment this out

Local $hDB

Local $aSudokus[6][2] = [ _
    ["Easy",          "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79"], _
    ["Sqlite",        "1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3.."], _
    ["Hard",          ".....6....59.....82....8....45........3........6..3.54...325..6.................."], _
    ["Hola",          "4.2....3.1..6.5.299.....1......42....8.9.1.5....85......3.....861.5.4..2.4....5.7"], _
    ["Hardest",       "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.."], _
    ["EasterMonster", "1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1"] _
]

_SQLite_Startup()

$hDB = _SQLite_Open()
Local $sTempCreate = "" & _
"create temporary table i (" & _
    "i integer primary key, " & _
    "name char, " & _
    "word0, " & _
    "word1, " & _
    "peers0, " & _
    "peers1)" & _
";" & _
"insert into i " & _
    "select i, " & _
        "char(65+y)||(x+1) as name, " & _
        "case when iword=0 then 1<<ibit else 0 end AS word0, " & _
        "case when iword=1 then 1<<ibit else 0 end AS word1, " & _
        "CASE WHEN iword=0 THEN (512-1)<<(y*9) ELSE 0 END | " & _
            "((1+512*(1+512*(1+512*(1+512*(1+512)))))<<x) | " & _
            "CASE WHEN iword=0 THEN ((8-1)*(1+512*(1+512)))<<(y/3*3*9+x/3*3) ELSE 0 END AS peers0, " & _
        "CASE WHEN iword=1 THEN (512-1)<<((y%6)*9) ELSE 0 END | " & _
            "((1 + 512 * (1 + 512)) << x) | " & _
            "CASE WHEN iword=1 THEN ((8-1)*(1+512*(1+512)))<<((y%6)/3*3*9+x/3*3) ELSE 0 END AS peers1 " & _
    "from (" & _
        "with xy AS (SELECT 0 AS xy UNION ALL SELECT xy+1 FROM xy WHERE xy < 80) " & _
        "select  xy+1 AS i, " & _
                "xy%9 AS x, " & _
                "xy/9 AS y, " & _
                "xy/54 AS iword, " & _
                "xy%54 AS ibit " & _
        "from xy" & _
    ")" & _
";"

_SQLite_Exec($hDB, $sTempCreate)

Local $sInsaneSolver = "" & _
"with   z AS (SELECT 1 AS z UNION ALL SELECT z+1 FROM z WHERE z < 9), " & _
        "input as (" & _
            "select  input, " & _
                    "sud, " & _
                    "ifnull (sum (word0), 0) as w0, " & _
                    "ifnull (sum (word1), 0) as w1, " & _
                    "ifnull (sum (case when z=1 then word0 end), 0) as w10, " & _
                    "ifnull (sum (case when z=1 then word1 end), 0) as w11, " & _
                    "ifnull (sum (case when z=2 then word0 end), 0) as w20, " & _
                    "ifnull (sum (case when z=2 then word1 end), 0) as w21, " & _
                    "ifnull (sum (case when z=3 then word0 end), 0) as w30, " & _
                    "ifnull (sum (case when z=3 then word1 end), 0) as w31, " & _
                    "ifnull (sum (case when z=4 then word0 end), 0) as w40, " & _
                    "ifnull (sum (case when z=4 then word1 end), 0) as w41, " & _
                    "ifnull (sum (case when z=5 then word0 end), 0) as w50, " & _
                    "ifnull (sum (case when z=5 then word1 end), 0) as w51, " & _
                    "ifnull (sum (case when z=6 then word0 end), 0) as w60, " & _
                    "ifnull (sum (case when z=6 then word1 end), 0) as w61, " & _
                    "ifnull (sum (case when z=7 then word0 end), 0) as w70, " & _
                    "ifnull (sum (case when z=7 then word1 end), 0) as w71, " & _
                    "ifnull (sum (case when z=8 then word0 end), 0) as w80, " & _
                    "ifnull (sum (case when z=8 then word1 end), 0) as w81, " & _
                    "ifnull (sum (case when z=9 then word0 end), 0) as w90, " & _
                    "ifnull (sum (case when z=9 then word1 end), 0) as w91, " & _
                    "count (*) as fixed, " & _
                    "ifnull (sum (z=1), 0) as f1, " & _
                    "ifnull (sum (z=2), 0) as f2, " & _
                    "ifnull (sum (z=3), 0) as f3, " & _
                    "ifnull (sum (z=4), 0) as f4, " & _
                    "ifnull (sum (z=5), 0) as f5, " & _
                    "ifnull (sum (z=6), 0) as f6, " & _
                    "ifnull (sum (z=7), 0) as f7, " & _
                    "ifnull (sum (z=8), 0) as f8, " & _
                    "ifnull (sum (z=9), 0) as f9 " & _
            "from ( " & _
                "select '" & $aSudokus[0][0] & "' as input, " & _
                "'" & $aSudokus[0][1] & "' as sud " & _
            "union all " & _
                "select '" & $aSudokus[1][0] & "', " & _
                "'" & $aSudokus[1][1] & "' " & _
            "union all " & _
                "select '" & $aSudokus[2][0] & "', " & _
                "'" & $aSudokus[2][1] & "' " & _
            "union all " & _
                "select '" & $aSudokus[3][0] & "', " & _
                "'" & $aSudokus[3][1] & "' " & _
            "union all " & _
                "select '" & $aSudokus[4][0] & "', " & _
                "'" & $aSudokus[4][1] & "' " & _
            "union all " & _
                "select '" & $aSudokus[5][0] & "', " & _
                "'" & $aSudokus[5][1] & "' " & _
            ") " & _
            "join i " & _
            "join z on z = cast (substr (sud, i.i, 1) as int) " & _
            "where input='#####' " & _
        ") " & _
", " & _
"sudoku as (" & _
    "select " & _
        "'' as text, " & _
        "fixed, " & _
        "f1,f2,f3,f4,f5,f6,f7,f8,f9, " & _
        "0 as zfixed, " & _
        "0 as i0, " & _
        "w0, w1, " & _
        "w10, w11, " & _
        "w20, w21, " & _
        "w30, w31, " & _
        "w40, w41, " & _
        "w50, w51, " & _
        "w60, w61, " & _
        "w70, w71, " & _
        "w80, w81, " & _
        "w90, w91 " & _
    "from input " & _
    "union all " & _
    "select " & _
        "(fixed+1)||','|| " & _
            "name||','|| " & _
            "( " & _
                "(w10&peers0 or w11&peers1) + " & _
                "(w20&peers0 or w21&peers1) + " & _
                "(w30&peers0 or w31&peers1) + " & _
                "(w40&peers0 or w41&peers1) + " & _
                "(w50&peers0 or w51&peers1) + " & _
                "(w60&peers0 or w61&peers1) + " & _
                "(w70&peers0 or w71&peers1) + " & _
                "(w80&peers0 or w81&peers1) + " & _
                "(w90&peers0 or w91&peers1) " & _
            ") ||','|| " & _
            "z||','|| " & _
            "'', " & _
        "fixed+1, " & _
        "f1+(z=1), " & _
        "f2+(z=2), " & _
        "f3+(z=3), " & _
        "f4+(z=4), " & _
        "f5+(z=5), " & _
        "f6+(z=6), " & _
        "f7+(z=7), " & _
        "f8+(z=8), " & _
        "f9+(z=9), " & _
        "case z " & _
            "when 1 then f1 " & _
            "when 2 then f2 " & _
            "when 3 then f3 " & _
            "when 4 then f4 " & _
            "when 5 then f5 " & _
            "when 6 then f6 " & _
            "when 7 then f7 " & _
            "when 8 then f8 " & _
            "when 9 then f9 " & _
        "end, " & _
        "i.i, " & _
        "w0+word0, " & _
        "w1+word1, " & _
        "case when z=1 then w10+word0 else w10 end, " & _
        "case when z=1 then w11+word1 else w11 end, " & _
        "case when z=2 then w20+word0 else w20 end, " & _
        "case when z=2 then w21+word1 else w21 end, " & _
        "case when z=3 then w30+word0 else w30 end, " & _
        "case when z=3 then w31+word1 else w31 end, " & _
        "case when z=4 then w40+word0 else w40 end, " & _
        "case when z=4 then w41+word1 else w41 end, " & _
        "case when z=5 then w50+word0 else w50 end, " & _
        "case when z=5 then w51+word1 else w51 end, " & _
        "case when z=6 then w60+word0 else w60 end, " & _
        "case when z=6 then w61+word1 else w61 end, " & _
        "case when z=7 then w70+word0 else w70 end, " & _
        "case when z=7 then w71+word1 else w71 end, " & _
        "case when z=8 then w80+word0 else w80 end, " & _
        "case when z=8 then w81+word1 else w81 end, " & _
        "case when z=9 then w90+word0 else w90 end, " & _
        "case when z=9 then w91+word1 else w91 end " & _
    "from sudoku " & _
    "join i " & _
        "on i = ifnull ( " & _
                            "( " & _
                                "select  i " & _
                                "from    i " & _
                                "where   i > i0 " & _
                                    "and     not (word0&w0 or word1&w1) " & _
                                    "and     ( " & _
                                                "(w10&peers0 or w11&peers1) + " & _
                                                "(w20&peers0 or w21&peers1) + " & _
                                                "(w30&peers0 or w31&peers1) + " & _
                                                "(w40&peers0 or w41&peers1) + " & _
                                                "(w50&peers0 or w51&peers1) + " & _
                                                "(w60&peers0 or w61&peers1) + " & _
                                                "(w70&peers0 or w71&peers1) + " & _
                                                "(w80&peers0 or w81&peers1) + " & _
                                                "(w90&peers0 or w91&peers1) " & _
                                            ") = 8 " & _
                                "limit 1 " & _
                            ") " & _
                            ", " & _
                            "( " & _
                                "select  i " & _
                                "from    ( " & _
                                    "select  i, " & _
                                            "max ( " & _
                                                    "(w10&peers0 or w11&peers1) + " & _
                                                    "(w20&peers0 or w21&peers1) + " & _
                                                    "(w30&peers0 or w31&peers1) + " & _
                                                    "(w40&peers0 or w41&peers1) + " & _
                                                    "(w50&peers0 or w51&peers1) + " & _
                                                    "(w60&peers0 or w61&peers1) + " & _
                                                    "(w70&peers0 or w71&peers1) + " & _
                                                    "(w80&peers0 or w81&peers1) + " & _
                                                    "(w90&peers0 or w91&peers1) " & _
                                            ") as maxfixed " & _
                                    "from    i " & _
                                    "where   not (word0&w0 or word1&w1) " & _
                                ") " & _
                                "where     maxfixed is not null " & _
                        ")) " & _
    "join    z " & _
    "on " & _
        "case z " & _
            "when 1 then not (w10&peers0 or w11&peers1) " & _
            "when 2 then not (w20&peers0 or w21&peers1) " & _
            "when 3 then not (w30&peers0 or w31&peers1) " & _
            "when 4 then not (w40&peers0 or w41&peers1) " & _
            "when 5 then not (w50&peers0 or w51&peers1) " & _
            "when 6 then not (w60&peers0 or w61&peers1) " & _
            "when 7 then not (w70&peers0 or w71&peers1) " & _
            "when 8 then not (w80&peers0 or w81&peers1) " & _
            "when 9 then not (w90&peers0 or w91&peers1) " & _
        "end " & _
    "order by fixed desc, " & _
            "zfixed desc " & _
") " & _
", " & _
"output as ( " & _
    "select  * " & _
    "from    ( " & _
        "select  1 as i, " & _
                "w10, w11, " & _
                "w20, w21, " & _
                "w30, w31, " & _
                "w40, w41, " & _
                "w50, w51, " & _
                "w60, w61, " & _
                "w70, w71, " & _
                "w80, w81, " & _
                "w90, w91, " & _
                "'' as sud " & _
        "from    sudoku " & _
        "where   fixed = 81 limit 1 " & _
    ") " & _
    "union all " & _
    "select  nullif (output.i + 1, 82), " & _
            "w10, w11, " & _
            "w20, w21, " & _
            "w30, w31, " & _
            "w40, w41, " & _
            "w50, w51, " & _
            "w60, w61, " & _
            "w70, w71, " & _
            "w80, w81, " & _
            "w90, w91, " & _
            "sud || replace (cast ( " & _
                "case 1 " & _
                "when w10&word0 OR w11&word1 then 1 " & _
                "when w20&word0 OR w21&word1 then 2 " & _
                "when w30&word0 OR w31&word1 then 3 " & _
                "when w40&word0 OR w41&word1 then 4 " & _
                "when w50&word0 OR w51&word1 then 5 " & _
                "when w60&word0 OR w61&word1 then 6 " & _
                "when w70&word0 OR w71&word1 then 7 " & _
                "when w80&word0 OR w81&word1 then 8 " & _
                "when w90&word0 OR w91&word1 then 9 " & _
                "else 0 " & _
                "end " & _
                "as char), '0', '.') " & _
    "from    output " & _
    "join    i on i.i = output.i " & _
") " & _
", " & _
"result as (select sud s from input union all select sud from output WHERE i is null) " & _
"SELECT " & _
       "'┏━┯━┯━┳━┯━┯━┳━┯━┯━┓' || x'0d0a' || " & _
       "'┃' || substr(s, 1,1) || '│' || substr(s, 2,1) || '│' || substr(s, 3,1) || '┃' || " & _
              "substr(s, 4,1) || '│' || substr(s, 5,1) || '│' || substr(s, 6,1) || '┃' || " & _
              "substr(s, 7,1) || '│' || substr(s, 8,1) || '│' || substr(s, 9,1) || '┃' || x'0d0a' || " & _
       "'┠┄┼┄┼┄╂┄┼┄┼┄╂┄┼┄┼┄┨' || x'0d0a' || " & _
       "'┃' || substr(s,10,1) || '│' || substr(s,11,1) || '│' || substr(s,12,1) || '┃' || " & _
              "substr(s,13,1) || '│' || substr(s,14,1) || '│' || substr(s,15,1) || '┃' || " & _
              "substr(s,16,1) || '│' || substr(s,17,1) || '│' || substr(s,18,1) || '┃' || x'0d0a' || " & _
       "'┠┄┼┄┼┄╂┄┼┄┼┄╂┄┼┄┼┄┨' || x'0d0a' || " & _
       "'┃' || substr(s,19,1) || '│' || substr(s,20,1) || '│' || substr(s,21,1) || '┃' || " & _
              "substr(s,22,1) || '│' || substr(s,23,1) || '│' || substr(s,24,1) || '┃' || " & _
              "substr(s,25,1) || '│' || substr(s,26,1) || '│' || substr(s,27,1) || '┃' || x'0d0a' || " & _
       "'┣━┿━┿━╋━┿━┿━╋━┿━┿━┫' || x'0d0a' || " & _
       "'┃' || substr(s,28,1) || '│' || substr(s,29,1) || '│' || substr(s,30,1) || '┃' || " & _
              "substr(s,31,1) || '│' || substr(s,32,1) || '│' || substr(s,33,1) || '┃' || " & _
              "substr(s,34,1) || '│' || substr(s,35,1) || '│' || substr(s,36,1) || '┃' || x'0d0a' || " & _
       "'┠┄┼┄┼┄╂┄┼┄┼┄╂┄┼┄┼┄┨' || x'0d0a' || " & _
       "'┃' || substr(s,37,1) || '│' || substr(s,38,1) || '│' || substr(s,39,1) || '┃' || " & _
              "substr(s,40,1) || '│' || substr(s,41,1) || '│' || substr(s,42,1) || '┃' || " & _
              "substr(s,43,1) || '│' || substr(s,44,1) || '│' || substr(s,45,1) || '┃' || x'0d0a' || " & _
       "'┠┄┼┄┼┄╂┄┼┄┼┄╂┄┼┄┼┄┨' || x'0d0a' || " & _
       "'┃' || substr(s,46,1) || '│' || substr(s,47,1) || '│' || substr(s,48,1) || '┃' || " & _
              "substr(s,49,1) || '│' || substr(s,50,1) || '│' || substr(s,51,1) || '┃' || " & _
              "substr(s,52,1) || '│' || substr(s,53,1) || '│' || substr(s,54,1) || '┃' || x'0d0a' || " & _
       "'┣━┿━┿━╋━┿━┿━╋━┿━┿━┫' || x'0d0a' || " & _
       "'┃' || substr(s,55,1) || '│' || substr(s,56,1) || '│' || substr(s,57,1) || '┃' || " & _
              "substr(s,58,1) || '│' || substr(s,59,1) || '│' || substr(s,60,1) || '┃' || " & _
              "substr(s,61,1) || '│' || substr(s,62,1) || '│' || substr(s,63,1) || '┃' || x'0d0a' || " & _
       "'┠┄┼┄┼┄╂┄┼┄┼┄╂┄┼┄┼┄┨' || x'0d0a' || " & _
       "'┃' || substr(s,64,1) || '│' || substr(s,65,1) || '│' || substr(s,66,1) || '┃' || " & _
              "substr(s,67,1) || '│' || substr(s,68,1) || '│' || substr(s,69,1) || '┃' || " & _
              "substr(s,70,1) || '│' || substr(s,71,1) || '│' || substr(s,72,1) || '┃' || x'0d0a' || " & _
       "'┠┄┼┄┼┄╂┄┼┄┼┄╂┄┼┄┼┄┨' || x'0d0a' || " & _
       "'┃' || substr(s,73,1) || '│' || substr(s,74,1) || '│' || substr(s,75,1) || '┃' || " & _
              "substr(s,76,1) || '│' || substr(s,77,1) || '│' || substr(s,78,1) || '┃' || " & _
              "substr(s,79,1) || '│' || substr(s,80,1) || '│' || substr(s,81,1) || '┃' || x'0d0a' || " & _
       "'┗━┷━┷━┻━┷━┷━┻━┷━┷━┛'" & _
"FROM result;"

Local $aRows, $iRows, $iCols
Local $sProblem

For $n = 0 To UBound($aSudokus) - 1
    $sProblem = StringReplace($sInsaneSolver, "#####", $aSudokus[$n][0])
    _SQLite_GetTable($hDB, $sProblem, $aRows,$iRows, $iCols)
    _ConsoleWrite($aSudokus[$n][0] & " problem" & @LF & $aRows[2] & @LF & @LF)
    _ConsoleWrite($aSudokus[$n][0] & " solution" & @LF & $aRows[3] & @LF & @LF)
Next

Func _ConsoleWrite($s)
    ConsoleWrite(BinaryToString(StringToBinary($s, 4), 1))
EndFunc

Serious warning: the SQL involved is NOT for heartfainted people. You've been warned!


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

I made one of these also :).  Then I used it to solve a website Sudoku, and continually populate winning answers in a cycle on the hardest setting.  Mine logically finds 100% answers, then performs a guess recursively, until it's all solved.

This is the one without the web-crawling and population.

Edited by jdelaney

IEbyXPATH-Grab IE DOM objects by XPATH IEscriptRecord-Makings of an IE script recorder ExcelFromXML-Create Excel docs without excel installed GetAllWindowControls-Output all control data on a given window.

Share this post


Link to post
Share on other sites

This version uses bitmaps to keep track of allowable values of cells and neighbours.

How does this SQL-only version perform?


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

No, there are no bitmaps...I'm just updating a gui with what is being done within the code...a visual of what's being performed.  I also think it looks cool.


IEbyXPATH-Grab IE DOM objects by XPATH IEscriptRecord-Makings of an IE script recorder ExcelFromXML-Create Excel docs without excel installed GetAllWindowControls-Output all control data on a given window.

Share this post


Link to post
Share on other sites

;-)

I was talking about the SQL version above.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now