qazwsx Posted August 22, 2007 Share Posted August 22, 2007 (edited) I have made a sudoku brute force solver, but i am having trouble with the backtracking of the solver. It seems to work for a while but then it seems to lose its place and skip all the way back to the beggining and then error out. expandcollapse popup#include <GUIConstants.au3> #include <array.au3> Global $constant[10][10];user numbers [row-1][column] Global $input[10][10];input boxes [row-1][column] Global $cell;cell to test Global $1 Global $2 Global $3 Global $r Global $c HotKeySet("{esc}", "_exit") $Form1_1 = GUICreate("solver", 633, 374, 189, 173) $Button1 = GUICtrlCreateButton("Solve", 264, 336, 75, 25, 0) For $i = 0 To 8 For $j = 1 To 9 $input[$i][$j] = GUICtrlCreateInput("", 56 * $j, 32 * ($i + 1), 41, 21) Next Next GUISetState(@SW_SHOW) While 1 $nMsg = GUIGetMsg() Switch $nMsg Case $GUI_EVENT_CLOSE Exit Case $Button1 _record() _brutetest () EndSwitch WEnd Func _record() For $i = 0 To 9 For $j = 1 To 9 $constant[$i][$j] = GUICtrlRead($input[$i][$j]) Next Next EndFunc ;==>_record Func _rowcheck($row, $column) For $i = 1 To 9 If $i <> $column Then If StringCompare(GUICtrlRead($input[$row - 1][$column]), GUICtrlRead($input[$row - 1][$i])) = 0 Then Return 1 EndIf Next EndFunc ;==>_rowcheck Func _columncheck($row, $column) For $i = 1 To 9 If $i <> $row Then If StringCompare(GUICtrlRead($input[$row - 1][$column]), GUICtrlRead($input[$i - 1][$column])) = 0 Then Return 1 EndIf Next EndFunc ;==>_columncheck Func _brutetest() For $r = 1 To 9;row For $c = 1 To 9;column If $constant[$r - 1][$c] = "" Then For $n = 1 To 9;number to test GUICtrlSetData($input[$r - 1][$c], $n) $1 = _rowcheck($r, $c) $2 = _columncheck($r, $c) $3 = _cellcheck($r, $c) If $1 = 0 And $2 = 0 And $3 = 0 Then ExitLoop Next ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Back track If $1 = 1 Or $2 = 1 Or $3 = 1 Then While 1 GUICtrlSetData($input[$r - 1][$c], $constant[$r - 1][$c]) $c = $c - 1 If $c < 1 Then $c = 9 $r = $r - 1 EndIf If $constant[$r - 1][$c] <> "" Then Else While 1 $back = GUICtrlRead($input[$r - 1][$c]) If $back = "" Then $back = 0 $back = $back + 1 If $back = 10 Then ExitLoop EndIf GUICtrlSetData($input[$r - 1][$c], $back) $1 = _rowcheck($r, $c) $2 = _columncheck($r, $c) $3 = _cellcheck($r, $c) If $1 = 0 And $2 = 0 And $3 = 0 Then ExitLoop (2) WEnd EndIf WEnd EndIf ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; EndIf Next Next EndFunc ;==>_brutetest Func _cellcheck($row, $column) $cellpos_row = Floor($row / 4) ; If $row= 0, 1, 2 then this=0, if $row= 3,4,5 then this=1, if $row= 6,7,8 then this=2 $cellpos_col = Floor(($column - 1) / 3); If $column= 1,2,3 then this=0, etc.. For $i = 3 * $cellpos_row To 3 * $cellpos_row + 2 ; (0 to 2) or (3 to 5) or (6 to 8) For $j = 3 * $cellpos_col + 1 To 3 * $cellpos_col + 3 ; (1 to 3) or (4 to 6) or (7 to 9) If $i <> $row - 1 Or $j <> $column Then If StringCompare(GUICtrlRead($input[$row - 1][$column]), GUICtrlRead($input[$i][$j])) = 0 Then Return 1 EndIf Next Next EndFunc ;==>_cellcheck Func _randomcheck () While 1 For $t = 0 to 8 For $l = 1 to 9 If $constant[$t][$l] = "" then GUICtrlSetData ($input[$t][$l], Random (1, 9, 1)) EndIf Next Next For $q = 1 to 9 For $z = 1 to 9 If _rowcheck($q, $z) = 1 or _columncheck ($q, $z) = 1 or _cellcheck ($q, $z) = 1 Then ExitLoop (2) Next Next If _rowcheck($q, $z) = 0 and _columncheck ($q, $z) = 0 and _cellcheck ($q, $z) = 0 Then ExitLoop (1) WEnd EndFunc Func _exit() Exit EndFunc ;==>_exit If you want a specific part of the code just ask me and ill post it. The back tracker part is set off by ;;; Edited August 23, 2007 by sccrstvn93 Link to comment Share on other sites More sharing options...
qazwsx Posted August 23, 2007 Author Share Posted August 23, 2007 *bump* Link to comment Share on other sites More sharing options...
Leighwyn Posted August 23, 2007 Share Posted August 23, 2007 *bump* expandcollapse popup#include <GUIConstants.au3> #include <array.au3> Global $constant[10][10];user numbers [row-1][column] Global $input[10][10];input boxes [row-1][column] Global $cell;cell to test HotKeySet("{esc}", "_exit") $Form1_1 = GUICreate("solver", 633, 374, 189, 173) $Button1 = GUICtrlCreateButton("Solve", 264, 336, 75, 25, 0) For $i = 0 To 8 For $j = 1 To 9 $input[$i][$j] = GUICtrlCreateInput("", 56 * $j, 32 * ($i + 1), 41, 21) Next Next GUISetState(@SW_SHOW) While 1 $nMsg = GUIGetMsg() Switch $nMsg Case $GUI_EVENT_CLOSE Exit Case $Button1 _record() Solver(1,1) EndSwitch WEnd Func _record() For $i = 0 To 8 For $j = 1 To 9 $constant[$i][$j] = GUICtrlRead($input[$i][$j]) Next Next EndFunc ;==>_record Func _rowcheck($row, $column) For $i = 1 To 9 If $i <> $column Then If StringCompare(GUICtrlRead($input[$row - 1][$column]), GUICtrlRead($input[$row - 1][$i])) = 0 Then Return 1 EndIf Next EndFunc ;==>_rowcheck Func _columncheck($row, $column) For $i = 1 To 9 If $i <> $row Then If StringCompare(GUICtrlRead($input[$row - 1][$column]), GUICtrlRead($input[$i - 1][$column])) = 0 Then Return 1 EndIf Next EndFunc ;==>_columncheck Func _cellcheck($row, $column) $cellpos_row = Floor(($row - 1)/3) ; If $row= 1, 2, 3 then this=0, if $row= 4,5,6 then this=1, if $row= 7,8,9 then this=2 $cellpos_col = Floor(($column - 1)/3); If $column= 1,2,3 then this=0, etc.. For $i = 3*$cellpos_row+1 To 3*$cellpos_row+3 ; (1 to 3) or (4 to 6) or (7 to 9) For $j = 3*$cellpos_col+1 To 3*$cellpos_col+3 ; (1 to 3) or (4 to 6) or (7 to 9) If $i <> $row Or $j <> $column Then If StringCompare(GUICtrlRead($input[$row - 1][$column]), GUICtrlRead($input[$i-1][$j])) = 0 Then Return 1 EndIf Next Next EndFunc ;==>_cellcheck Func Solver($row,$col) If $constant[$row-1][$col]="" Then For $value=1 to 9 GuictrlSetData($input[$row-1][$col],$value) $1 = _rowcheck($row,$col) $2 = _columncheck($row,$col) $3 = _cellcheck($row,$col) If $1<>1 and $2<>1 and $3<>1 Then If $col < 9 Then Solver($row,$col+1) Elseif $row < 9 Then Solver($row+1,1) Else msgbox(0,"","Solved!") EndIf EndIf Next GuictrlSetData($input[$row-1][$col],"") Else If $col < 9 Then Solver($row,$col+1) Elseif $row <9 Then Solver($row+1,1) Else msgbox(0,"","SOLVED!") EndIf EndIf EndFunc Func _exit() Exit EndFunc ;==>_exit Link to comment Share on other sites More sharing options...
Shevilie Posted August 23, 2007 Share Posted August 23, 2007 Not to bother you, but there is like 3,95 * 10^55 kombinations. I would suggest that you had a look of those different algorithm around the net to actually solve it - maybe bruteforce it the last part (That whats I would have done ) Start here if you are new Valuater's AutoIT 1-2-3Looking for an UDF - Look hereDo you need to do it twice - Autoit Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now