En ce moment je travaille sur un programme qui devrait etre capable de reussir un sudoku tout seul.
Voici mon code en entier :
► Afficher le texte
Code : Tout sélectionner
#include <ButtonConstants.au3>
#include <EditConstants.au3>
#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>
#include <Array.au3>
; Chaines possibles pour l'import des valeurs :
; 050310020010698540800020000007040080045000910090050700000060007076235090030089050
Global $GrilleTest[9][9]
#Region Couleurs de l'interface
Global Const $SUDOKU_COLOR_OK = 0x0066FF, $SUDOKU_COLOR_KO = 0xFF6666, $SUDOKU_COLOR_NAN = 0xAAAAAA
#EndRegion
#Region Interface graphique générale
Local $GUI = GUICreate("Sudoku", 480, 363, 192, 132)
GUISetFont(12, 800, 0, "MS Mincho")
#EndRegion
#Region 9x9 cases à remplir du Sudoku
Global $matrice[9][9] , $resultatProvisoire[9][9]
; Pour chaque ligne et colonne
For $i=0 To 8
For $j=0 To 8
; Position [X,Y] pour les cases à remplir du sudoku
Local $x = 32+$i*32, $y = 40+$j*32
; Ajout d'un décalage de 10 px pour bien séparer les 3x3 blocs
$x += cond($i>2,10,0)+cond($i>5,10,0)
$y += cond($j>2,10,0)+cond($j>5,10,0)
$matrice[$i][$j] = GUICtrlCreateInput("", $x, $y, 25, 25, $ES_CENTER)
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_OK)
Next
Next
#EndRegion
#Region Boutons d'actions
$Button1 = GUICtrlCreateButton("Lancer", 368, 40, 91, 33, $WS_GROUP)
GUICtrlSetColor($Button1, $SUDOKU_COLOR_OK)
$Button2 = GUICtrlCreateButton("Importer", 368, 90, 91, 33, $WS_GROUP)
GUICtrlSetColor($Button2, $SUDOKU_COLOR_OK)
$Button3 = GUICtrlCreateButton("Remplir", 368, 140, 91, 33, $WS_GROUP)
GUICtrlSetColor($Button3, $SUDOKU_COLOR_OK)
;$Button4 = GUICtrlCreateButton ("B' T'",368,190,91,33,$WS_GROUP)
;GUICtrlSetColor($Button4, $SUDOKU_COLOR_OK)
;$Progress1 = GUICtrlCreateProgress(40, 0, 401, 33)
#EndRegion
#Region Pavé numérique pour l'affichage des valeurs possibles
Local $chiffres[9]
For $i=0 To 2
For $j=0 To 2
; Position [X,Y] pour les boutons du pavé numérique
Local $x = 368+$i*32, $y = 252+$j*32, $n=$i*3+$j
$chiffres[$n] = GUICtrlCreateButton($n+1, $x, $y, 25, 25, $ES_CENTER)
GUICtrlSetColor($chiffres[$n], $SUDOKU_COLOR_OK)
Next
Next
#EndRegion
GUISetState(@SW_SHOW)
Local $focus_previous[2] = [-1,-1]
#Region Traitement des messages de l'interface
While 1
Local $nMsg = GUIGetMsg()
Switch $nMsg
Case $GUI_EVENT_CLOSE
Exit
#region Buttons
#region Button 1
Case $Button1
; Récupération de la grille des valeurs
Local $grille = getGrille($matrice)
; $estValide est une matrice 9x9 contenant dans chaque case une séries de 3 caractères {_,L,C,B}
; $checkGrille est à True si toute la grille est correcte
Local $estValide = estValide($grille), $checkGrille = True
; Pour chaque ligne et colonne
For $i = 0 To 8
For $j = 0 To 8
; La case est correctement remplie si $estValide est égale à "___" en [$i,$j]
Local $checkCase = ($estValide[$i][$j]="___")
$checkGrille = $checkGrille And $checkCase
; Si $checkCase est à True, on met la case en bleu, sinon en rouge
GUICtrlSetColor($matrice[$i][$j], cond($checkCase,$SUDOKU_COLOR_OK,$SUDOKU_COLOR_KO))
Next
Next
; Message Traytip pour prévenir de l'état de la grille
TrayTip("Sudoku", cond($checkGrille,"Grille correcte", "Grille incorrecte"), 10, cond($checkGrille,1,3))
#endregion
#region Button 2
Case $Button2
; On demande une chaine de 81 caractères (M:obligatoire, 81:taille demandée)
Local $chaine = InputBox("Importer", "Entrez une chaine de 81 valeurs à importer"&@CRLF&"(1-9 pour les valeurs, 0 pour une valeur vide)", "", " M81")
; Si pas d'erreur, et 81 symboles entre 0 et 9, alors...
If Not @error And StringRegExp($chaine, "^[0-9]{81}$") Then
; On sépare chaque caractère de la chaine, on en fait un tableau $split indexé à partir de 0
Local $split = StringSplit($chaine,"",2)
; Pour chaque ligne et colonne
For $i = 0 To 8
For $j = 0 To 8
; la valeur à mettre en [$i,$j] dans $matrice est en $j+9*$i dans $split
Local $valeur = Number($split[$j+$i*9])
; Si la valeur n'est pas entre 1 et 9, on affiche la chaine vide
GUICtrlSetData($matrice[$i][$j], cond($valeur>0 And $valeur<10,$valeur,""))
; On considère que chaque case est correcte, couleur bleue
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_OK)
Next
Next
EndIf
#endregion
#region Button 3
Case $Button3
_resolution($matrice)
#endregion
#region Button 4
; Case $Button4
; backT(getGrille($matrice),0)
; #endregion
#region Buttons Chiffres
Case Else
; Liste des boutons du pavé numérique
For $i = 0 To 8
; Si on clique sur le bouton $i (Attention ! valeur du bouton:$i+1, car indexé de 0 à 8 pour les valeurs de 1 à 9)
If $nMsg = $chiffres[$i] Then
; Si le focus est gardé sur une case valide du Sudoku,
If $focus_previous[0]<>-1 And $focus_previous[1]<>-1 Then
; On affiche la valeur du bouton (GUICtrlRead($chiffres[$i])) dans la case du Sudoku correspondant ($matrice[$focus_previous[0]][$focus_previous[1]])
GUICtrlSetData($matrice[$focus_previous[0]][$focus_previous[1]], GUICtrlRead($chiffres[$i]))
EndIf
EndIf
Next
; Quel case a le focus?
Local $focus[2] = [-1,-1] ; [-1,-1] correspond aux coordonnées d'un bouton ayant le focus, mais qui ne fait pas partie des cases du Sudoku
; Pour chaque ligne et colonne
For $i = 0 To 8
For $j = 0 To 8
; Si la case en [$i,$j] a le focus, on l'enregistre
If isFocused($matrice[$i][$j],$GUI) Then
$focus[0]=$i
$focus[1]=$j
EndIf
Next
Next
; Si le focus a changé depuis la dernière fois (et qu'il est "valide", autrement dit que c'est bien une case du Sudoku)
If $focus[0]<>$focus_previous[0] Or $focus[1]<>$focus_previous[1] And $focus[0]<>-1 And $focus[1]<>-1 Then
; On enregistre dans $focus_previous la valeur actuelle, pour ne faire cette opération que si le focus change
$focus_previous = $focus
; Récupération de la grille des valeurs
Local $grille = getGrille($matrice)
; On récupère la liste des valeurs possibles
Local $possibilites = getValeursPossibles($grille, $focus[0],$focus[1])
; Pour chaque case du pavé
For $i = 0 To 8
; Si la valeur est disponible, on active le bouton, sinon on le désactive
GUICtrlSetState($chiffres[$i], cond($possibilites[$i],$GUI_ENABLE,$GUI_DISABLE))
Next
EndIf
#endregion
#endregion
EndSwitch
WEnd
#region estPossibleSurX
Func estPossibleSurLigne($grille, $x,$y, $val)
For $i = 0 To 8
If $i<>$x Then
Local $possibilites = getValeursPossibles($grille, $i,$y)
If $possibilites[$val-1] Then Return True
EndIf
Next
Return False
EndFunc
; Fonction de vérification des possibilités de le colonne
Func estPossibleSurColonne($grille, $x,$y, $val)
For $j = 0 To 8
If $j<>$y Then
Local $possibilites = getValeursPossibles($grille, $x,$j)
If $possibilites[$val-1] Then Return True
EndIf
Next
Return False
EndFunc
; Fonction de vérification des possibilités du bloc
Func estPossibleSurBloc($grille, $x,$y, $val)
Local $bloc[2]=[ _
cond($x>2,1,0)+cond($x>5,1,0), _
cond($y>2,1,0)+cond($y>5,1,0) _
]
For $i = 0+3*$bloc[0] To 2+3*$bloc[0]
For $j = 0+3*$bloc[1] To 2+3*$bloc[1]
If ($i<>$x Or $j<>$y) And $grille[$i][$j] = 0 Then
Local $possibilites = getValeursPossibles($grille, $i,$j)
If $possibilites[$val-1] Then Return True
EndIf
Next
Next
Return False
EndFunc
#endregion
; Fonction conditionnelle rapide
Func cond($cond, $true, $false)
If $cond Then Return $true
Return $false
EndFunc
; Fonction de comparaison de matrices
Func matrixEquals($m1,$m2)
; On teste d'abord les dimensions des deux matrices
For $d = 0 To 2
; Si différents, on retourne false
If UBound($m1,$d)<>UBound($m2,$d) Then Return False
Next
; Pour chaque ligne et colonne
For $i = 0 To UBound($m1,1)-1
For $j = 0 To UBound($m1,2)-1
; Si différents, on retourne false
If $m1[$i][$j]<>$m2[$i][$j] Then Return False
Next
Next
Return True
EndFunc
; Fonction de détection d'un état sur un controle
Func isState($control,$state)
Return BitAND(GUICtrlGetState($control),$state)=$state
EndFunc
; Fonction de détection du focus sur un controle
Func isFocused($control,$gui)
Return GUICtrlGetHandle($control) = ControlGetHandle($gui,"",ControlGetFocus($gui))
EndFunc
; Fonction de vérification de la grille
Func estValide($grille)
Local $resultat[9][9]
; Pour chaque ligne et colonne
For $i = 0 To 8
For $j = 0 To 8
Local $case = "___"
; On ne vérifie que les cases dont la valeur est entre 1 et 9
If StringRegExp($grille[$i][$j]&"", "^[1-9]$") Then
$case = _
cond(estValideSurLigne($grille, $i,$j),"_","L") & _
cond(estValideSurColonne($grille, $i,$j),"_","C") & _
cond(estValideSurBloc($grille, $i,$j),"_","B")
EndIf
$resultat[$i][$j] = $case
Next
Next
Return $resultat
EndFunc
; Fonction de récupération des valeurs de la grille (chiffres entre 0 et 9)
Func getGrille($matrice)
Local $grille[9][9]
For $i=0 To 8
For $j=0 To 8
$grille[$i][$j] = Number(GUICtrlRead($matrice[$i][$j]))
If Not StringRegExp($grille[$i][$j]&"", "^[1-9]$") Then $grille[$i][$j] = 0
Next
Next
Return $grille
EndFunc
#region estValideXXX
; Fonction de vérification des lignes
Func estValideSurLigne($grille, $x,$y)
Local $valeur = $grille[$x][$y]
For $i = 0 To 8
; Si $valeur est présente sur la ligne (ailleurs qu'en [$x,$y]), on retourne False
If $i<>$x And $grille[$i][$y]=$valeur Then
Return False
EndIf
Next
Return True
EndFunc
; Fonction de vérification des lignes
Func estValideSurColonne($grille, $x,$y)
Local $valeur = $grille[$x][$y]
For $j = 0 To 8
; Si $valeur est présente sur la colonne (ailleurs qu'en [$x,$y]), on retourne False
If $j<>$y And $grille[$x][$j]=$valeur Then
Return False
EndIf
Next
Return True
EndFunc
; Fonction de vérification des lignes
Func estValideSurBloc($grille, $x,$y)
; On détecte le bloc concerné par la valeur [$x,$y] ($bloc est un couple dont chaque valeur est entre 0 et 2)
Local $bloc[2]=[ _
cond($x>2,1,0)+cond($x>5,1,0), _
cond($y>2,1,0)+cond($y>5,1,0) _
]
; Pour chaque ligne et colonne de ce bloc
For $i = 0+3*$bloc[0] To 2+3*$bloc[0]
For $j = 0+3*$bloc[1] To 2+3*$bloc[1]
; Si $valeur est présente sur le bloc (ailleurs qu'en [$x,$y]), on retourne False
If ($i<>$x Or $j<>$y) And $grille[$i][$j]=$grille[$x][$y] Then
Return False
EndIf
Next
Next
Return True
EndFunc
#endregion
; Fonction de récupération des valeurs possibles pour une case donnée
Func getValeursPossibles($grille, $i,$j)
Local $resultat[9]
; Pour chaque valeur possible (de 1 à 9, dans un tableau indexé de 0 à 8)
For $n = 0 To 8
; Par défaut, $resultat[$n] = True, c'est à dire que la valeur est disponible
$resultat[$n] = True
; On ne teste les valeurs possibles que si les valeurs $i et $j correspondent à un focus valide
If $i<>-1 And $j<>-1 Then
; $n = 0 à 8, dont la valeur à traiter $val (qui est entre 1 et 9) est $n+1
; On détecte le bloc concerné par la valeur [$i,$j] ($bloc est un couple dont chaque valeur est entre 0 et 2)
Local $val = $n+1, $bloc[2]=[ _
cond($i>2,1,0)+cond($i>5,1,0), _
cond($j>2,1,0)+cond($j>5,1,0) _
]
; On vérifie sur la ligne concernée que la valeur n'apparait pas ailleurs qu'en [$i,$j]
For $x = 0 To 8
If $x<>$j And $grille[$i][$x] = $val Then $resultat[$n] = False
Next
; On vérifie sur la colonne concernée que la valeur n'apparait pas ailleurs qu'en [$i,$j]
For $x = 0 To 8
If $x<>$i And $grille[$x][$j] = $val Then $resultat[$n] = False
Next
; On vérifie sur le bloc concerné que la valeur n'apparait pas ailleurs qu'en [$i,$j]
For $x = 0+3*$bloc[0] To 2+3*$bloc[0]
For $y = 0+3*$bloc[1] To 2+3*$bloc[1]
If $x<>$i And $y<>$j And $grille[$x][$y] = $val Then $resultat[$n] = False
Next
Next
Else
; Pour les valeurs ayant des coordonnées invalides, on retourne False
$resultat[$n] = False
EndIf
Next
Return $resultat
EndFunc
Func _resolution($grillade, $option = 0,$grilleatest = 0)
; Récupération de la grille des valeurs
If $option = 0 Then
Do
Local $grille = getGrille($grillade)
Local $grille_avant = getGrille($grillade)
_resoudre1( $grille)
; On recalcule la grille une fois modifiée
Local $grille_apres = getGrille($grillade)
; Tant que la grille change entre le début de l'opération ($grille) et la fin ($grille_apres), on recommence
Until matrixEquals($grille_avant,$grille_apres)
EndIf
If $option <> 0 Then
Do
; On recalcule la grille une fois modifiée
Local $grille_apres = _resoudre1( $grillade,1)
; Tant que la grille change entre le début de l'opération ($grille) et la fin ($grille_apres), on recommence
Until $grille_apres = False
EndIf
; 1er cas: résolution incoplete
if not _estTotalementRemplie(getGrille($matrice)) then
_resoudre(getgrille($matrice))
else
return true
endif
; 2e cas résolution complete
EndFunc
Func _resoudre1 ($grille,$option = 0)
Local $grille_avant2[9][9]
$grille_avant2= $grille
For $i = 0 To 8
For $j = 0 To 8
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $grille[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles, $found correspond au nombre de valeurs possibles, et $val à la valeur possible la plus haute
Local $possibilites = getValeursPossibles($grille, $i,$j), $found=0, $val=-1
; On compte
For $k = 0 to 8
If $possibilites[$k] Then
$found=$found+1
$val=$k+1
EndIf
Next
; Si une seule valeur possible ($found = 1), on affiche $val dans la case correspondante
If $found = 1 Then
$grille[$i][$j] = $val
If $option = 0 Then
GUICtrlSetData($matrice[$i][$j],$val)
EndIf
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
If $grille[$i][$j] = 0 Then
For $k = 0 To 8
;on regarde si la valeur n'est possible qu'une fois sur la ligne
If $possibilites[$k] and Not estPossibleSurLigne($grille,$i,$j,$k+1) Then
$grille[$i][$j] = $k+1
If $option = 0 Then
GUICtrlSetData($matrice[$i][$j],$k+1)
EndIf
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
;on regarde si la valeur n'est possible qu'une fois dans le bloc
If $possibilites[$k] And Not estPossibleSurBloc($grille,$i,$j,$k+1) Then
$grille[$i][$j] = $k + 1
If $option = 0 Then
GUICtrlSetData($matrice[$i][$j],$k+1)
EndIf
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
;on regarde si la valeur n'est possible qu'une fois sur la colone
If $possibilites[$k] and Not estPossibleSurColonne ($grille,$i,$j,$k+1) Then
$grille[$i][$j] = $k+1
If $option = 0 Then
GUICtrlSetData($matrice[$i][$j],$k+1)
EndIf
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
Next
EndIf
EndIf
Next
Next
If $grille_avant2 <> $grille Then
Return False
Else
Return True
EndIf
EndFunc
Func _resoudre ($grille)
$GrilleTest = _scinderGrilles ($grille,$GrilleTest)
For $i = 0 To 8
For $j = 0 To 8
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $GrilleTest[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles, $found correspond au nombre de valeurs possibles, et $val à la valeur possible la plus haute
Local $possibilites = getValeursPossibles($GrilleTest, $i,$j), $found=0, $val=-1
; On compte
For $k = 0 to 8
If $possibilites[$k] Then
$GrilleTest[$i][$j] = $k + 1
GUICtrlSetData($matrice[$i][$j],$k+1)
#region algorithme 1
do
$grille_debut = $grilleTest
For $i = 0 To 8
For $j = 0 To 8
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $grilleTest[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles, $found correspond au nombre de valeurs possibles, et $val à la valeur possible la plus haute
Local $possibilites = getValeursPossibles($grilletest, $i,$j), $found=0, $val=-1
; On compte
For $k = 0 to 8
If $possibilites[$k] Then
$found=$found+1
$val=$k+1
EndIf
Next
; Si une seule valeur possible ($found = 1), on affiche $val dans la case correspondante
If $found = 1 Then
$grilletest[$i][$j] = $val
GUICtrlSetData($matrice[$i][$j],$val)
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
If $grille[$i][$j] = 0 Then
For $k = 0 To 8
;on regarde si la valeur n'est possible qu'une fois sur la ligne
If $possibilites[$k] and Not estPossibleSurLigne($grille,$i,$j,$k+1) Then
$grilletest[$i][$j] = $k+1
GUICtrlSetData($matrice[$i][$j],$k+1)
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
;on regarde si la valeur n'est possible qu'une fois dans le bloc
If $possibilites[$k] And Not estPossibleSurBloc($grille,$i,$j,$k+1) Then
$grilletest[$i][$j] = $k + 1
GUICtrlSetData($matrice[$i][$j],$k+1)
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
;on regarde si la valeur n'est possible qu'une fois sur la colone
If $possibilites[$k] and Not estPossibleSurColonne ($grille,$i,$j,$k+1) Then
$grilletest[$i][$j] = $k+1
GUICtrlSetData($matrice[$i][$j],$k+1)
;une fois remplit plus besoin de continuer à chercher dans cette case
ExitLoop
EndIf
Next
EndIf
EndIf
Next
Next
Until matrixequals($grille_debut,$grilletest)
_resoudre($GrilleTest)
if _esttotalementremplie($grilletest) then
return true
endif
#end-region
EndIf
Next
EndIf
Next
Next
EndFunc
Func _estTotalementRemplie($grille)
For $i = 0 to 8
for $j = 0 to 8
If $grille[$i][$j] = 0 then return False
Next
Next
return True
EndFunc
Func _estValideBis($grille)
Local $estValide = estValide($grille)
; Pour chaque ligne et colonne
For $i = 0 To 8
For $j = 0 To 8
If $estValide[$i][$j]<>"____" Then
Return False
EndIf
Next
Next
Return True
EndFunc
Func _remplirGrille($grille)
For $i = 0 to 8
For $j = 0 to 8
If $grille[$i][$j] <> 0 Then
GUICtrlSetData($matrice[$i][$j],$grille[$i][$j])
EndIf
Next
Next
EndFunc
Func _scinderGrilles($grille1,$grille2)
For $i = 0 to 8
For $j = 0 to 8
If $grille2[$i][$j] = 0 Then
$grille2[$i][$j] = $grille1[$i][$j]
EndIf
Next
Next
Return $grille2
EndFunc
)
