Jump to content
Sign in to follow this  
qazwsx

Help with sudoku backtracking

Recommended Posts

qazwsx

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.

#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 by sccrstvn93

Share this post


Link to post
Share on other sites
Leighwyn

*bump*

#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

Share this post


Link to post
Share on other sites
Shevilie

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

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  

×

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.