Jump to content

Sudoku solver help

qazwsx

By qazwsx,
in AutoIt General Help and Support

 Share

Recommended Posts

qazwsx Universalist

qazwsx

Posted
Posted (edited)

Im having a problem with the backtracker the code for the backtracker is offset by the ;;;;;

#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 Then
                    
                    While 1
                        GUICtrlSetData($input[$r - 1][$c], $constant[$r - 1][$c])
                        $c = $c - 1
                        If $c = 0 Then
                            $c = 9
                            $r = $r - 1
                        EndIf
                        If $constant[$r - 1][$c] = "" Then
                            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
;[check to see if value is repeated]
            EndIf
        Next
    Next
EndFunc;==>_cellcheck



Func _exit()
    Exit
EndFunc;==>_exit

Here is the new code but i get ab error on line 86 about a badly formated array. I cannot see a problem with it.

Edit: i dont think the problem is actually with that line. I think somehow my script is losing the position of where the user input values are so the script is then overwriting these values with somehting else. Im not sure tho.

Edited by sccrstvn93
Link to comment
Share on other sites
martin Universalist

martin

Posted
Posted

I am trying to make a brute force soduko solver. I have the input setup and the reading of the variable but the logic behin chekcing if a number is already present in a column is killing me. I have looked at some of the other solvers but i don not understand them. If someone could just explain this to me it would be greatly appreciated. Thx in advance.

Can you show what you have so far? Your question is difficult to answer when you haven't told us how you reference the squares for example. Are they numbered 1 to 81, or are they in row x and column y or something else?

Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.
Link to comment
Share on other sites
qazwsx Universalist

qazwsx

Posted
  • Author
Posted (edited)

Yeh sorry, I have created a row checker and a column checker, now all i need is the cell checker.

#include <GUIConstants.au3>
#include <array.au3>
#include <math.au3>
Global $constant[10][10];user numbers [row-1][column]
Global $input[10][10];input boxes [row-1][column]
Global $cell;cell to test


$Form1_1 = GUICreate("solver", 633, 374, 189, 173)
$Button1 = GUICtrlCreateButton("Solve", 264, 336, 75, 25, 0)
$input[0][1] = GUICtrlCreateInput("", 56, 32, 41, 21)
$input[0][2] = GUICtrlCreateInput("", 112, 32, 41, 21)
$input[0][3] = GUICtrlCreateInput("", 168, 32, 41, 21)
$input[0][4] = GUICtrlCreateInput("", 232, 32, 41, 21)
$input[0][5] = GUICtrlCreateInput("", 288, 32, 41, 21)
$input[0][6] = GUICtrlCreateInput("", 344, 32, 41, 21)
$input[0][7] = GUICtrlCreateInput("", 408, 32, 41, 21)
$input[0][8] = GUICtrlCreateInput("", 464, 32, 41, 21)
$input[0][9] = GUICtrlCreateInput("", 520, 32, 41, 21)
$input[1][1] = GUICtrlCreateInput("", 56, 64, 41, 21)
$input[1][2] = GUICtrlCreateInput("", 112, 64, 41, 21)
$input[1][3] = GUICtrlCreateInput("", 168, 64, 41, 21)
$input[1][4] = GUICtrlCreateInput("", 232, 64, 41, 21)
$input[1][5] = GUICtrlCreateInput("", 288, 64, 41, 21)
$input[1][6] = GUICtrlCreateInput("", 344, 64, 41, 21)
$input[1][7] = GUICtrlCreateInput("", 408, 64, 41, 21)
$input[1][8] = GUICtrlCreateInput("", 464, 64, 41, 21)
$input[1][9] = GUICtrlCreateInput("", 520, 64, 41, 21)
$input[2][1] = GUICtrlCreateInput("", 56, 96, 41, 21)
$input[2][2] = GUICtrlCreateInput("", 112, 96, 41, 21)
$input[2][3] = GUICtrlCreateInput("", 168, 96, 41, 21)
$input[2][4] = GUICtrlCreateInput("", 232, 96, 41, 21)
$input[2][5] = GUICtrlCreateInput("", 288, 96, 41, 21)
$input[2][6] = GUICtrlCreateInput("", 344, 96, 41, 21)
$input[2][7] = GUICtrlCreateInput("", 408, 96, 41, 21)
$input[2][8] = GUICtrlCreateInput("", 464, 96, 41, 21)
$input[2][9] = GUICtrlCreateInput("", 520, 96, 41, 21)
$input[3][1] = GUICtrlCreateInput("", 56, 136, 41, 21)
$input[3][2] = GUICtrlCreateInput("", 112, 136, 41, 21)
$input[3][3] = GUICtrlCreateInput("", 168, 136, 41, 21)
$input[3][4] = GUICtrlCreateInput("", 232, 136, 41, 21)
$input[3][5] = GUICtrlCreateInput("", 288, 136, 41, 21)
$input[3][6] = GUICtrlCreateInput("", 344, 136, 41, 21)
$input[3][7] = GUICtrlCreateInput("", 408, 136, 41, 21)
$input[3][8] = GUICtrlCreateInput("", 464, 136, 41, 21)
$input[3][9] = GUICtrlCreateInput("", 520, 136, 41, 21)
$input[4][1] = GUICtrlCreateInput("", 56, 168, 41, 21)
$input[4][2] = GUICtrlCreateInput("", 112, 168, 41, 21)
$input[4][3] = GUICtrlCreateInput("", 168, 168, 41, 21)
$input[4][4] = GUICtrlCreateInput("", 232, 168, 41, 21)
$input[4][5] = GUICtrlCreateInput("", 288, 168, 41, 21)
$input[4][6] = GUICtrlCreateInput("", 344, 168, 41, 21)
$input[4][7] = GUICtrlCreateInput("", 408, 168, 41, 21)
$input[4][8] = GUICtrlCreateInput("", 464, 168, 41, 21)
$input[4][9] = GUICtrlCreateInput("", 520, 168, 41, 21)
$input[5][1] = GUICtrlCreateInput("", 56, 200, 41, 21)
$input[5][2] = GUICtrlCreateInput("", 112, 200, 41, 21)
$input[5][3] = GUICtrlCreateInput("", 168, 200, 41, 21)
$input[5][4] = GUICtrlCreateInput("", 232, 200, 41, 21)
$input[5][5] = GUICtrlCreateInput("", 288, 200, 41, 21)
$input[5][6] = GUICtrlCreateInput("", 344, 200, 41, 21)
$input[5][7] = GUICtrlCreateInput("", 408, 200, 41, 21)
$input[5][8] = GUICtrlCreateInput("", 464, 200, 41, 21)
$input[5][9] = GUICtrlCreateInput("", 520, 200, 41, 21)
$input[6][1] = GUICtrlCreateInput("", 56, 240, 41, 21)
$input[6][2] = GUICtrlCreateInput("", 112, 240, 41, 21)
$input[6][3] = GUICtrlCreateInput("", 168, 240, 41, 21)
$input[6][4] = GUICtrlCreateInput("", 232, 240, 41, 21)
$input[6][5] = GUICtrlCreateInput("", 288, 240, 41, 21)
$input[6][6] = GUICtrlCreateInput("", 344, 240, 41, 21)
$input[6][7] = GUICtrlCreateInput("", 408, 240, 41, 21)
$input[6][8] = GUICtrlCreateInput("", 464, 240, 41, 21)
$input[6][9] = GUICtrlCreateInput("", 520, 240, 41, 21)
$input[7][1] = GUICtrlCreateInput("", 56, 272, 41, 21)
$input[7][2] = GUICtrlCreateInput("", 112, 272, 41, 21)
$input[7][3] = GUICtrlCreateInput("", 168, 272, 41, 21)
$input[7][4] = GUICtrlCreateInput("", 232, 272, 41, 21)
$input[7][5] = GUICtrlCreateInput("", 288, 272, 41, 21)
$input[7][6] = GUICtrlCreateInput("", 344, 272, 41, 21)
$input[7][7] = GUICtrlCreateInput("", 408, 272, 41, 21)
$input[7][8] = GUICtrlCreateInput("", 464, 272, 41, 21)
$input[7][9] = GUICtrlCreateInput("", 520, 272, 41, 21)
$input[8][1] = GUICtrlCreateInput("", 56, 304, 41, 21)
$input[8][2] = GUICtrlCreateInput("", 112, 304, 41, 21)
$input[8][3] = GUICtrlCreateInput("", 168, 304, 41, 21)
$input[8][4] = GUICtrlCreateInput("", 232, 304, 41, 21)
$input[8][5] = GUICtrlCreateInput("", 288, 304, 41, 21)
$input[8][6] = GUICtrlCreateInput("", 344, 304, 41, 21)
$input[8][7] = GUICtrlCreateInput("", 408, 304, 41, 21)
$input[8][8] = GUICtrlCreateInput("", 464, 304, 41, 21)
$input[8][9] = GUICtrlCreateInput("", 520, 304, 41, 21)
GUISetState(@SW_SHOW)


While 1
    $nMsg = GUIGetMsg()
    Switch $nMsg
        Case $GUI_EVENT_CLOSE
            Exit
        Case $Button1
            _record()
            MsgBox (0, "", "")
            _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 _boxcheck ($row, $column)
    

endfunc


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)
                    If $1 = 0 and $2 = 0 Then ExitLoop
                    
                Next
            EndIf
        Next
    Next
EndFunc ;==>_brutetest

If you want a specific part of the code just ask me and ill repost it. I have it setup so the input boxes are 2 dimensional arrays. the first dimension is the row - 1 and the second is the column. Right now i dont ever store the values of the input boxes, this was so i could see what was goin on. If anyone thinks this will be a major slowdown of the final script just tell me and ill try to fix it.

Edited by sccrstvn93
Link to comment
Share on other sites
Leighwyn Wayfarer

Leighwyn

Posted
Posted (edited)

With the way you've numbered things, here's what you'd want to do to check each 3x3 cell:

Note: Untested

Func _cellcheck($row, $column)
    $cell_rowstart = 3*floor($row/3)  ;  If $row= 0, 1, 2 then this=0, if $row= 3,4,5 then this=3, if $row= 6,7,8 then this=6
    $cell_colstart = 3*floor(($column-1)/3)+1 ;  If $column= 1,2,3 then this=1, etc..

    For $i = $cell_rowstart to $cell_rowstart+ 2  ;  (0 to 2) or (3 to 5) or (6 to 8)
        For $j = $cell_colstart to $cell_colstart +2  ;  (1 to 3) or (4 to 6) or (7 to 9)
            If $i <> $row AND $j <> $column Then
                ;[check to see if value is repeated]
            EndIf
        Next
    Next
EndFuncoÝ÷ Ø l£bìßÚÞyØ­x2¢é¢Z³¥·©§Ê«&§¶X¬¶È­r·¶*'Â+ajëh×6for $i = 0 to 8
    for $j = 1 to 9
        $input[$i][$j] = GUICtrlCreateInput("", 56*$j, 32*($i+1), 41, 21)
    Next
Next
Edited by Leighwyn
Link to comment
Share on other sites
qazwsx Universalist

qazwsx

Posted
  • Author
Posted (edited)

thx for the help but i don't understand how to check it.

Func _cellcheck($row, $column)

$cellpos_row = floor($row/3) ; 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 AND $j <> $column Then

If StringCompare(GUICtrlRead($input[$row - 1][$column]), GUICtrlRead($input[$row - 1][$i])) = 0 Then Return 1

;[check to see if value is repeated]

EndIf

Next

Next

EndFunc

Edit: dam i knew there was an easier way to make all thos inputs

The logic is still confusing me. Does this check one box against every other one in the cell? Im sorry but if its obvious or it seems like im being lazy.

Edited by sccrstvn93
Link to comment
Share on other sites
Leighwyn Wayfarer

Leighwyn

Posted
Posted (edited)

yes this checks each box against every box in its own cell. If your box was row 6 column 3, then the first two calculations would say that this box should be checked against boxes from row 6 to row 8 and column 1 to column 3

On another note...

I think you might have to work harder on your _brutetest( ) code, it doesn't seem adequate. It almost feels like you'd need some recursion to make things work. Right now things are like....

$r = 1, $c = 1

$n = 1 works, cycling to next $c

$r = 1, $c = 2

$n = 1 doesn't work

$n = 2 , etc..

But what if for that first box, $r=$c=1, not only 1 would have worked? What if it could have been any number at this state? And the actual solution has it as NOT 1? You have no way to go BACK to this very first box and try alternate values once you inevitably reach the point where you're sitting at a box later into the code, and NO values work.

Basically, do you have any way to keep trying new numbers for a cell, if the one you originally picked turns out to not be the correct one? As it is now, I don't think you do.

Edited by Leighwyn
Link to comment
Share on other sites
qazwsx Universalist

qazwsx

Posted
  • Author
Posted (edited)

Yeh i am working on the back tracking here is wat i have so far 

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)
                    If $1 = 0 And $2 = 0 And $3 = 0 Then ExitLoop
                Next
                
                
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;Back track
                If $1 = 1 Or $2 = 1 Then
                    
                    While 1
                        GUICtrlSetData($input[$r - 1][$c], "")
                        $c = $c - 1
                        If $c = 0 Then
                            $c = 9
                            $r = $r - 1
                        EndIf

                        While 1
                            $back = GUICtrlRead($input[$r - 1][$c])
                            $back = $back + 1
                            If $back = 10 Then
                                ExitLoop
                            EndIf
                            GUICtrlSetData($input[$r - 1][$c], $back)
                            $1 = _rowcheck($r, $c)
                            $2 = _columncheck($r, $c)
                            
                            If $1 = 0 And $2 = 0 Then ExitLoop (2)
                            
                        WEnd
                        
                    WEnd
                EndIf
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
            EndIf
        Next
    Next
EndFunc;==>_brutetest

It backtracks and seems to work fairly well, but i need a way for it to check if the value of the input is a $constant so it does not change it. Im trying to figure out where the best place for that if statement would be.

Thx for all the help.

Edit: did one of your posts just diappear?

Edit2: it still does not include the _cellcheck () because that was giving errors, i think i screwed up the checking part.

Edited by sccrstvn93
Link to comment
Share on other sites
Vardebedian Seeker

Vardebedian

Posted
Posted

I am trying to make a brute force soduko solver. I have the input setup and the reading of the variable but the logic behin chekcing if a number is already present in a column is killing me. I have looked at some of the other solvers but i don not understand them. If someone could just explain this to me it would be greatly appreciated. Thx in advance.

Edit: I need help with the cell check and backtracking

Edit2: if you want to see the newest version of code just tell me, it has the ability to check rows and columns and has the code to check cells but i cannot figure out how to impliment it.

Func _cellcheck($row, $column)
    $cellpos_row = Floor($row/ 3);  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 and $j <> $column Then
                If StringCompare(GUICtrlRead($input[$row-1][$column]), GUICtrlRead($input[$i][$j])) = 0 Then Return 1
        ;[check to see if value is repeated]
            EndIf
        Next
    Next
EndFunc ;==>_cellcheck

For some reason the cell checker is not working it gets some of the doubles but not all.

Two years ago I wrote a soduku solver and generator. Brute force solvers are lost against sudoku with 17-23 clues. If you want, may download absolute free sudoku collections from my web site. There you'll find also a collection of fourty hard-and-terrible seventeen clues, so you may test your solver.

I also tried to write a kakuro solver and generator using Autoit3, but it's too slow for this purpose.

Have a good luck!

Link to comment
Share on other sites
qazwsx Universalist

qazwsx

Posted
  • Author
Posted

Brute force solvers are lost against sudoku with 17-23 clues

What does that mean. It just takes a long time for it to get the answer? Thx for the help. Anyone have any ideas on how to fix the _cellchecker or make the back tracker more efficient?

Link to comment
Share on other sites
Leighwyn Wayfarer

Leighwyn

Posted
Posted

What does that mean. It just takes a long time for it to get the answer? Thx for the help. Anyone have any ideas on how to fix the _cellchecker or make the back tracker more efficient?

That's my fault, I didn't realized you passed in your check functions a 1-9 for row, I had assumed it was the 0-8 like how you'd defined it. Just change this line:

$cellpos_row = Floor($row /3)oÝ÷ ÚÚºÚ"µÍÌÍØÙ[Ü×ÜÝÈHÛÜ
    ÌÍÜÝÈHJKÌÊ
Link to comment
Share on other sites
qazwsx Universalist

qazwsx

Posted
  • Author
Posted (edited)

yeh i tried that but for some reason it was giving me an error, so i changed the three to a 4 and it seems to be working now. But it is taking extremely long to solve a blank board. Is a blank board hard for a brute force solver? I need a way to seperate the cells from each other so it is easier to read, Should i add lines to the gui and if so, do i need to find an image?

Edited by sccrstvn93
Link to comment
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
 Share
Go to topic listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...