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

[jchd]

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).

expandcollapse popup

#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!

[jdelaney]

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 March 16, 2015 by jdelaney

[jchd]

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

How does this SQL-only version perform?

[jdelaney]

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.

[jchd]

;-)

I was talking about the SQL version above.

[Gianni]

@jchd, that query is really insane,  You are a crazy! ... (i'm joking btw )
Just a question please: what is the difficulty level of a sudoku determined from?
i.e: in what differs the initial states of "Easy" or "Hard" or "Hardest" ? ....
Thanks

Edited January 2, 2018 by Chimp

[jchd]

It isn't my SQL code, the author of the hard work is Edzard Pasma. I grabbed it from the SQLite mailing list and added the possibility to process more than one problem, then packaged the baby in an AutoIt wrapper with decently viewable output (provided it uses fixed-wiidth font).

The various entries Easy, Hard, ... are different inputs of increasing difficulty.

Feel free to change the samples and solve whatever Sudoku problem you want, but there is clearly zero step taken to check input for correct format or consistancy. I find it surprisingly fast compared to many compiled-code programs, even with the overhead of slow AutoIt code, SQLite DLL loading & init, parsing/byte-coding the lengthy SQL code by the RDBMS engine, run and AutoIt output formatting.

Recursive CTE support makes SQL Turing-complete, just like recursion and backtracking give PCRE regular expression that very same characteristic. Therefore your 2018 challenge is to solve several Sudokus problems with a single AutoIt regex. Have fun!

[Gianni]

I've done a very little modification. Changed only few lines to generate a new random puzzle on each run (don't know if it's an hard or simple puzle)
also changed the output so to be in plain ascii chars

expandcollapse popup

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

Local $hDB
_SQLite_Startup() ; _SQLite_Startup('.\sqlite3.dll")
$hDB = _SQLite_Open()

; an empty puzzle
Local $aSudokus[1][2] = [["Random", "                                                                                 "]]

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

; generate a sequence of numbers 1 to 9 in a random order using an SQL query
Local $aRandom, $sSQL_Query = "WITH RECURSIVE cnt(x) AS (SELECT 1 UNION ALL SELECT x+1 FROM cnt LIMIT 9) SELECT x FROM cnt ORDER BY random();"
_SQLite_GetTable(-1, $sSQL_Query, $aRandom, $iRows, $iCols)

; generate a random sudoku puzzle
For $i = 0 To 8
    $aSudokus[0][1] = StringReplace($aSudokus[0][1], $i * 9 + Random(1,9,1) , $aRandom[$i + 2], 1)
Next

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 " & _
            ") " & _
            "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;"

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))
    ConsoleWrite($s)
EndFunc

 

[jchd]

I wonder how you can generate a solvable random Sudoku, satisfying all the rules.

[Gianni]

I generate a sequence of numbers from 1 to 9 in a random order and then I spread those numbers on the grid in a random position (only one for each row). In this way there is no possibility to have 2 same numbers aligned on a row or on a column or in a 3x3 square. Also, even if all numbers falls in one single column or row or in a 3x3 square, since they are all different the rule should not be broken.
I think that in this way only very basic puzzles are generated, anyway this is just a funny experimenting.

[jchd]

That's what I understood. The problems created this way have an awfully large number of solutions then!
Once again I'm responsible for diverting this thread from it's original subject. Sorry about that folks.

[farouk12]

On 1/2/2018 at 4:02 PM, Chimp said:

@jchd, that query is really insane,  You are a crazy! ... (i'm joking btw )
Just a question please: what is the difficulty level of a sudoku determined from?
i.e: in what differs the initial states of "Easy" or "Hard" or "Hardest" ? ....
Thanks

You will find the answer in this pdf (With all Information about making Sudoku) .

Sudoku.pdf

[farouk12]

On 1/3/2018 at 0:52 AM, Chimp said:

I generate a sequence of numbers from 1 to 9 in a random order and then I spread those numbers on the grid in a random position (only one for each row). In this way there is no possibility to have 2 same numbers aligned on a row or on a column or in a 3x3 square. Also, even if all numbers falls in one single column or row or in a 3x3 square, since they are all different the rule should not be broken.
I think that in this way only very basic puzzles are generated, anyway this is just a funny experimenting.

In this way you will get Sudoku with many many many solutions .

[Gianni]

7 hours ago, farouk12 said:

You will find the answer in this pdf (With all Information about making Sudoku) .

Sudoku.pdf

thanks for the link

[Gianni]

On this page of SQLite documentation related to the "WITH" clause (http://www.sqlite.org/lang_with.html) I found a less complex version of the SQL query that solves the sudoku puzzles.
this version has the advantage of returning all the solutions it finds for the given puzzle.
in this way it is possible to check if a puzzle has none, just one or more solutions. (element 0 of the array contains 1 for no solution 2 for only one solution or N-1 for multiple solutions All the solutions that have been found are included in the array)
since I am not even remotely able to understand this query ( for now), I simply limit myself to making a copy paste with a minimum of adaptation to this script. However I think it can be useful as a basis for Sudoku puzzle generation / resolution programs.

the puzzle included in the listing has only one solution

#include <SQLite.au3>
#include <array.au3>
Local $hDB, $aRows, $iRows, $iCols
_SQLite_Startup(".\sqlite3.dll")
$hDB = _SQLite_Open()
Local $sSudoku_sql = "WITH RECURSIVE" & _
        "  input(sud) AS (" & _
        "    VALUES('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')" & _
        "  )," & _
        "  digits(z, lp) AS (" & _
        "    VALUES('1', 1)" & _
        "    UNION ALL SELECT" & _
        "    CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9" & _
        "  )," & _
        "  x(s, ind) AS (" & _
        "    SELECT sud, instr(sud, '.') FROM input" & _
        "    UNION ALL" & _
        "    SELECT" & _
        "      substr(s, 1, ind-1) || z || substr(s, ind+1)," & _
        "      instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )" & _
        "     FROM x, digits AS z" & _
        "    WHERE ind>0" & _
        "      AND NOT EXISTS (" & _
        "            SELECT 1" & _
        "              FROM digits AS lp" & _
        "             WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)" & _
        "                OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)" & _
        "                OR z.z = substr(s, (((ind-1)/3) % 3) * 3" & _
        "                        + ((ind-1)/27) * 27 + lp" & _
        "                        + ((lp-1) / 3) * 6, 1)" & _
        "         )" & _
        "  )" & _
        "SELECT s FROM x WHERE ind=0;"
_SQLite_GetTable($hDB, $sSudoku_sql, $aRows, $iRows, $iCols)
_ArrayDisplay($aRows)

 

Edited January 5, 2018 by Chimp

[farouk12]

3 minutes ago, Chimp said:

On this page of SQLite documentation related to the "WITH" clause (http://www.sqlite.org/lang_with.html) I found a less complex version of

here is difficult one, the topic one solve it in more than 50 sec but yours couldn't solve it at all

.61..7..3.92..3..............853..........5.45....8....4......1...16.8..6........

 

[Gianni]

@farouk12 your puzzle has been under elaboration by the query for several minutes, but at the end it has found the only one solution. So, it's slow but it works.

@jchd, please, if you allow, I have a request, how could be modified the first post query so to have, none or all the found solutions instead of only one of the possible solutions? thanks.

[jchd]

@Chimp, this is impossible using the Peter Norvig algorithm as implemented since it's built for finding the first solution of a puzzle.
"Normal" Sudoku puzzles only have a unique solution, like all those published in revues.

[farouk12]

3 hours ago, Chimp said:

@farouk12 your puzzle has been under elaboration by the query for several minutes, but at the end it has found the only one solution. So, it's slow but it works.

that sad because its take less then 5 sec with backtracking algorithm built in autoit

SudokuSolver.au3

Edited January 6, 2018 by farouk12

[farouk12]

3 hours ago, Chimp said:

all the found solutions instead of only one of the possible solutions

that can be with backtracking but that will take a bit of time.

Edited January 6, 2018 by farouk12