Sign in to follow this  
Followers 0
samba7

Challenge puzzle!

10 posts in this topic

Hell-o guys,

I am trying to solve a numerical puzzle needed for my small autoit game to work, but 300 lines of code later, I give up!!!

So I am posting it here as a challenge for any brave free member who enjoys discombobulating problems. Who knows, maybe there is a faster more efficient way to do it.

Puzzle:

http://imageshack.us/photo/my-images/59/gameefu.jpg/

Here we see a 2darray with 10 row and columns, each index in the 2darray contains a string of two digits separated by a comma. The target is to find 10 different strings in ten different columns (1 in each column) together constitute from 1 to 40 and extract those 10 strings. Keep in mind that the strings change each execution and that the strings should remain in the same order.

i.e.

$2darr[0][0] = 7,16,18,35 ;ok, still need [1,2,3,4,5,6,8,9,10,11,12,13,14,15,17,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,37,38,39,40] for 40

$2darr[0][1] = 5,9,10,12,19,24,31 ;ok, need [1,2,3,4,6,8,11,13,14,15,17,20,21,22,23,25,26,27,28,29,30,32,33,34,36,37,38,39,40] for 40

$2darr[0][2] = 16,17,24,38 ; wrong, 16 exists in 2darr[0][0], try different path

$2darr[1][2] = etc…

It looks simple but Enjoy!! :D

Share this post


Link to post
Share on other sites



Provide an AutoIt text representation of some of the problems array and I'll solve them easily and efficiently.


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

im at work right now, when im home ill provide it.

thanks :D

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

Challenge accepted!

Global $2darr[10][10]
ConsoleWrite("The following cells will form a valid set (from col0, to col9):" & @CRLF)
For $iCol = 0 To 9
    For $iRow = 0 To 9
        For $iNum = 0 To Random(0,6,1)
            $2darr[$iRow][$iCol] &= Random(1,40,1) & ","
        Next
        $2darr[$iRow][$iCol] &= Random(1,40,1)
    Next
    $iRnd = Random(0,9,1)
    ConsoleWrite($iRnd & ",")
    $2darr[$iRnd][$iCol] = ($iCol*4)+1 & "," & ($iCol*4)+2 & "," & ($iCol*4)+3 & "," & ($iCol*4)+4 ;ensure there is a valid combo
Next
ConsoleWrite(@CRLF & "Preparations done..." & @CRLF & @CRLF)


ConsoleWrite("Result of function:" & _Search_Rec(0, "") & @CRLF)
Func _Search_Rec($iCol, $sNumbers)
    $aiList = StringSplit($sNumbers, ",") ;make an array of the numbers we have so far (keep in mind cell1 will always be empty)
    If ($iCol < 9) And ($aiList = 41) Then Return -1 ;if we have all 40 numbers bevore collumn9, we're on the wrong track
    For $iRow = 0 To 9 ;loop through all rows of the current collumn
        For $iNum = 2 To $aiList[0] ;check for a number we already have
            If StringInStr("," & $2darr[$iRow][$iCol] & ",", "," & $aiList[$iNum] & ",") Then ContinueLoop 2 ;skip if duplicate number is found
        Next
        If $iCol = 9 Then ;this looks promising
            $aiList = StringSplit($sNumbers & "," & $2darr[$iRow][$iCol], ",") ;check how many unique numbers we have.
            If $aiList[0] = 41 Then Return $iRow ;success!
        Else
            $sReturn = _Search_Rec($iCol + 1, $sNumbers & "," & $2darr[$iRow][$iCol]) ;next collumn
            If $sReturn <> -1 Then Return $iRow & "," & $sReturn ;return the row included in a successfull group.
        EndIf
    Next
    Return -1
EndFunc

I just got tricked into writing someones code for him, didn't I? Well played sir!

Off to bed.

Edit: Quick fix. It would not accept sets including $2darr[0][9], because I used Return 0 to indicate an incorrect combo before. Changed it to Return -1 now.

Let the speed improvements and line count reductions commence! (it typically takes <1sec to complete, but a worst case scenario could easily take longer than an hour)

Edited by Tvern

Share this post


Link to post
Share on other sites

Hello again and sorry guys for late reply, it was a hectic day at work and when i arrived home i was so tired that f5

engraved a cool tattoo on my forehead.

Jchd, below is a text file with the challenge array, you can read it to 2darray with _filereadtoarray delim '|'.

2darray1.txt

Tvern, you were not tricked because i am not playing games here. if you want ill post my 300 lines script attempt, but its embracing so i wont. think of this as charity for a poor programmer :D

ill compensate your efforts by donating to autoit, been wanting to do that for a while, yet again i wish there was another way than paypal bec. its not accepted in my country. ill find a way ^^

testing your script now.

Share this post


Link to post
Share on other sites

The problem posted doesn't seem to have a solution, at least not within the specifications you posted (one cell selected in _every_ column). My brute-force algorithm is identical to what Tvern posted, just almost twice as fast thanks to a bitmap representation of integers subsets. I'm contemplating a completely different algorithm but I still wonder if it can be made faster.

; This comes from an UDF I've posted to allow for 64-bit bitwise operations (plus 64_bit Div, Mod and others)
Local $AddOnDllPath = "addons.dll"
Local $AddOnDll = DllOpen($AddOnDllPath)
; problem array
Local $aPb[10][10] = [ _
["7,16,18,35",          "5,9,10,12,19,24,31", "16,17,24,38",         "7,21,30,34,37",   "8,25,28",         "21",                  "4,8",                "1,8,10,25",      "16,33",                     "14,19,20,22,27"   ], _
["8",                    "28,37,38,40",     "6,23,27",           "3,16,25,29",     "17,27,29,38",      "7,32",              "13,32",              "28,32",        "3,4,38,39",                 "2,7,9,23"        ], _
["4,6,15,21,23,27,31,40", "1,16,17,23,30",    "2,10,21,31,32,37,40", "2,8,10,14,27",     "3",                "4,22,25,27,29,30,38", "1,18,39",          "3,9,15,16",      "1,7,11,15,17,24,25,32,37,40", "3,8,15,30,40"  ], _
["10,22,25,29,30,33,36",  "18,26,35",          "9,26",              "4,19,32,35",      "32,40",          "1,10,11,17,31",      "5,10,11,21,30",   "2,4,6,23,33,36", "9,22,36",                   "13,18,29,31,32"   ], _
["9",                    "2,6,36",           "1,5,8,28,34",      "5,17,20,22,23,31", "2,4,10,11,31",      "3,12,13,24,33",     "9,25,36",           "12,24,29,40",  "10,35",                       "34,38"          ], _
["14,32,34",              "11,20",            "11,12,13,30",         "6,12,24,36,38",   "1,5,13,18,19,35",   "15,36,37,39",      "17,33,34,37",     "7,14,31,35",    "2,18,34",                  "10,16,25,26,37,39"], _
["3,20,24,38",          "7,29,32,33",        "3,14,15,35,39",      "15,18",         "12,14,15,22,23,39", "8,16,34,35",        "3,7,12,15,16,20,22", "5,17,26,27",    "19,26,28,31",              "11,12,17,28"    ], _
["1,5,26",              "8,15",            "18,22,36",          "11",              "6,7,9,16,26,36",    "2,5,9,18,20",       "2,14,28,29,38",     "18,20,21,30",    "6,14,23,27,29",               "6,24"            ], _
["12,13,17,19,37",      "3,4,14,22,27,34",  "4,7,19,20,25,33",   "13,26,40",         "20,21,33,34,37",  "19,23,28",         "19,26,27",        "22,38,39",     "5,8,12,13,20",              "4,21,33,36"       ], _
["2,11,28,39",          "13,21,25,39",      "29",                 "1,9,28,33,39",    "24,30",            "6,14,26,40",        "6,23,24,31,35,40",   "11,13,19,34,37", "21,30",                     "1,5,35"        ] _
]
Local $bMax = 2 ^ 40 - 1 ; 40-bit bitmap of the complete target interval of integers 1..40
; build a copy of the problem array containing integer values
; those integers are bit image of the set of numbers in the string inside each input cell
; e.g. input cell '1,3,6,11' is represented by integer 0000 0000 0000 0000 0000 0100 0010 0101, that is 0x00000425
Local $aBits[10][10], $bits
For $i = 0 To 9
For $j = 0 To 9
  $bits = 0
  Local $values = StringSplit($aPb[$i][$j], ',', 2)
  For $val In $values
   $bits = _BitOR($bits, 2 ^ ($val - 1))
  Next
  $aBits[$i][$j] = $bits
Next
Next

; from now on we work with bitmaps array, faster than string input format
Local $count = 1, $res, $sol = ''  ; will hold a string of row indices of the solution
; the challenge requires that one selects a set of numbers in every column
; we scan rows of the array in turn:
For $i = 0 To 9
; find the solution within the remaining columns
$res = _SubSolve($aBits[$i][0], 1)
If IsString($res) Then
  $sol = $i & $res
  ExitLoop
EndIf
Next
; Display solution
If $sol = '' Then
ConsoleWrite("The problem doesn't admit a solution" & @LF)
Else
ConsoleWrite("The solution is the union of rows " & $sol & " from columns 0..9 resp." & @LF)
ConsoleWrite("Only " & $count & " 9-column combinations tested out of the theoritical worst-case number (" & 10^10 & ")" & @LF)
EndIf

Func _SubSolve($bits, $col)
Local $bittest
For $i = 0 To 9
  ; check that the subset we are trying is compatible (no duplicates) with what is being tested
  If _BitAND($bits, $aBits[$i][$col]) Then
   ; at least one integer in the test column already exists in the set we've gathered
   ContinueLoop
  Else
   $bittest = _BitOR($bits, $aBits[$i][$col])
   If $col = 9 Then
    If $bittest = $bMax Then
     Return(', ' & $i)
    EndIf
   Else
    Local $test = _SubSolve($bittest, $col + 1)
    If IsString($test) Then
     Return(', ' & $i & $test)
    EndIf
   EndIf
  EndIf
Next
$count += 1
Return(0)
EndFunc

;; Integer divide for 64-bit signed integers
Func _Div($iNumerator, $iDenominator)
If $iDenominator = 0 Then Return(1 / 0) ;; make it behave like the built-in / operator
Local $ret = DllCall($AddOnDll, "int64:cdecl", "Div", "int64", $iNumerator, "int64", $iDenominator)
Return($ret[0])
EndFunc
;; Modulus for 64-bit signed integers
Func _Mod($iNumber, $iModulus)
If $iModulus = 0 Then Return(1 / 0) ;; make it behave like the built-in Mod() function
Local $ret = DllCall($AddOnDll, "int64:cdecl", "Mod", "int64", $iNumber, "int64", $iModulus)
Return($ret[0])
EndFunc
;; Bitwise AND on 64-bit integers
Func _BitAnd($uiA, $uiB)
Local $ret = DllCall($AddOnDll, "uint64:cdecl", "BitAnd", "uint64", $uiA, "uint64", $uiB)
Return($ret[0])
EndFunc
;; Bitwise OR on 64-bit integers
Func _BitOr($uiA, $uiB)
Local $ret = DllCall($AddOnDll, "uint64:cdecl", "BitOr", "uint64", $uiA, "uint64", $uiB)
Return($ret[0])
EndFunc
;; Bitwise XOR on 64-bit integers
Func _BitXor($uiA, $uiB)
Local $ret = DllCall($AddOnDll, "uint64:cdecl", "BitXor", "uint64", $uiA, "uint64", $uiB)
Return($ret[0])
EndFunc
;; Bitwise 1-complement on 64-bit signed integers
Func _BitNot($iA)
Return(-($iA + 1))
EndFunc
;~ ;; Bitwise 1-complement on 64-bit integers
;~ Func _BitNot($uiA)
;~  Local $ret = DllCall($AddOnDll, "uint64:cdecl", "BitNot", "uint64", $uiA)
;~  Return($ret[0])
;~ EndFunc
;; Arithmetic Shift (Right > 0, Left < 0) : signed shift on 64-bit signed integers
Func _SignBitShift($iA, $iB)
Local $ret = DllCall($AddOnDll, "int64:cdecl", "SignBitShift", "int64", $iA, "int", $iB)
Return($ret[0])
EndFunc
;; Logical Shift (Right > 0, Left < 0) : unsigned shift on 64-bit integers
Func _BitShift($uiA, $iB)
Local $ret = DllCall($AddOnDll, "uint64:cdecl", "BitShift", "uint64", $uiA, "int", $iB)
Return($ret[0])
EndFunc
;; Logical Rotate (Right > 0, Left < 0) : rotate on 64-bit integers
Func _BitRotate($uiA, $iB)
Local $ret = DllCall($AddOnDll, "uint64:cdecl", "BitRotate", "uint64", $uiA, "int", $iB)
Return($ret[0])
EndFunc
;; Hex string to 64-bit signed integer conversion
Func _HexToInt64($sHexStr)
If StringLeft($sHexStr, 2) = '0x' Then $sHexStr = StringTrimLeft($sHexStr, 2)
Local $len = StringLen($sHexStr)
If ($len > 16) Then
  Return(SetError(-2, 0, ''))  ;; don't know how to deal wih larger string
Else
  $sHexStr = StringLeft("0000000000000000", 16 - StringLen($sHexStr)) & $sHexStr
EndIf
Return( Execute("0x" & StringLeft($sHexStr, 6)) * 1099511627776 + _
   Execute("0x" & StringMid($sHexStr, 7, 6)) * 65536 + _
   Execute("0x" & StringRight($sHexStr, 4)))
EndFunc
;; 64-bit signed integer to Hex string conversion
Func _Int64ToHex($iNumber)
Return(Hex(_BitShift($iNumber, 32)) & Hex(_BitShift(_BitShift($iNumber, -32), 32)))
EndFunc

addons.dll


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

The problem posted doesn't seem to have a solution

this is not a surprise because i was not able to complete the "bruteforce" algo myself and test for errors.

the good news is i can debug now and thanks to tvern we all can generate a valid combo.

why cant i edit my post? it turns out i can donate with my cc, for some reason i thought i nedded a paypal account...

Share this post


Link to post
Share on other sites

Be warned that the problem space is relatively large (1010). Of course, duplicate values cut this down to a much smaller value but still, depending on the algorithm used it's possible to build a strong instance which will need a long time to solve (assuming there is a solution).

Maybe editing posts is restrained to new users. You probably need some more (useful) posts to jump over the limit.

AFAIK you can pay anything using Paypal without a Paypal account, just need an accepted credit/debit card.


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

That is a nice speed-up. I was thinking of preparing the array in a way that would make he comparison easier, but hadn't thought of something like this.

@Samba7: I was just kidding. I liked the challenge. It'd be fun if there was a puzzles sub forum here.

Share this post


Link to post
Share on other sites

#10 ·  Posted (edited)

I went back to the problem and here are my findings. First, the posted problem does have solutions, and even 10 solutions at least. Looking more closely to the values, you can see that each column _is_ a solution. This is certainly no miracle: the author built this example on purpose.

Anyway I found the problem an interesting challenge in its own right, given that with some hard instance it doesn't seem completely trivial to solve efficiently. I was thinking about a less brute force algorithm and indeed, the results are good enough to deserve posting.

I removed the "one cell in every column" specification and assumed that the solution could be any set of cells, whatever the number and position of cells.

This more general and much harder problem can still be solved more efficiently than brute-force. I used ... SQLite ... to store everything and make it the heart of my search engine. Those who have spent some time on the forum won't be surprised. I'm glad to exhibit a creative non-trivial application of SQLite in such context, which doesn't seem to call for a database layer at first glance.

The idea is to build only one single table containing, for every occurence, the integer, the cell position where it is, a "integer used" flag and a "cell used" flag, both flags defaulting to 0.

(I posted then removed a more complex setup using 3 tables, but it finally proved a bit slower than this version.)

I make use of recent features of both SQLite3 and the SQLite UDF, so you need to use the AutoIt beta to run the program. SQLite3.dll needs to be >= v3.7

I store cell positions [row, column] in a single integer = row * 10 + column. That's for efficiency.

Then the recursion starts: find the next "not used" integer in the table. Query a list of all cells where this integer shows, whose cells' content don't conflict with the set on integers accumulated so far. For each of these cells, get a list of the integers it contains and toggle the "not used" flags to "used" for the cell and all its integers. We then recurse to the Solve function itself until all integers are "used" (one solution found) or we have no more cell to try (no solution exists).

There is something important I didn't explain so far: how can recursion "go back" if we reach a local dead end at some point in the parse tree? We need some kind of stack to this effect. Once again a recent feature of SQLite solved this smartly: nested named transactions (savepoint feature) that we can start and either rollback or commit. Of course here, we only commit the whole transaction stack when a solution appears or none exists.

What's more? Few things, like efficient indices and everything wrapped in an outer, solid (non-nested) transaction. The code has provision to display what it's doing on the console and of course the result as well in two distinct formats (to show uses of group_concat).

What advantage does this approach give us? We dramatically limit the parse tree (hence the number of tries). That's because we only try "not used" cells that themselves contain integers that don't collide with the list of integers we have currently in the "used" state. This way, we don't test too many cells at each recursion level.

Of course SQLite (and its UDF) introduces significant overhead compared to more simple memory structures. But this is somehow balanced by the small size and low complexity of the code: less than 90 lines all in all, the Solve function being 20 active lines. I wonder if a pure AutoIt implementation relying only on arrays would win, because the most complex part of the selection/organization is pushed over to carefully optimized C SQLite code.

You can select to make the DB disk-based (look at the _SQLite_Open line) in order to look at the DB with a third-party SQLite manager like SQLite-Expert, my hands off winner.

Since we use transactions and the DB is so small, it all resides in cache(s). This explains why there's so little difference in runtime between the memory DB and its disk-based counterpart.

#include            ; requires the last AutoIt beta (v3.3.7.21) or later to work
;~ #include     ; I don't use this but up to you (change _SQLite_Startup then)
#include

; problem array
Local $aPb[10][10] = [ _
    ["7,16,18,35",          "5,9,10,12,19,24,31", "16,17,24,38",         "7,21,30,34,37",   "8,25,28",         "21",                  "4,8",                "1,8,10,25",      "16,33",                     "14,19,20,22,27"   ], _
    ["8",                    "28,37,38,40",     "6,23,27",           "3,16,25,29",     "17,27,29,38",      "7,32",              "13,32",              "28,32",        "3,4,38,39",                 "2,7,9,23"        ], _
    ["4,6,15,21,23,27,31,40", "1,16,17,23,30",    "2,10,21,31,32,37,40", "2,8,10,14,27",     "3",                "4,22,25,27,29,30,38", "1,18,39",          "3,9,15,16",      "1,7,11,15,17,24,25,32,37,40", "3,8,15,30,40"  ], _
    ["10,22,25,29,30,33,36",  "18,26,35",          "9,26",              "4,19,32,35",      "32,40",          "1,10,11,17,31",      "5,10,11,21,30",   "2,4,6,23,33,36", "9,22,36",                   "13,18,29,31,32"   ], _
    ["9",                    "2,6,36",           "1,5,8,28,34",      "5,17,20,22,23,31", "2,4,10,11,31",      "3,12,13,24,33",     "9,25,36",           "12,24,29,40",  "10,35",                       "34,38"          ], _
    ["14,32,34",              "11,20",            "11,12,13,30",         "6,12,24,36,38",   "1,5,13,18,19,35",   "15,36,37,39",      "17,33,34,37",     "7,14,31,35",    "2,18,34",                  "10,16,25,26,37,39"], _
    ["3,20,24,38",          "7,29,32,33",        "3,14,15,35,39",      "15,18",         "12,14,15,22,23,39", "8,16,34,35",        "3,7,12,15,16,20,22", "5,17,26,27",    "19,26,28,31",              "11,12,17,28"    ], _
    ["1,5,26",              "8,15",            "18,22,36",          "11",              "6,7,9,16,26,36",    "2,5,9,18,20",       "2,14,28,29,38",     "18,20,21,30",    "6,14,23,27,29",               "6,24"            ], _
    ["12,13,17,19,37",      "3,4,14,22,27,34",  "4,7,19,20,25,33",   "13,26,40",         "20,21,33,34,37",  "19,23,28",         "19,26,27",        "22,38,39",     "5,8,12,13,20",              "4,21,33,36"       ], _
    ["2,11,28,39",          "13,21,25,39",      "29",                 "1,9,28,33,39",    "24,30",            "6,14,26,40",        "6,23,24,31,35,40",   "11,13,19,34,37", "21,30",                     "1,5,35"        ] _
]

_SQLite_Startup("..binsqlite3.dll", True, 1)        ; (adapt the path) your version must be > 3.7 or something; better download the last one!
ConsoleWrite("SQLite v" & _SQLite_LibVersion() & @LF)
_SQLite_SafeMode(0)
Local $hDB = _SQLite_Open()                         ; ("Puzzle.db3")  ; put this to make the DB disk-based, so as look at it
_SQLite_Exec($hDB,  "Begin;" & _
                    "DROP TABLE if exists Cells;" & _
                    "pragma recursive_triggers=on;" & _
                    "CREATE TABLE if not exists Cells (Num INTEGER, XY INTEGER, NumUsed BOOLEAN DEFAULT (0), CellUsed BOOLEAN DEFAULT (0));" & _
                    "CREATE INDEX if not exists ixNum ON Cells (Num);" & _
                    "CREATE INDEX if not exists ixXY ON Cells (XY);")

Local $values, $xy
For $i = 0 To 9
    For $j = 0 To 9
        $xy = 10 * $i + $j
        $values = StringSplit($aPb[$i][$j], ',', 2)
        For $val In $values
            _SQLite_Exec($hDB, "insert into cells (num, xy) values(" & $val & "," & $xy & ");")
        Next
    Next
Next
_SQLite_Exec($hDB, "commit;")

_SQLite_Exec($hDB, "begin;")
Global $rows, $cols, $newN
Global $Display = 0     ; set to 1 to watch progress in the combination tree

If _Solve() Then
    _SQLite_Exec($hDB, "commit;")
    ConsoleWrite(@LF & " One solution is the union of the following cells [row, column]:" & @LF)
    Local $sol
    _SQLite_QuerySingleRow($hDB, "select group_concat('[' || (pos / 10) || ',' || (pos % 10) || ']', ' ') from (select xy pos from cells where cellused group by xy order by xy);", $sol)
    ConsoleWrite(' ' & $sol[0] & @LF & @LF)
    _SQLite_GetTable2d($hDB, "select '[' || (xy / 10) || ',' || (xy % 10) || ']' [Cell], group_concat(num, ' ') [Content] from cells where cellused group by XY order by xy;", $sol, $rows, $cols)
    ConsoleWrite(_SQLite_Display2DResult($sol, 0, 1) & @LF)
Else
    _SQLite_Exec($hDB, "commit;")
    ConsoleWrite(@LF & "The problem has no solution" & @LF)
EndIf

_SQLite_Close($hDB)
_SQLite_Shutdown()

Func _Solve()
    Local $cells, $n, $sol
    Static $level = 0
    _SQLite_QuerySingleRow($hDB, "select num from cells where not numused;", $newN)
    If $newN[0] Then
        $n = Int($newN[0])
    Else
If $Display Then ConsoleWrite("! Success" & @LF)
        Return(1)
    EndIf
    _SQLite_GetTable($hDB, "select xy from cells C where num = " & $n & " and not cellused and not exists (select 1 from cells N where N.xy = C.xy and N.numused);", $cells, $rows, $cols)
    For $i = 2 To UBound($cells) - 1
If $Display Then
    _SQLite_QuerySingleRow($hDB, "select group_concat(num, ' ') from cells where cellused group by (select 1) order by num;", $sol)
    ConsoleWrite("  Done so far: {" & $sol[0] & '}' & @LF)
    ConsoleWrite("> Number " & $n & " trying cell [" & Int($cells[$i] / 10) & ',' & Mod($cells[$i], 10) & "] " & @LF)
EndIf
        $level += 1
        _SQLite_Exec($hDB, "savepoint sp" & $level & ";")
        _SQLite_Exec($hDB, "update cells set cellused = 1 where xy = " & $cells[$i] & ";")
        _SQLite_Exec($hDB, "update cells set numused = 1 where num in (select num from cells where xy = " & $cells[$i] & ");")
        If _Solve() Then Return(1)
If $Display Then ConsoleWrite("- Failed" & @LF)
        _SQLite_Exec($hDB, "rollback to sp" & $level & ";")
        $level -= 1
    Next
If $Display Then ConsoleWrite("+ Trying next leaf of previous branch" & @LF)
    Return(0)
EndFunc

What that teaches us is that an SQLITE-powered solution can successfully compete with much more pedestrian coding when the problem at hand can be somehow subsumed to operations on sets.

I really had fun with this!

Edited by jchd

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

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

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

Create an account

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


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0