Un solveur de Sudoku

Programmation d'applications complexes
Répondre
ATHOW
Messages : 226
Inscription : mer. 29/déc./2004 16:54

Un solveur de Sudoku

Message par ATHOW »

Salut à tous,

N'ayant pas supporté la résistance d'un Sudoku hier, j'ai planché aujourd'hui sur un solveur de sudoku qui permettrait de trouver le plus rapidement possible une solution à toutes ces vilaines grilles.

J'ai vu que certains d'entre vous ont déjà proposé des solveurs étape-par-étape, et même une lib, mais moi, je voulais juste un programme ultra-simpliste qui me dit la solution et ai donc écrit ceci :

Code : Tout sélectionner

; Sudoku Killer, solveur de sudoku utilisant une sorte de backtracking
; 14/02/06 Guillaume HUSSON
; PB 3.94

; 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

; Ouvre la fenetre principale
Procedure Open_sudoku()
  If OpenWindow(#sudoku, 0, 0, 390, 430,  #PB_Window_SystemMenu | #PB_Window_TitleBar | #PB_Window_MinimizeGadget | #PB_Window_ScreenCentered , "Sudoku Killer | © Guillaume HUSSON")
    CreateImage(#TraitHorizontal, 383, 1); crée un trait noir horizontal
    CreateImage(#TraitVertical, 1,383) ; crée un trait noir vertical
    If CreateGadgetList(WindowID())
      ; les "traits" :
      ImageGadget(#TraitHorizontal0, 4, 4, 390, 1, UseImage(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal1, 4, 5, 390, 1, UseImage(#TraitHorizontal))
      ImageGadget(#TraitHorizontal2, 4, 6, 390, 1, UseImage(#TraitHorizontal))
      
      ImageGadget(#TraitHorizontal3, 4, 45, 390, 1, UseImage(#TraitHorizontal))
      ImageGadget(#TraitHorizontal4, 4, 85, 390, 1, UseImage(#TraitHorizontal))
      
      ImageGadget(#TraitHorizontal5, 4, 129, 390, 1, UseImage(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal6, 4, 130, 390, 1, UseImage(#TraitHorizontal))
      ImageGadget(#TraitHorizontal7, 4, 131, 390, 1, UseImage(#TraitHorizontal))
      
      ImageGadget(#TraitHorizontal8, 4, 175, 390, 1, UseImage(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal9, 4, 215, 390, 1, UseImage(#TraitHorizontal))
      
      ImageGadget(#TraitHorizontal10, 4, 259, 390, 1, UseImage(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal11, 4, 260, 390, 1, UseImage(#TraitHorizontal))
      ImageGadget(#TraitHorizontal12, 4, 261, 390, 1, UseImage(#TraitHorizontal))
      
      ImageGadget(#TraitHorizontal13, 4, 305, 390, 1, UseImage(#TraitHorizontal))
      ImageGadget(#TraitHorizontal14, 4, 345, 390, 1, UseImage(#TraitHorizontal))
      
      ImageGadget(#TraitHorizontal15, 4, 384, 390, 1, UseImage(#TraitHorizontal)) 
      ImageGadget(#TraitHorizontal16, 4, 385, 390, 1, UseImage(#TraitHorizontal))
      ImageGadget(#TraitHorizontal17, 4, 386, 390, 1, UseImage(#TraitHorizontal))
      
      ImageGadget(#TraitVertical0, 4, 4, 390, 1, UseImage(#TraitVertical)) 
      ImageGadget(#TraitVertical1, 5, 4, 390, 1, UseImage(#TraitVertical))
      ImageGadget(#TraitVertical2, 6, 4, 390, 1, UseImage(#TraitVertical))
      
      ImageGadget(#TraitVertical3, 45, 4, 390, 1, UseImage(#TraitVertical))
      ImageGadget(#TraitVertical4, 85, 4, 390, 1, UseImage(#TraitVertical))
      
      ImageGadget(#TraitVertical5, 129, 4, 390, 1, UseImage(#TraitVertical)) 
      ImageGadget(#TraitVertical6, 130, 4, 390, 1, UseImage(#TraitVertical))
      ImageGadget(#TraitVertical7, 131, 4, 390, 1, UseImage(#TraitVertical))
      
      ImageGadget(#TraitVertical8, 175, 4, 390, 1, UseImage(#TraitVertical)) 
      ImageGadget(#TraitVertical9, 215, 4, 390, 1, UseImage(#TraitVertical))
      
      ImageGadget(#TraitVertical10, 259, 4, 390, 1, UseImage(#TraitVertical)) 
      ImageGadget(#TraitVertical11, 260, 4, 390, 1, UseImage(#TraitVertical))
      ImageGadget(#TraitVertical12, 261, 4, 390, 1, UseImage(#TraitVertical))
      
      ImageGadget(#TraitVertical13, 305, 4, 390, 1, UseImage(#TraitVertical))
      ImageGadget(#TraitVertical14, 345, 4, 390, 1, UseImage(#TraitVertical))
      
      ImageGadget(#TraitVertical15, 384, 4, 390, 1, UseImage(#TraitVertical)) 
      ImageGadget(#TraitVertical16, 385, 4, 390, 1, UseImage(#TraitVertical))
      ImageGadget(#TraitVertical17, 386, 4, 390, 1, UseImage(#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)
      
      ; les boutons
      ButtonGadget(#Button_OK, 85, 393, 110, 30, "Trouver une solution")
      ButtonGadget(#Button_Clear, 200, 393, 110, 30, "Effacer la grille") 
    EndIf
  EndIf
EndProcedure

; dans un case, il y a une valeur (0 si elle n'a pas été découverte)
; et une liste de valeurs possibles, représentée par une chaine de caractère
; exemple, si la case peut etre un 4, un 2 ou un 6, cette chaine sera "426"
Structure element
  valeur.b
  valeursPossibles$.s
EndStructure

; le tableau représentant le sudoku
Dim sudoku.element(9,9)

Procedure initialiser() ; initialise le 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() ; renvoie 1 si le sudoku est resolu, 0 sinon
  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$ = 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$ = 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$ = 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 = colonne + 1
    If colonne = 9
      colonne = 0
      ligne = 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 "la case est vide : " + 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 = colonne + 1
        If colonne = 9
          colonne = 0
          ligne = 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 = i + 1
    Wend
    ProcedureReturn trouve
  Else ; la case n'est pas vide : sa valeur est imposée
    colonne = colonne + 1
    If colonne = 9
      colonne = 0
      ligne = ligne + 1
    EndIf
    ProcedureReturn resoudreParBackTracking(ligne, colonne)
  EndIf
EndProcedure

Open_sudoku()
Repeat
  
  Event = WaitWindowEvent()
  
  If Event = #PB_EventGadget 
    GadgetID = EventGadgetID()
    If GadgetID = #Button_OK
      
      DisableGadget(#Button_OK, 1)
      SetGadgetText(#Button_OK,"Recherche...")
      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 = colonne + 1
        If colonne = 9
          colonne = 0
          ligne = 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 !!!", "La solution de ce Sudoku est introuvable.", #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 trouvée en " + Str(ElapsedMilliseconds() - Debut) + " millisecondes."
        Else
          message$.s = "Solution trouvée en " + Str(ElapsedMilliseconds() - Debut) + " millisecondes."
        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 = colonne + 1
          If colonne = 9
            colonne = 0
            ligne = ligne + 1
          EndIf
        Next i
        MessageRequester("Solution trouvée !", message, #MB_OK|#MB_ICONINFORMATION)
      EndIf
      DisableGadget(#Button_OK, 0)
      SetGadgetText(#Button_OK,"Trouver une 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_EventCloseWindow

End
C'est simple, on rentre les chiffres donnés par le journal ou autre, on clique sur "Trouver une solution", et c'est fini !
Résultat : la grille qui m'a cassé les dents hier a été trouvé en 30 millisecondes. Je sais qu'il n'y a aucun intéret à avoir une solution sans savoir d'où elle sort, mais on a tous le droit de faire des trucs sans intéret, non ?

Non ?
Haut
CameleonTH
Messages : 333
Inscription : sam. 25/juin/2005 11:18
Localisation : Laon (02)
Contact :
Contacter CameleonTH

Message par CameleonTH »

Ton programme est trés bien fait est trés puissant, félicitation.
Méme si je sais pas jouer au Sudoku j'ai tester avec le jeux et sa marche impecable.

Alor vraiment félicitation.
Haut
nico
Messages : 3702
Inscription : ven. 13/févr./2004 0:57

Message par nico »

Je viens de le tester, il à l'air de bien fonctionner, félicitation. :P
Haut
mangatome
Messages : 80
Inscription : mer. 29/déc./2004 13:19
Contact :
Contacter mangatome

Message par mangatome »

Excellent, ça fonctionne nickel.
Le truc pas mal a ajouter (et assez simple) ça serait de mettre en couleur les solutions trouvées (ou en gras).
http://www.cybisoft.net - mes jeux, mods, tools en PB et autres languages :)
Haut
Frenchy Pilou
Messages : 2194
Inscription : jeu. 27/janv./2005 19:07

Message par Frenchy Pilou »

Bigre il trouve même une solution quand il n'y a rien dans les les cases !
(Bon d'accord c'est toujours la même, mais quand même c'est trop fort ! )

Killer c'est le mot ! 16 millisecondes cela fuse un max!

http://www.angusj.com/sudoku/index.php était bien sympathique mais rouspetait quand il y avait trop de possibilités ! :D
(J'ai pas encore tout compris de ses résolutions à base de couleurs :(


Chapeau bas pour l'algo ! Et en une journée, c'est quasiment un exploit ! 8O 8O 8O
Bravo ! 8)

(on pourrait avoir le nombre de tests effectués pour trouver une résolution ? )
Juste à titre indicatif pour avoir le vertige s'il fallait le faire à la main :)

Comme quoi on ne peut lutter contre une machine bien programmée ! :lol:

Un petit "jeu de go" maintenant ? :)
Ca c'est un challenge qui tape !

http://purebasic.hmt-forum.com/viewtopi ... =jeu+de+go :roll:
Est beau ce qui plaît sans concept :)
Speedy Galerie
Haut
ATHOW
Messages : 226
Inscription : mer. 29/déc./2004 16:54

Message par ATHOW »

Merci à tous !

En fait je n'ai pas beaucoup de mérite : je n'ai fais que retrancrire un algo qu'un de mes profs d'algo m'a enseigné pour un autre jeu (le rétroparcours, pour trouver une solution au problème des huit reines, certains doivent connaitre... C'est moins passionant que le SudoKu...).

C'est vrai que je m'attendais pas à ce que ça aille si vite...
Le truc pas mal a ajouter (et assez simple) ça serait de mettre en couleur les solutions trouvées (ou en gras).
Ca serait pas mal... mais je ne sais pas comment coloriser les Gadgets... une lib peut etre ?
Un petit "jeu de go" maintenant ?
Ca c'est un challenge qui tape !
Je peux toujours essayer... Je vais jeter un oeil aux régles !

Il faut aussi que je fasse en Pure un vieil Abalone avec IA que j'avais fait en Pascal (et oui), en mode console (re et oui). Si ça intéresse quelqu'un...
Haut
Frenchy Pilou
Messages : 2194
Inscription : jeu. 27/janv./2005 19:07

Message par Frenchy Pilou »

Et avec 9 reines ou 10 ? :lol: :roll:
Là je suis sûr que cela ne marchera pas même en y mettant le temps :D
11 oui :roll:
Est beau ce qui plaît sans concept :)
Speedy Galerie
Haut
ATHOW
Messages : 226
Inscription : mer. 29/déc./2004 16:54

Message par ATHOW »

Pas la peine d'aller jusque 9 ou 10... 2 ou 3 reines ça marche déjà pas !
On l'avait généralisé à N reines... la fonction renvoyait false si c'était insolvable, et le résolvait et renvoyait true sinon.

Bref, je préfére le sudoku :)
Haut
Frenchy Pilou
Messages : 2194
Inscription : jeu. 27/janv./2005 19:07

Message par Frenchy Pilou »

Non non cela marche à partir de 11 pour les impairs pour 7 aussi :D
Est beau ce qui plaît sans concept :)
Speedy Galerie
Haut
ATHOW
Messages : 226
Inscription : mer. 29/déc./2004 16:54

Message par ATHOW »

Oui oui, je disais juste que le premier cas où ça ne marchait pas n'était pas 9 mais 2... Je me suis mal exprimé !

Pour en revenir au sudoku, mon killer a galéré avec celui-ci :

1 0 0 9 0 7 0 0 3
0 8 0 0 0 0 0 7 0
0 0 9 0 0 0 6 0 0
0 0 7 2 0 9 4 0 0
4 1 0 0 0 0 0 9 5
0 0 8 5 0 4 3 0 0
0 0 3 0 0 0 7 0 0
0 5 0 0 0 0 0 4 0
2 0 0 8 0 6 0 0 9


400 millisecondes...
Haut
CameleonTH
Messages : 333
Inscription : sam. 25/juin/2005 11:18
Localisation : Laon (02)
Contact :
Contacter CameleonTH

Message par CameleonTH »

Tant que sa marche c'est le principale.
Haut
Frenchy Pilou
Messages : 2194
Inscription : jeu. 27/janv./2005 19:07

Message par Frenchy Pilou »

400 millisecondes...
C'est moins d'une seconde non ?
Et à l'oeil on ne voit pas la différence :lol:
Est beau ce qui plaît sans concept :)
Speedy Galerie
Haut
mangatome
Messages : 80
Inscription : mer. 29/déc./2004 13:19
Contact :
Contacter mangatome

Message par mangatome »

Ca serait pas mal... mais je ne sais pas comment coloriser les Gadgets... une lib peut etre ?
Si je ne m'abuse, c'est une des grandes nouveautées de PB 4.0 ...
http://www.cybisoft.net - mes jeux, mods, tools en PB et autres languages :)
Haut
julien
Messages : 846
Inscription : ven. 30/janv./2004 15:06
Contact :
Contacter julien

Message par julien »

@ATHOW Bon boulot, il manque plus une algo pour remplir partiellement les cases et ainsi en faire un jeu complet !
Haut
rob6523
Messages : 1
Inscription : mer. 05/avr./2006 8:04

Message par rob6523 »

Et ici code pour PB 4.00

Code : Tout sélectionner

; Sudoku Killer, solveur de sudoku utilisant une sorte de backtracking 
; 14/02/06 Guillaume HUSSON 
; PB 4.00 adaption par René Brioul (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

; le tableau représentant le sudoku 
Global Dim sudoku.elements(9,9)

; Ouvre la fenetre principale 
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) 
      
      ; les boutons 
      ButtonGadget(#Button_OK, 85, 393, 110, 30, "Trouver une solution") 
      ButtonGadget(#Button_Clear, 200, 393, 110, 30, "Effacer la grille") 
    EndIf 
  EndIf 
EndProcedure 

; dans un case, il y a une valeur (0 si elle n'a pas été découverte) 
; et une liste de valeurs possibles, représentée par une chaine de caractère 
; exemple, si la case peut etre un 4, un 2 ou un 6, cette chaine sera "426" 


Procedure initialiser() ; initialise le 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() ; renvoie 1 si le sudoku est resolu, 0 sinon 
  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 "la case est vide : " + 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,"Recherche...") 
      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 !!!", "La solution de ce Sudoku est introuvable.", #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 trouvée en " + Str(ElapsedMilliseconds() - Debut) + " millisecondes." 
        Else 
          message.s = "Solution trouvée en " + Str(ElapsedMilliseconds() - Debut) + " millisecondes." 
        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 trouvée !", message, #MB_OK|#MB_ICONINFORMATION) 
      EndIf 
      DisableGadget(#Button_OK, 0) 
      SetGadgetText(#Button_OK,"Trouver une 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
Haut
Répondre

Revenir à « Applications »