sudoku generator & solver

[CodyBarrett]

i've got a small start on this project of mine.

however

i've hit a bump. i've got the grids, and the checking functions done. but to place the initial values to make a unique grid is whats stumping me.

anywho this is my version

expandcollapse popup

#include <WINDOWSCONSTANTS.au3>
#include <GUICONSTANTSEX.au3>
#include <STATICCONSTANTS.au3>
#include <EDITCONSTANTS.au3>
Global $nSQUARE_SIDE_SIZE = 180
Global $nBLOCK_SIDE_SIZE = $nSQUARE_SIDE_SIZE/3
Global $hHWND = GUICreate (@ScriptName,3*$nSQUARE_SIDE_SIZE,3*$nSQUARE_SIDE_SIZE,Default,Default,Default,Default,Default)
Dim $aGUI_GRID[3][3][3][3]
Dim $aVALUE_GRID[3][3][3][3]
Dim $aVALUE_GRID_POSSIBLE[3][3][3][3]
;blank string = blank square
For $nSQUARE_X = 0 To 2
    For $nSQUARE_Y = 0 To 2
        $nCOLOR = '0x' & Hex (Random (0x202020,0xFFFFFF,1),6)
        $nFCOLOR = invert_color ($nCOLOR)
        For $nBLOCK_X = 0 To 2
            For $nBLOCK_Y = 0 To 2
                $nX = ($nSQUARE_X*($nSQUARE_SIDE_SIZE))+($nBLOCK_X*$nBLOCK_SIDE_SIZE)
                $nY = ($nSQUARE_Y*($nSQUARE_SIDE_SIZE))+($nBLOCK_Y*$nBLOCK_SIDE_SIZE)
                $aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = GUICtrlCreateInput ('',$nX,$nY,$nBLOCK_SIDE_SIZE,$nBLOCK_SIDE_SIZE,BitOR ($SS_CENTER,$SS_CENTERIMAGE,$ES_NUMBER),Default)
                $aVALUE_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = ''
                $aVALUE_GRID_POSSIBLE[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = '123456789'
                GUICtrlSetFont ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y],$nBLOCK_SIDE_SIZE/2,999,Default,'Tahoma')
                GUICtrlSetLimit ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y],1,0)
                GUICtrlSetBkColor ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y],$nCOLOR)
                GUICtrlSetColor ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y],$nFCOLOR)
            Next
        Next
    Next
Next
GUISetState (@SW_SHOW,$hHWND)
;~ Sleep (2000)
generate_new_grid ()
While True
    Switch GUIGetMsg ()
        Case $GUI_EVENT_CLOSE
            Exit
        Case Else
    EndSwitch
WEnd
Func invert_color ($sCOLOR)
    Local $sSTRING = ''
    Local $sRETURN = ''
    Local $nCOUNT = 0
    For $nCOUNT = 1 To 6 Step 2
        $sSTRING = StringMid (StringTrimLeft ($sCOLOR,2),$nCOUNT,2)
        $sRETURN &= 255-Dec ($sSTRING)
    Next
    Return '0x' & $sRETURN
EndFunc
Func reset_grid ()
    Local $nSQUARE_X
    Local $nSQUARE_Y
    Local $nBLOCK_X
    Local $nBLOCK_Y
    For $nSQUARE_X = 0 To 2
        For $nSQUARE_Y = 0 To 2
            For $nBLOCK_X = 0 To 2
                For $nBLOCK_Y = 0 To 2
                    $aVALUE_GRID_POSSIBLE[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = '123456789'
                    set_block_with_number ('',$nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
                Next
            Next
        Next
    Next
EndFunc
Func reset_from_point ($nSQUARE_X_START,$nSQUARE_Y_START,$nBLOCK_X_START,$nBLOCK_Y_START)
    Local $nSQUARE_X
    Local $nSQUARE_Y
    Local $nBLOCK_X
    Local $nBLOCK_Y
    For $nSQUARE_X = $nSQUARE_X_START To 2
        For $nSQUARE_Y = $nSQUARE_Y_START To 2
            For $nBLOCK_X = $nBLOCK_X_START To 2
                For $nBLOCK_Y =$nBLOCK_Y_START To 2
                    $aVALUE_GRID_POSSIBLE[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = '123456789'
                    set_block_with_number ('',$nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
                Next
            Next
        Next
    Next
EndFunc
Func check_for_blanks ()
    Local $nSQUARE_X
    Local $nSQUARE_Y
    Local $nBLOCK_X
    Local $nBLOCK_Y
    For $nSQUARE_X = 0 To 2
        For $nSQUARE_Y = 0 To 2
            For $nBLOCK_X = 0 To 2
                For $nBLOCK_Y = 0 To 2
                    If $aVALUE_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = '' Then
                        Return False
                    EndIf
                Next
            Next
        Next
    Next
EndFunc
Func generate_new_grid ()
    Local $nSQUARE_X
    Local $nSQUARE_Y
    Local $nBLOCK_X
    Local $nBLOCK_Y
    Local $nNUMBER
    reset_grid ()



    For $nSQUARE_X = 0 To 2
        For $nSQUARE_Y = 0 To 2
            For $nBLOCK_X = 0 To 2
                For $nBLOCK_Y = 0 To 2
                    If generate_number ($nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y) = False Then
                        reset_from_point ($nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
                        If $nBLOCK_Y = 2 Then
                            ExitLoop 1
                        ElseIf $nBLOCK_X = 2 Then
                            ExitLoop 2
                        ElseIf $nSQUARE_Y = 2 Then
                            ExitLoop 3
                        EndIf
                    EndIf
                Next
            Next
        Next
    Next






    If check_for_blanks () = False Then
        generate_new_grid ()
    EndIf
EndFunc
Func generate_number ($nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
    Local $nNUMBER
    Local $sSTRING = $aVALUE_GRID_POSSIBLE[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y]
    If StringLen ($sSTRING) >= 1 Then
        If StringLen ($sSTRING) = 1 Then
            $nNUMBER = $sSTRING
        Else
            $nNUMBER = StringMid ($sSTRING,Random (1,StringLen ($sSTRING),1),1)
        EndIf
        $aVALUE_GRID_POSSIBLE[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = StringReplace ($sSTRING,$nNUMBER,'')
        If check_square ($nNUMBER,$nSQUARE_X,$nSQUARE_Y) = True Then
            If check_column ($nNUMBER,$nSQUARE_Y,$nBLOCK_Y) = True Then
                If check_row ($nNUMBER,$nSQUARE_X,$nBLOCK_X) = True Then
                    set_block_with_number ($nNUMBER,$nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
                    Return True
                Else
                    Return generate_number ($nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
                EndIf
            Else
                Return generate_number ($nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
            EndIf
        Else
            Return generate_number ($nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
        EndIf
    Else
        Return False
    EndIf
EndFunc
Func check_square ($nNUMBER,$nSQUARE_X,$nSQUARE_Y)
    Local $nBLOCK_X
    Local $nBLOCK_Y
    For $nBLOCK_X = 0 To 2
        For $nBLOCK_Y = 0 To 2
            If GUICtrlRead ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y]) = $nNUMBER Then
                Return False
            EndIf
        Next
    Next
    Return True
EndFunc
Func check_block ($nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
    If GUICtrlRead ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y]) <> '' Then
        Return False
    Else
        Return True
    EndIf
EndFunc
Func check_row ($nNUMBER,$nSQUARE_X,$nBLOCK_X)
    Local $nSQUARE_Y
    Local $nBLOCK_Y
    For $nSQUARE_Y = 0 To 2
        For $nBLOCK_Y = 0 To 2
            If GUICtrlRead ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y]) = $nNUMBER Then
                Return False
            EndIf
        Next
    Next
    Return True
EndFunc
Func check_column ($nNUMBER,$nSQUARE_Y,$nBLOCK_Y)
    Local $nSQUARE_X
    Local $nBLOCK_X
    For $nSQUARE_X = 0 To 2
        For $nBLOCK_X = 0 To 2
            If GUICtrlRead ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y]) = $nNUMBER Then
                Return False
            EndIf
        Next
    Next
    Return True
EndFunc
Func set_block_with_number ($nNUMBER,$nSQUARE_X,$nSQUARE_Y,$nBLOCK_X,$nBLOCK_Y)
    $aVALUE_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y] = $nNUMBER
    GUICtrlSetData ($aGUI_GRID[$nSQUARE_X][$nSQUARE_Y][$nBLOCK_X][$nBLOCK_Y],$nNUMBER)
EndFunc

much more research will be needed.

Edited February 24, 2011 by CodyBarrett

[CodyBarrett]

okay so i've gotten it to backtrack and restart with a random number but it exceeds the recursion level.

i've searched the forums, and google, found PLENTY of examples, but it just flies over my head... anyone know where i'm going wrong?

[jvanegmond]

okay so i've gotten it to backtrack and restart with a random number but it exceeds the recursion level.

i've searched the forums, and google, found PLENTY of examples, but it just flies over my head... anyone know where i'm going wrong?

If you get a "recursion level exceeded" then you probably have infinite recursion. There are a few cases to think of where you can 1. Use recursion in a valid way and 2. Exceed recursion level, but they're pretty uncommon. Anyway, the only place where you really have a recursion problem is here:

Func generate_new_grid ()
    ; Do stuff
    If stuff failed Then
        generate_new_grid ()
    EndIF
EndFunc

Replace with:

Func generate_new_grid()
    While 1
       ; Do stuff
       If NOT stuff failed Then
          ExitLoop
       EndiF
    Wend

Then you don't get recursion level exceeded anymore, and you just have the problem that your generation code is shit and probably will never find a solution.

[CodyBarrett]

oh, mmk. loop instead of recursion.

thanks....

-sigh- back to the drawing board..