Jump to content
jchd

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

Recommended Posts

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

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

  • Like 3

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
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 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
jchd

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


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
jchd

;-)

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
Chimp

@jchd, that query is really insane, :blink: 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 by Chimp
  • Like 1

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Share this post


Link to post
Share on other sites
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!


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
Chimp

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

#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

 

  • Like 2

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Share this post


Link to post
Share on other sites
jchd

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


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
Chimp

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.


small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Share this post


Link to post
Share on other sites
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.


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
farouk12
On 1/2/2018 at 4:02 PM, Chimp said:

@jchd, that query is really insane, :blink: 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

  • Like 1

Share this post


Link to post
Share on other sites
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 .

Share this post


Link to post
Share on other sites
Chimp
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 :)


small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Share this post


Link to post
Share on other sites
Chimp

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 (:blink: 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 by Chimp

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Share this post


Link to post
Share on other sites
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........

 

Share this post


Link to post
Share on other sites
Chimp

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


small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Share this post


Link to post
Share on other sites
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.


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
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 by farouk12
  • Like 2

Share this post


Link to post
Share on other sites
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 by farouk12

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

×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.