Sudoku solution finder

Share your advanced PureBasic knowledge/code with the community.
rob6523
User
User
Posts: 59
Joined: Sat Sep 25, 2004 2:02 pm
Location: Netherlands (Ophemert)
Contact:

Sudoku solution finder

Post by rob6523 »

Code updated for 5.20+

Here is some code I found on the French forum adapted to PB 4.00
Credits for the code go to Guillaume HUSSON (French forum)

Code: Select all

; Sudoku Killer, Sudoku solver using a kind of backtracking 
; 14/02/06 Guillaume HUSSON 

; the original code was found on the french forum.
; PB 4.00  (Code adapted from pb 3.94 by rob6523)

; la fenetre 
Enumeration 
  #sudoku 
EndEnumeration 

; les champs, les boutons et les "traits" 
Enumeration 
  #String_00 
  #String_01 
  #String_02 
  #String_03 
  #String_04 
  #String_05 
  #String_06 
  #String_07 
  #String_08 
  #String_10 
  #String_11 
  #String_12 
  #String_13 
  #String_14 
  #String_15 
  #String_16 
  #String_17 
  #String_18 
  #String_20 
  #String_21 
  #String_22 
  #String_23 
  #String_24 
  #String_25 
  #String_26 
  #String_27 
  #String_28 
  #String_30 
  #String_31 
  #String_32 
  #String_33 
  #String_34 
  #String_35 
  #String_36 
  #String_37 
  #String_38 
  #String_40 
  #String_41 
  #String_42 
  #String_43 
  #String_44 
  #String_45 
  #String_46 
  #String_47 
  #String_48 
  #String_50 
  #String_51 
  #String_52 
  #String_53 
  #String_54 
  #String_55 
  #String_56 
  #String_57 
  #String_58 
  #String_60 
  #String_61 
  #String_62 
  #String_63 
  #String_64 
  #String_65 
  #String_66 
  #String_67 
  #String_68 
  #String_70 
  #String_71 
  #String_72 
  #String_73 
  #String_74 
  #String_75 
  #String_76 
  #String_77 
  #String_78 
  #String_80 
  #String_81 
  #String_82 
  #String_83 
  #String_84 
  #String_85 
  #String_86 
  #String_87 
  #String_88 
  #Button_Clear 
  #Button_OK 
  #TraitVertical 
  #TraitHorizontal 
  #TraitVertical0 
  #TraitHorizontal0 
  #TraitVertical1 
  #TraitHorizontal1 
  #TraitVertical2 
  #TraitHorizontal2 
  #TraitVertical3 
  #TraitHorizontal3 
  #TraitVertical4 
  #TraitHorizontal4 
  #TraitVertical5 
  #TraitHorizontal5 
  #TraitVertical6 
  #TraitHorizontal6 
  #TraitVertical7 
  #TraitHorizontal7 
  #TraitVertical8 
  #TraitHorizontal8 
  #TraitVertical9 
  #TraitHorizontal9 
  #TraitVertical10 
  #TraitHorizontal10 
  #TraitVertical11 
  #TraitHorizontal11 
  #TraitVertical12 
  #TraitHorizontal12 
  #TraitVertical13 
  #TraitHorizontal13 
  #TraitVertical14 
  #TraitHorizontal14 
  #TraitVertical15 
  #TraitHorizontal15 
  #TraitVertical16 
  #TraitHorizontal16 
  #TraitVertical17 
  #TraitHorizontal17 
  #TraitVertical18 
  #TraitHorizontal18 
  #TraitVertical19 
  #TraitHorizontal19 
  #TraitVertical20 
  #TraitHorizontal20 
EndEnumeration 

Structure elements
  valeur.b
  valeursPossibles.s
EndStructure

; the grid representing the sudoku 
Global Dim sudoku.elements(9,9)

; Open the main window
Procedure Open_sudoku() 
  If OpenWindow(#sudoku, 0, 0, 390, 430, "Sudoku Killer | © Guillaume HUSSON",  #PB_Window_SystemMenu | #PB_Window_TitleBar | #PB_Window_MinimizeGadget | #PB_Window_ScreenCentered ) 
    CreateImage(#TraitHorizontal, 383, 1); crée un trait noir horizontal 
    CreateImage(#TraitVertical, 1,383) ; crée un trait noir vertical 
    If CreateGadgetList(WindowID(0)) 
      ; les "traits" : 
      ImageGadget(#TraitHorizontal0, 4, 4, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal1, 4, 5, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal2, 4, 6, 390, 1, ImageID(#TraitHorizontal)) 
      
      ImageGadget(#TraitHorizontal3, 4, 45, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal4, 4, 85, 390, 1, ImageID(#TraitHorizontal)) 
      
      ImageGadget(#TraitHorizontal5, 4, 129, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal6, 4, 130, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal7, 4, 131, 390, 1, ImageID(#TraitHorizontal)) 
      
      ImageGadget(#TraitHorizontal8, 4, 175, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal9, 4, 215, 390, 1, ImageID(#TraitHorizontal)) 
      
      ImageGadget(#TraitHorizontal10, 4, 259, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal11, 4, 260, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal12, 4, 261, 390, 1, ImageID(#TraitHorizontal)) 
      
      ImageGadget(#TraitHorizontal13, 4, 305, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal14, 4, 345, 390, 1, ImageID(#TraitHorizontal)) 
      
      ImageGadget(#TraitHorizontal15, 4, 384, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal16, 4, 385, 390, 1, ImageID(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal17, 4, 386, 390, 1, ImageID(#TraitHorizontal)) 
      
      ImageGadget(#TraitVertical0, 4, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical1, 5, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical2, 6, 4, 390, 1, ImageID(#TraitVertical)) 
      
      ImageGadget(#TraitVertical3, 45, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical4, 85, 4, 390, 1, ImageID(#TraitVertical)) 
      
      ImageGadget(#TraitVertical5, 129, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical6, 130, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical7, 131, 4, 390, 1, ImageID(#TraitVertical)) 
      
      ImageGadget(#TraitVertical8, 175, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical9, 215, 4, 390, 1, ImageID(#TraitVertical)) 
      
      ImageGadget(#TraitVertical10, 259, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical11, 260, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical12, 261, 4, 390, 1, ImageID(#TraitVertical)) 
      
      ImageGadget(#TraitVertical13, 305, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical14, 345, 4, 390, 1, ImageID(#TraitVertical)) 
      
      ImageGadget(#TraitVertical15, 384, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical16, 385, 4, 390, 1, ImageID(#TraitVertical)) 
      ImageGadget(#TraitVertical17, 386, 4, 390, 1, ImageID(#TraitVertical)) 
      
      ; les champs 
      StringGadget(#String_00, 10, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_01, 50, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_02, 90, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_03, 140, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_04, 180, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_05, 220, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_06, 270, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_07, 310, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_08, 350, 10, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_10, 10, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_11, 50, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_12, 90, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_13, 140, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_14, 180, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_15, 220, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_16, 270, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_17, 310, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_18, 350, 50, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_20, 10, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_21, 50, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_22, 90, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_23, 140, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_24, 180, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_25, 220, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_26, 270, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_27, 310, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_28, 350, 90, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_30, 10, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_31, 50, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_32, 90, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_33, 140, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_34, 180, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_35, 220, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_36, 270, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_37, 310, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_38, 350, 140, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_40, 10, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_41, 50, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_42, 90, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_43, 140, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_44, 180, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_45, 220, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_46, 270, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_47, 310, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_48, 350, 180, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_50, 10, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_51, 50, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_52, 90, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_53, 140, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_54, 180, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_55, 220, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_56, 270, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_57, 310, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_58, 350, 220, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_60, 10, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_61, 50, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_62, 90, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_63, 140, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_64, 180, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_65, 220, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_66, 270, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_67, 310, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_68, 350, 270, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_70, 10, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_71, 50, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_72, 90, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_73, 140, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_74, 180, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_75, 220, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_76, 270, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_77, 310, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_78, 350, 310, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      StringGadget(#String_80, 10, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_81, 50, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_82, 90, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_83, 140, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_84, 180, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_85, 220, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_86, 270, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_87, 310, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      StringGadget(#String_88, 350, 350, 30, 30, "", #PB_String_Numeric | #ESB_DISABLE_LEFT) 
      
      ; the buttons 
      ButtonGadget(#Button_OK, 85, 393, 110, 30, "Find a solution") 
      ButtonGadget(#Button_Clear, 200, 393, 110, 30, "Clear the grid") 
    EndIf 
  EndIf 
EndProcedure 

; in the case there is a value (0 if there isn't found one yet) 
; and a list of possible values, represented by a character string
; example, if it could be a 4, a 2 or a 6, the character string would be "426" 


Procedure initialiser() ; initialize the sudoku 
  For i=0 To 8 
    For j=0 To 8 
      sudoku(i,j)\valeur = 0 
      sudoku(i,j)\valeursPossibles = "123456789" 
    Next j 
  Next i 
EndProcedure 

Procedure verifier(GadgetID)  ; vérifie si la valeur que l'on vient de taper est bien un nombre à UN SEUL chiffre 
  If (Len(GetGadgetText(GadgetID)) > 1) 
    SetGadgetText(GadgetID, Left(GetGadgetText(GadgetID),1)) 
  EndIf 
EndProcedure 

Procedure.b estResolu() ; return 1 if solved otherwise 0  
  result.b = 1 
  For i=0 To 8 
    For j=0 To 8 
      If sudoku(i,j)\valeur=0 
        result = 0 
      EndIf 
    Next j 
  Next i 
  ProcedureReturn result 
EndProcedure 

; renvoie, sous forme de chaine de caractère, la liste des valeurs que ne peut pas prendre la case (ligne,colonne) 
; cette ligne peut contenir des répétitions (pas génant) 
Procedure.s listeValeursEnPrise(ligne.b,colonne.b) 
  result.s = "" 
  ; les valeurs sur la même ligne 
  For i.b=0 To 8 
    If ((i <> colonne) And (sudoku(ligne,i)\valeur <> 0)) ; on tient une valeur : on l'ajoute 
      result$ + Str(sudoku(ligne,i)\valeur) 
    EndIf 
  Next i 
  ; les valeurs sur la même colonne 
  For i=0 To 8 
    If ((i <> ligne) And (sudoku(i,colonne)\valeur <> 0)) ; on tient une valeur : on l'ajoute 
      result$ + Str(sudoku(i,colonne)\valeur) 
    EndIf 
  Next i 
  ; les valeurs dans le même carré 
  For i=(ligne/3)*3 To ((ligne/3)*3)+2 
    For j.b=(colonne/3)*3 To ((colonne/3)*3)+2 
      If ((i<>ligne) And (j<>colonne) And (sudoku(i,j)\valeur <> 0)) 
        result$ + Str(sudoku(i,j)\valeur) 
      EndIf 
    Next j 
  Next i 
  ProcedureReturn result$ 
EndProcedure 

Procedure simplifierSudoku() ; trouve et met à jour les cases evidentes 
  ligne.b = 0 
  colonne.b = 0 
  While((ligne<9)) 
    If (sudoku(ligne,colonne)\valeur = 0) 
      valeursImpossibles.s = listeValeursEnPrise(ligne,colonne) ; les valeurs que ne peut pas prendre la case en cours 
      While Len(valeursImpossibles)>0 
        sudoku(ligne,colonne)\valeursPossibles=RemoveString(sudoku(ligne,colonne)\valeursPossibles,Left(valeursImpossibles,1)) 
        valeursImpossibles = RemoveString(valeursImpossibles,Left(valeursImpossibles,1)) 
      Wend 
      If(Len(sudoku(ligne,colonne)\valeursPossibles)=1) ; on a trouvé la valeur définitive de cette case 
        sudoku(ligne,colonne)\valeur = Val(Left(sudoku(ligne,colonne)\valeursPossibles,1)) 
        ligne = 0 
        colonne = -1 
      EndIf 
    EndIf 
    colonne + 1 
    If colonne = 9 
      colonne = 0 
      ligne + 1 
    EndIf 
  Wend 
EndProcedure 

Procedure.b resoudreParBackTracking(ligne.b, colonne.b) ; resoud le sudoku en utilisant le backtracking 
  If (ligne = 9) 
    ProcedureReturn 1 
  EndIf 
  If (sudoku(ligne, colonne)\valeur = 0) 
    ;Debug "Zero at : " + Str(ligne) + Str(colonne) 
    i.b=1 
    trouve.b=0 
    While ((i < (Len(sudoku(ligne, colonne)\valeursPossibles)) + 1) And (trouve = 0)) 
      If ((FindString(listeValeursEnPrise(ligne,colonne),Mid(sudoku(ligne,colonne)\valeursPossibles,i,1),1)) = 0) 
        sudoku(ligne,colonne)\valeur = Val(Mid(sudoku(ligne,colonne)\valeursPossibles,i,1)) 
        colonne + 1 
        If colonne = 9 
          colonne = 0 
          ligne + 1 
        EndIf 
        trouve=resoudreParBackTracking(ligne, colonne) 
        If (trouve = 0) 
          colonne = colonne - 1 
          If colonne = -1 
            colonne = 8 
            ligne = ligne -1 
          EndIf 
          If ligne <> -1 
            sudoku(ligne,colonne)\valeur = 0 
          Else 
            ProcedureReturn 0 
          EndIf 
        EndIf 
      EndIf 
      i + 1 
    Wend 
    ProcedureReturn trouve 
  Else ; la case n'est pas vide : sa valeur est imposée 
    colonne + 1 
    If colonne = 9 
      colonne = 0 
      ligne + 1 
    EndIf 
    ProcedureReturn resoudreParBackTracking(ligne, colonne) 
  EndIf 
EndProcedure 

Open_sudoku() 
Repeat 
  
  Event = WaitWindowEvent() 
  
  If Event = #PB_Event_Gadget 
    GadgetID = EventGadget() 
    If GadgetID = #Button_OK 
      
      DisableGadget(#Button_OK, 1) 
      SetGadgetText(#Button_OK,"Finding a solution...") 
      initialiser() 
      ligne.b = 0 
      colonne.b = 0 
      
      ; on rentre les valeurs des gadget dans le tableau 
      For i=#String_00 To #String_88 
        If GetGadgetText(i) <> "" 
          sudoku(ligne,colonne)\valeur = Val(GetGadgetText(i)) 
        EndIf 
        colonne + 1 
        If colonne = 9 
          colonne = 0 
          ligne + 1 
        EndIf 
      Next i 
      
      ; verifier si il y a aucune aberration dans les chiffres donnés par l'utilisateur 
      verif.b = 0 
      For ligne=0 To 8 
        For colonne=0 To 8 
          If (sudoku(ligne,colonne)\valeur <> 0) And (FindString(listeValeursEnPrise(ligne,colonne),Str(sudoku(ligne,colonne)\valeur), 1) <> 0) 
            verif = 1 
          EndIf 
        Next colonne 
      Next ligne 
      If verif = 1 
        MessageRequester("Sudoku impossible !!!", "The solution of this Sudoku cannot be found.", #MB_OK|#MB_ICONERROR) 
      Else 
        
        Debut = ElapsedMilliseconds() 
        
        ; on commence par simplifier rapidement le sudoku, pour que l'éventuel backtracking qui suivra soit plus rapide 
        ; certains sudoku très simple seront résolus sans backtracking 
        simplifierSudoku() 
        ; si il n'est pas résolu après cette simplification, on lance le backtracking 
        If estResolu() = 0 
          resoudreParBackTracking(0,0) 
          message.s = "Solution found in " + Str(ElapsedMilliseconds() - Debut) + " milliseconds." 
        Else 
          message.s = "Solution found in " + Str(ElapsedMilliseconds() - Debut) + " milliseconds." 
        EndIf 
        
        ; on écrit les valeurs du tableau dans les gadgets 
        ligne = 0 
        colonne = 0 
        For i=#String_00 To #String_88 
          If sudoku(ligne, colonne)\valeur <>0 
            SetGadgetText(i,Str(sudoku(ligne, colonne)\valeur)) 
          EndIf 
          colonne + 1 
          If colonne = 9 
            colonne = 0 
            ligne + 1 
          EndIf 
        Next i 
        MessageRequester("Solution found !", message, #MB_OK|#MB_ICONINFORMATION) 
      EndIf 
      DisableGadget(#Button_OK, 0) 
      SetGadgetText(#Button_OK,"Find a solution") 
      
    ElseIf GadgetID = #Button_Clear 
      For i=#String_00 To #String_88 
        SetGadgetText(i, "") 
      Next i 
      
    ElseIf ((GadgetID >= #String_00) And (GadgetID <= #String_88)) 
      verifier(GadgetID) 
    EndIf 
  EndIf 
  
Until Event = #PB_Event_CloseWindow

End
PB
PureBasic Expert
PureBasic Expert
Posts: 7581
Joined: Fri Apr 25, 2003 5:24 pm

Re: Sudoku solution finder

Post by PB »

Nice!
I compile using 5.31 (x86) on Win 7 Ultimate (64-bit).
"PureBasic won't be object oriented, period" - Fred.
User avatar
Michael Vogel
Addict
Addict
Posts: 2811
Joined: Thu Feb 09, 2006 11:27 pm
Contact:

Post by Michael Vogel »

Cool :P

If you are a fan of Sudoku, feel free to play my program downloading it from http://sudokuprogram.googlepages.com/ (Windows only)
Post Reply