Il s'agit d'un code que j'ai conçu à partir d'une demande de Guitarist, mais d'un tout autre acabit. Le but étant de résoudre de façon certaine une grille pré-remplie à laquelle il n'existe qu'une seule possibilité. L'interface graphique est adaptée de celle fournie par Guitarist avec Koda, mais entièrement repensée afin de gérer des Sudokus de taille 3x2², 3x3² (taille classique, de 1 à 9), 4x3² (de 1 à 9 et A, B et C) ... jusque 7x5 (1 à 9 et A à Z, pas d'autre caractère potable sous la main ^^).
► Afficher le texteRésolveur de Sudoku
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 :
; 9x9 Facile = 050310020010698540800020000007040080045000910090050700000060007076235090030089050
; 9x9 Débutant = 000400000570000103210605000390080200000701000007020016000802079905000082000009000
; 9x9 Confirmé = 005000601000700000780061900300500000059040030000100006007006120810009007500200800
; 9x9 Difficile = 002300007809000005005009046000003000090127600007480000000572013070940000540800000
; 9x9 Expert = 003040057908060200001350600800700400000008500000014002000430800410080320000000000
; 9x9 Tentative = 400081000007200980080060000700005000103000507000100002000070060094006200000450003
#Region Système d'arrêt du programme
Global $stop = False
HotKeySet("#{F4}","stop")
Func stop()
If $stop Then Exit
$stop = True
EndFunc
Global $vide[1][2] = [[0,""]]
#EndRegion
#Region Comportement du programme
Global $SUDOKU_DIMENSION[3] = [9,3,3]
Global Const $SUDOKU_TITRE = "Sudoku"
Global Const $SUDOKU_SYMBOLES[36] = ["" _
,"1","2","3","4","5","6","7" _
,"8","9","A","B","C","D","E" _
,"F","G","H","I","J","K","L" _
,"M","N","O","P","Q","R","S" _
,"T","U","V","W","X","Y","Z" _
]
; Dimension du sudoku trop grande, ajoutez des symboles
If $SUDOKU_DIMENSION[0] >= UBound($SUDOKU_SYMBOLES) Then Exit
; Dimensions non conforme, le premier nombre est le produit des deux autres
If $SUDOKU_DIMENSION[0] <> $SUDOKU_DIMENSION[1]*$SUDOKU_DIMENSION[2] Then Exit
Global Const $SUDOKU_MIDDLE = 20+$SUDOKU_DIMENSION[0]*32-32+Floor(($SUDOKU_DIMENSION[0]-1)/$SUDOKU_DIMENSION[1])*10+25+20-10
#EndRegion
#Region Couleurs de l'interface
Global Const $SUDOKU_COLOR_OK = 0x0066FF, $SUDOKU_COLOR_KO = 0xFF6666, $SUDOKU_COLOR_NAN = 0xAAAAAA
Global Const $SUDOKU_BKCOLOR_NO = 0xFFFFFF, $SUDOKU_BKCOLOR_YES = 0xAAAAAA
#EndRegion
#Region Interface graphique générale
Local $GUI_size[2] = [ _
$SUDOKU_MIDDLE + 10 + ($SUDOKU_DIMENSION[1]-1)*32+25 + 20 _
, _
20 + $SUDOKU_DIMENSION[0]*32-32+Floor(($SUDOKU_DIMENSION[0]-1)/$SUDOKU_DIMENSION[2])*10+25 + 20 + 25 + 20 _
]
Local $GUI = GUICreate("Sudoku", $GUI_size[0], $GUI_size[1], -1, -1, BitOR($WS_POPUP,$WS_BORDER))
GUISetFont(12, 800, 0, "MS Mincho")
#EndRegion
#Region Cases à remplir du Sudoku
Global $matrice[$SUDOKU_DIMENSION[0]][$SUDOKU_DIMENSION[0]]
; Pour chaque ligne et colonne
For $i=0 To $SUDOKU_DIMENSION[0]-1
For $j=0 To $SUDOKU_DIMENSION[0]-1
; Position [X,Y] pour les cases à remplir du sudoku
Local $x = 20+$i*32, $y = 20+$j*32
; Ajout d'un décalage de 10 px pour bien séparer les $SUDOKU_DIMENSION[1]x$SUDOKU_DIMENSION[2] blocs
$x += Floor($i/$SUDOKU_DIMENSION[1])*10
$y += Floor($j/$SUDOKU_DIMENSION[2])*10
$matrice[$i][$j] = GUICtrlCreateInput($SUDOKU_SYMBOLES[0], $x, $y, 25, 25, $ES_CENTER)
GUICtrlSetLimit($matrice[$i][$j], 1)
GUICtrlSetBkColor($matrice[$i][$j], $SUDOKU_BKCOLOR_NO)
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_OK)
Next
Next
#EndRegion
#Region Boutons d'actions
$Bouton_Quitter = GUICtrlCreateButton("Quitter", $SUDOKU_MIDDLE+10, 20, ($SUDOKU_DIMENSION[1]-1)*32+25, 33, $WS_GROUP)
GUICtrlSetColor($Bouton_Quitter, $SUDOKU_COLOR_OK)
$Bouton_Importer = GUICtrlCreateButton("Importer", $SUDOKU_MIDDLE+10, 63, ($SUDOKU_DIMENSION[1]-1)*32+25, 33, $WS_GROUP)
GUICtrlSetColor($Bouton_Importer, $SUDOKU_COLOR_OK)
$Bouton_Resoudre = GUICtrlCreateButton("Résoudre", $SUDOKU_MIDDLE+10, 106, ($SUDOKU_DIMENSION[1]-1)*32+25, 33, $WS_GROUP)
GUICtrlSetColor($Bouton_Resoudre, $SUDOKU_COLOR_OK)
#EndRegion
#Region Pavé numérique pour l'affichage des valeurs possibles
Local $chiffres[$SUDOKU_DIMENSION[0]+1] = [$SUDOKU_DIMENSION[0]]
For $i=0 To $SUDOKU_DIMENSION[1]-1
For $j=0 To $SUDOKU_DIMENSION[2]-1
; Position [X,Y] pour les boutons du pavé numérique
Local _
$x = $SUDOKU_MIDDLE+10 + $i*32, _
$y = $GUI_size[1]-20-20-20-25-32*($SUDOKU_DIMENSION[2]-1)+$j*32, _
$n=$j+$i*$SUDOKU_DIMENSION[2]+1
$chiffres[$n] = GUICtrlCreateButton($SUDOKU_SYMBOLES[$n], $x, $y, 25, 25, $ES_CENTER)
GUICtrlSetColor($chiffres[$n], $SUDOKU_COLOR_OK)
Next
Next
#EndRegion
#Region Pavé numérique pour l'affichage des valeurs possibles
Global $Label_Infos = GUICtrlCreateLabel("", 20, $GUI_size[1]-20-20, $GUI_size[0]-20-20, 20, 0x01) ; $SS_CENTER = 0x01
GUICtrlSetFont($Label_Infos, 11, 800, 0, "MS Mincho")
#EndRegion
GUISetState(@SW_SHOW)
Local $focus_previous[2] = [-1,-1]
#Region Traitement des messages de l'interface
While Not $stop
Local $nMsg = GUIGetMsg()
Switch $nMsg
Case $GUI_EVENT_CLOSE, $Bouton_Quitter
$stop = True
Case $Bouton_Importer
; On demande une chaine de XX caractères ; (M:obligatoire, XX:taille demandée=$SUDOKU_DIMENSION[0]*$SUDOKU_DIMENSION[0])
Local $taille = $SUDOKU_DIMENSION[0]*$SUDOKU_DIMENSION[0]
Local $chaine = InputBox("Importer", "Entrez une chaine de "&$taille&" valeurs à importer"&@CRLF&"(0 pour une valeur vide)", "", " M"&$taille)
; Si pas d'erreur, et XX symboles entre 0 et $SUDOKU_DIMENSION[0], alors...
If Not @error And StringRegExp($chaine, "^(0|"&joinArray($SUDOKU_SYMBOLES,"|",True)&"){"&$taille&"}$") 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 $SUDOKU_DIMENSION[0]-1
For $j = 0 To $SUDOKU_DIMENSION[0]-1
; la valeur à mettre en [$i,$j] dans $matrice est en $j+$SUDOKU_DIMENSION[0]*$i dans $split
Local $valeur = $split[$j+$i*$SUDOKU_DIMENSION[0]]
If Not isInArray($SUDOKU_SYMBOLES,$valeur) Then $valeur = $SUDOKU_SYMBOLES[0]
; Si la valeur n'est pas entre 1 et $SUDOKU_DIMENSION[0], on affiche la chaine vide
displayValeurInGrille($i,$j,$valeur)
; On considère que chaque case est correcte, couleur bleue
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_OK)
Next
Next
EndIf
Case $Bouton_Resoudre
Local $grille = getGrille(), $estGlobalementValide, $estUnMinimumRemplie, $ok = True
; Vérification
$estGlobalementValide = estGlobalementValide($grille)
$estUnMinimumRemplie = estUnMinimumRemplie($grille, 15)
If $estGlobalementValide[1] Then
$ok = (6 = MsgBox(4+48, $SUDOKU_TITRE, "La grille fournie est considérée comme remplie,"&@CRLF&"voulez-vous tout de même lancer la résolution?", 15, $GUI))
ElseIf Not $estGlobalementValide[0] Then
$ok = (6 = MsgBox(4+48, $SUDOKU_TITRE, "La grille fournie semble incorrecte,"&@CRLF&"voulez-vous tout de même lancer la résolution?", 15, $GUI))
ElseIf Not $estUnMinimumRemplie Then
$ok = (6 = MsgBox(4+48, $SUDOKU_TITRE, "La grille fournie semble trop peu remplie,"&@CRLF&"voulez-vous tout de même lancer la résolution?", 15, $GUI))
Else
$ok = (6 = MsgBox(4+64, $SUDOKU_TITRE, "La grille fournie semble correcte,"&@CRLF&"voulez-vous lancer la résolution?", 15, $GUI))
EndIf
; Résolution
If $ok Then
GUICtrlSetData($Label_Infos, "Résolution en cours")
; Algorithme
$grille = resoudreGrille($grille,$vide)
; Vérification
GUICtrlSetData($Label_Infos, "")
Local $estValide = estValide($grille)
Local $estGlobalementValide = estGlobalementValide($grille, $estValide)
If Not $estGlobalementValide[0] Then
; Pour chaque ligne et colonne
For $i = 0 To $SUDOKU_DIMENSION[0]-1
For $j = 0 To $SUDOKU_DIMENSION[0]-1
; La case est correctement remplie si $estValide est égale à "____" en [$i,$j]
Local $checkCase = ($estValide[$i][$j]="____")
; Si $checkCase est à True, on met la case en bleu, sinon en rouge
If $checkCase Then
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_OK)
If $grille[$i][$j] = 0 Then GUICtrlSetData($matrice[$i][$j], "")
Else
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_KO)
If $grille[$i][$j] = 0 Then GUICtrlSetData($matrice[$i][$j], "#")
EndIf
Next
Next
; Message
MsgBox(16, $SUDOKU_TITRE, "La grille générée est incorrecte !")
ElseIf Not $estGlobalementValide[1] Then
; Message
MsgBox(16, $SUDOKU_TITRE, "La grille générée est incomplète !")
Else
; Message
MsgBox(64, $SUDOKU_TITRE, "La grille fournie a été résolue !")
EndIf
EndIf
Case Else
; Liste des boutons du pavé numérique
For $i = 1 To $SUDOKU_DIMENSION[0]
; Si on clique sur le bouton $i (Attention ! valeur du bouton:$i+1, car indexé de 0 à $SUDOKU_DIMENSION[0]-1 pour les valeurs de 1 à $SUDOKU_DIMENSION[0])
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]])
displayValeurInGrille($focus_previous[0],$focus_previous[1],$SUDOKU_SYMBOLES[$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 $SUDOKU_DIMENSION[0]-1
For $j = 0 To $SUDOKU_DIMENSION[0]-1
; 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()
; On récupère la liste des valeurs possibles
Local $possibilites = getValeursPossibles($grille, $focus[0],$focus[1])
; Pour chaque case du pavé
For $i = 1 To $SUDOKU_DIMENSION[0]
; 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
EndSwitch
WEnd
; 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[$SUDOKU_DIMENSION[0]][$SUDOKU_DIMENSION[0]]
; Pour chaque ligne et colonne
For $i = 0 To $SUDOKU_DIMENSION[0]-1
For $j = 0 To $SUDOKU_DIMENSION[0]-1
Local $case = "____"
; On vérifie les cases dont la valeur est entre 1 et $SUDOKU_DIMENSION[0], sur les lignes, les colonnes et les blocs
If StringRegExp($grille[$i][$j]&"", "^("&joinArray($SUDOKU_SYMBOLES,"|",True)&")$") Then
$case = _
cond(estValideSurLigne($grille, $i,$j),"_","L") & _
cond(estValideSurColonne($grille, $i,$j),"_","C") & _
cond(estValideSurBloc($grille, $i,$j),"_","B") & "_"
Else
$case = "___" & _
cond(estValideSurPossibilite($grille, $i,$j),"_","P")
EndIf
$resultat[$i][$j] = $case
Next
Next
Return $resultat
EndFunc
; Fonction de vérification globale de la grille
Func estGlobalementValide($grille, $estValide="")
Local $correct = True, $complet = True
If $estValide = "" Then $estValide = estValide($grille)
; Pour chaque ligne et colonne
For $i = 0 To $SUDOKU_DIMENSION[0]-1
For $j = 0 To $SUDOKU_DIMENSION[0]-1
If $estValide[$i][$j]<>"____" Then $correct = False
If $grille[$i][$j] = 0 Then $complet = False
Next
Next
Local $resultat[2] = [$correct, $complet]
Return $resultat
EndFunc
; Fonction de vérification d'un remplissage minimal de la grille
Func estUnMinimumRemplie($grille, $nb=10)
Local $nb_found = 0
For $i = 0 To $SUDOKU_DIMENSION[0]-1
For $j = 0 To $SUDOKU_DIMENSION[0]-1
If $grille[$i][$j] <> 0 Then $nb_found = $nb_found+1
Next
Next
Return ($nb_found >= $nb)
EndFunc
; Fonction de récupération des valeurs de la grille (chiffres entre 0 et $SUDOKU_DIMENSION[0])
Func getGrille()
Local $grille[$SUDOKU_DIMENSION[0]][$SUDOKU_DIMENSION[0]]
For $i=0 To $SUDOKU_DIMENSION[0]-1
For $j=0 To $SUDOKU_DIMENSION[0]-1
Local $valeur = GUICtrlRead($matrice[$i][$j])
$grille[$i][$j] = 0
For $k = 1 To $SUDOKU_DIMENSION[0]
If $valeur = $SUDOKU_SYMBOLES[$k] Then $grille[$i][$j] = $k
Next
Next
Next
Return $grille
EndFunc
; Fonction d'affichage de la grille sur l'interface graphique
Func displayGrille($grille,$tentative)
For $i=0 To $SUDOKU_DIMENSION[0]-1
For $j=0 To $SUDOKU_DIMENSION[0]-1
Local $valeur = $grille[$i][$j]
displayValeurInGrille($i,$j,$SUDOKU_SYMBOLES[$valeur])
Next
Next
For $i = 1 To $tentative[0][0]
displayValeurInGrille($tentative[$i][0],$tentative[$i][1],$SUDOKU_SYMBOLES[$grille[$tentative[$i][0]][$tentative[$i][1]]],True)
Next
EndFunc
; Fonction de remplissage d'un élément dans la grille
Func setValeurInGrille(ByRef $grille,$i,$j,$valeur)
$grille[$i][$j] = $valeur
displayValeurInGrille($i,$j,$SUDOKU_SYMBOLES[$valeur])
EndFunc
; Fonction d'affichage d'une valeur dans une case de l'interface graphique
Func displayValeurInGrille($i,$j,$valeur,$tentative=False)
GUICtrlSetData($matrice[$i][$j], $valeur)
GUICtrlSetBkColor($matrice[$i][$j], cond($tentative,$SUDOKU_BKCOLOR_YES,$SUDOKU_BKCOLOR_NO))
EndFunc
; Fonction de vérification des lignes
Func estValideSurLigne($grille, $x,$y)
Local $valeur = $grille[$x][$y]
For $i = 0 To $SUDOKU_DIMENSION[0]-1
; 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 $SUDOKU_DIMENSION[0]-1
; 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)
Local $valeur = $grille[$x][$y]
; On détecte le bloc concerné par la valeur [$x,$y] ($bloc est un couple dont les valeurs sont entre [0,0] et [$SUDOKU_DIMENSION[1],$SUDOKU_DIMENSION[2]])
Local $bloc[2]=[Floor($x/$SUDOKU_DIMENSION[1]),Floor($y/$SUDOKU_DIMENSION[2])]
; Pour chaque ligne et colonne de ce bloc
For $i = $SUDOKU_DIMENSION[1]*$bloc[0] To $SUDOKU_DIMENSION[1]-1+$SUDOKU_DIMENSION[1]*$bloc[0]
For $j = $SUDOKU_DIMENSION[2]*$bloc[1] To $SUDOKU_DIMENSION[2]-1+$SUDOKU_DIMENSION[2]*$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]=$valeur Then
Return False
EndIf
Next
Next
Return True
EndFunc
; Fonction de vérification des possibilités
Func estValideSurPossibilite($grille, $x,$y)
; On récupère la liste des possibilités d'une case
Local $possibilites = getValeursPossibles($grille, $x,$y)
; On compte le nombre de possibilités d'une case
Local $nombre = getNombrePossibilites($possibilites)
; Si il n'y a aucune possibilité, on retourne False
Return $nombre[0]>0
EndFunc
; Fonction de récupération des valeurs possibles pour une case donnée
Func getValeursPossibles($grille, $i,$j)
Local $resultat[$SUDOKU_DIMENSION[0]+1] = [$SUDOKU_DIMENSION[0]]
; Pour chaque valeur possible (de 1 à $SUDOKU_DIMENSION[0], dans un tableau indexé de 0 à $SUDOKU_DIMENSION[0]-1)
For $n = 1 To $SUDOKU_DIMENSION[0]
; Par défaut, $resultat[$n] = True si la valeur $n+1 est celle présente dans la grille
$resultat[$n] = True
; Si la valeur [$i,$j] est déjà remplie, on retourne une liste ne contenant qu'une seule valeur possible, la valeur déjà fournie
If $grille[$i][$j] <> 0 Then
$resultat[$n] = ($grille[$i][$j] = $n)
; On ne teste les valeurs possibles que si les valeurs $i et $j correspondent à un focus valide
Else
If $i<>-1 And $j<>-1 Then
; $n = 0 à $SUDOKU_DIMENSION[0]-1, dont la valeur à traiter $val (qui est entre 1 et $SUDOKU_DIMENSION[0]) est $n+1
; On détecte le bloc concerné par la valeur [$i,$j] ($bloc est un couple dont les valeurs sont entre [0,0] et [$SUDOKU_DIMENSION[1],$SUDOKU_DIMENSION[2]])
Local $bloc[2]=[Floor($i/$SUDOKU_DIMENSION[1]),Floor($j/$SUDOKU_DIMENSION[2])]
; On vérifie sur la ligne concernée que la valeur n'apparait pas ailleurs qu'en [$i,$j]
For $x = 0 To $SUDOKU_DIMENSION[0]-1
If $x<>$j And $grille[$i][$x] = $n 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 $SUDOKU_DIMENSION[0]-1
If $x<>$i And $grille[$x][$j] = $n 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 = $SUDOKU_DIMENSION[1]*$bloc[0] To $SUDOKU_DIMENSION[1]-1+$SUDOKU_DIMENSION[1]*$bloc[0]
For $y = $SUDOKU_DIMENSION[2]*$bloc[1] To $SUDOKU_DIMENSION[2]-1+$SUDOKU_DIMENSION[2]*$bloc[1]
If $x<>$i And $y<>$j And $grille[$x][$y] = $n Then $resultat[$n] = False
Next
Next
Else
; Pour les valeurs ayant des coordonnées invalides, on retourne False
$resultat[$n] = False
EndIf
EndIf
Next
Return $resultat
EndFunc
; Fonction de récupération du nombre de possibilités et de la valeur la plus haute trouvée
Func getNombrePossibilites($tableau)
; Valeur de base, aucune valeur trouvée ($resultat[0] = 0, et $resultat[1] = -1 pour symbolisé le fait qu'aucune valeur ne correspond)
Local $resultat[2]=[0,-1]
; Pour chaque valeur de 1 à $SUDOKU_DIMENSION[0] (indexée dans le tableau de 0 à $SUDOKU_DIMENSION[0]-1)
For $i = 1 To $SUDOKU_DIMENSION[0]
; Si $i+1 est une valeur possible (donc $i dans l'index du tableau)
If $tableau[$i] Then
; Une valeur de plus trouvée, on incrémente $resultat[0]
$resultat[0]=$resultat[0]+1
; Valeur enregistrée dans $resultat[1]
$resultat[1]=$i
EndIf
Next
; On retourne le resultat trouvé
Return $resultat
EndFunc
; Fonction de résolution de grille par heuristiques successives
Func resoudreGrille($grille, $tentative)
displayGrille($grille, $tentative)
; INITIALISATION
Local $grille_apres = $grille
Do
Do
Do
Do
Do
Local $grille_avant = $grille_apres
; MODE DE RESOLUTION N°0 : Remplir les cases n'ayant qu'un seul choix possible
$grille_apres = remplirGrille($grille_avant,0,$tentative)
displayGrille($grille_apres,$tentative)
Until matrixEquals($grille_avant,$grille_apres) ; Tant que la grille change entre le début de l'opération ($grille_avant) et la fin ($grille_apres), on recommence
; MODE DE RESOLUTION N°1 : Remplir les cases dont une des valeurs possibles ne peut pas aller ailleurs sur la ligne
$grille_apres = remplirGrille($grille_avant,1,$tentative)
displayGrille($grille_apres,$tentative)
Until matrixEquals($grille_avant,$grille_apres) ; Tant que la grille change entre le début de l'opération ($grille_avant) et la fin ($grille_apres), on recommence
; MODE DE RESOLUTION N°2 : Remplir les cases dont une des valeurs possibles ne peut pas aller ailleurs sur la colonne
$grille_apres = remplirGrille($grille_avant,2,$tentative)
displayGrille($grille_apres,$tentative)
Until matrixEquals($grille_avant,$grille_apres) ; Tant que la grille change entre le début de l'opération ($grille_avant) et la fin ($grille_apres), on recommence
; MODE DE RESOLUTION N°3 : Remplir les cases dont une des valeurs possibles ne peut pas aller ailleurs sur le bloc
$grille_apres = remplirGrille($grille_avant,3,$tentative)
displayGrille($grille_apres,$tentative)
Until matrixEquals($grille_avant,$grille_apres) ; Tant que la grille change entre le début de l'opération ($grille_avant) et la fin ($grille_apres), on recommence
; MODE DE RESOLUTION N°4 : Choisir une valeur possible sur une case, et recommencer l'algorithme de résolution
$grille_apres = remplirGrille($grille_avant,4,$tentative)
displayGrille($grille_apres,$tentative)
Until matrixEquals($grille_avant,$grille_apres) ; Tant que la grille change entre le début de l'opération ($grille_avant) et la fin ($grille_apres), on recommence
Return $grille_apres
EndFunc
; Fonction de remplissage de grille par heuristiques
Func remplirGrille($grille, $mode, $tentative)
GUICtrlSetData($Label_Infos, _
"Résolution mode '"&$mode&"'"& _
cond($tentative[0][0]=0,""," : "&$tentative[0][0]&" hypothèse"&cond($tentative[0][0]>1,"s","")) _
)
displayGrille($grille,$tentative)
Local $resultat = $grille
Local $estGlobalementValide = estGlobalementValide($grille)
If $estGlobalementValide[0] And Not $estGlobalementValide[1] Then
Switch $mode
Case 0
Local $grille_possibilites[$SUDOKU_DIMENSION[0]][$SUDOKU_DIMENSION[0]]
; Pour chaque ligne et colonne
For $j = 0 To $SUDOKU_DIMENSION[0]-1
For $i = 0 To $SUDOKU_DIMENSION[0]-1
; On enregistre dans $grille_possibilites la liste des valeurs possibles pour la case [$i,$j] de $grille
$grille_possibilites[$i][$j] = getValeursPossibles($grille, $i,$j)
Next
Next
; Pour chaque ligne et colonne
For $j = 0 To $SUDOKU_DIMENSION[0]-1
For $i = 0 To $SUDOKU_DIMENSION[0]-1
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $resultat[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles
Local $possibilites = $grille_possibilites[$i][$j]
; On compte (getNombrePossibilites retourne un couple de valeurs, le premier élément correspond au nombre de valeur possibles, le second à la valeur possible la plus haute)
Local $nombre = getNombrePossibilites($possibilites)
; Si une seule valeur possible ($nombre[0] = 1), on affiche $nombre[1] dans la case correspondante
If $nombre[0] = 1 Then
setValeurInGrille($resultat,$i,$j,$nombre[1])
EndIf
EndIf
Next
Next
Case 1
; Pour chaque ligne et colonne
For $j = 0 To $SUDOKU_DIMENSION[0]-1
For $i = 0 To $SUDOKU_DIMENSION[0]-1
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $resultat[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles
Local $possibilites = getValeursPossibles($resultat, $i,$j)
; On compte (getNombrePossibilites retourne un couple de valeurs, le premier élément correspond au nombre de valeur possibles, le second à la valeur possible la plus haute)
Local $nombre = getNombrePossibilites($possibilites)
; Si une seule valeur possible ($nombre[0] = 1), On ne fait rien, cela sera traité dans la méthode 1
If $nombre[0] = 1 Then
; Rien
ElseIf $nombre[0]>1 Then
; Sinon pour chaque valeur possible
For $k = 1 To $SUDOKU_DIMENSION[0]
If $possibilites[$k] Then
; $found correspond au fait qu'on ait trouvé la valeur $val ailleurs
Local $found=False
For $x = 0 To $SUDOKU_DIMENSION[0]-1
If $i<>$x Then
Local $possibilites_to_compare = getValeursPossibles($resultat, $x,$j)
If $possibilites_to_compare[$k] Then $found = True
EndIf
Next
; Si on ne l'a trouvée nulle part, on affiche $val dans la case [$i,$j]
If Not $found Then
setValeurInGrille($resultat,$i,$j,$k)
EndIf
EndIf
Next
EndIf
EndIf
Next
Next
Case 2
; Pour chaque ligne et colonne
For $j = 0 To $SUDOKU_DIMENSION[0]-1
For $i = 0 To $SUDOKU_DIMENSION[0]-1
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $resultat[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles
Local $possibilites = getValeursPossibles($resultat, $i,$j)
; On compte (getNombrePossibilites retourne un couple de valeurs, le premier élément correspond au nombre de valeur possibles, le second à la valeur possible la plus haute)
Local $nombre = getNombrePossibilites($possibilites)
; Si une seule valeur possible ($nombre[0] = 1), On ne fait rien, cela sera traité dans la méthode 1
If $nombre[0] = 1 Then
; Rien
ElseIf $nombre[0]>1 Then
; Sinon pour chaque valeur possible
For $k = 1 To $SUDOKU_DIMENSION[0]
If $possibilites[$k] Then
; $found correspond au fait qu'on ait trouvé la valeur $val ailleurs
Local $found=False
For $y = 0 To $SUDOKU_DIMENSION[0]-1
If $j<>$y Then
Local $possibilites_to_compare = getValeursPossibles($resultat, $i,$y)
If $possibilites_to_compare[$k] Then $found = True
EndIf
Next
; Si on ne l'a trouvée nulle part, on affiche $val dans la case [$i,$j]
If Not $found Then
setValeurInGrille($resultat,$i,$j,$k)
EndIf
EndIf
Next
EndIf
EndIf
Next
Next
Case 3
; Pour chaque ligne et colonne
For $j = 0 To $SUDOKU_DIMENSION[0]-1
For $i = 0 To $SUDOKU_DIMENSION[0]-1
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $resultat[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles
Local $possibilites = getValeursPossibles($resultat, $i,$j)
; On compte (getNombrePossibilites retourne un couple de valeurs, le premier élément correspond au nombre de valeur possibles, le second à la valeur possible la plus haute)
Local $nombre = getNombrePossibilites($possibilites)
; Si une seule valeur possible ($nombre[0] = 1), On ne fait rien, cela sera traité dans la méthode 1
If $nombre[0] = 1 Then
; Rien
ElseIf $nombre[0]>1 Then
; Sinon pour chaque valeur possible
For $k = 1 To $SUDOKU_DIMENSION[0]
If $possibilites[$k] Then
; $found correspond au fait qu'on ait trouvé la valeur $val ailleurs
Local $found=False
Local $bloc[2]=[Floor($i/$SUDOKU_DIMENSION[1]),Floor($j/$SUDOKU_DIMENSION[2])]
For $x = $SUDOKU_DIMENSION[1]*$bloc[0] To $SUDOKU_DIMENSION[1]-1+$SUDOKU_DIMENSION[1]*$bloc[0]
For $y = $SUDOKU_DIMENSION[2]*$bloc[1] To $SUDOKU_DIMENSION[2]-1+$SUDOKU_DIMENSION[2]*$bloc[1]
If $i<>$x Or $j<>$y Then
Local $possibilites_to_compare = getValeursPossibles($resultat, $x,$y)
If $possibilites_to_compare[$k] Then $found = True
EndIf
Next
Next
; Si on ne l'a trouvée nulle part, on affiche $val dans la case [$i,$j]
If Not $found Then
setValeurInGrille($resultat,$i,$j,$k)
EndIf
EndIf
Next
EndIf
EndIf
Next
Next
Case 4
; Pour chaque ligne et colonne
For $j = 0 To $SUDOKU_DIMENSION[0]-1
For $i = 0 To $SUDOKU_DIMENSION[0]-1
; On ne travaille que sur les valeurs qui ne sont pas remplies, et qui valent donc 0 dans la grille des valeurs
If $resultat[$i][$j] = 0 Then
; On récupère la liste des valeurs possibles
Local $possibilites = getValeursPossibles($resultat, $i,$j)
; On compte (getNombrePossibilites retourne un couple de valeurs, le premier élément correspond au nombre de valeur possibles, le second à la valeur possible la plus haute)
Local $nombre = getNombrePossibilites($possibilites)
; Si une seule valeur possible ($nombre[0] = 1), On ne fait rien, cela sera traité dans la méthode 1
If $nombre[0] = 1 Then
; Rien
ElseIf $nombre[0]>1 Then
; Sinon pour chaque valeur possible
For $k = 1 To $SUDOKU_DIMENSION[0]
If $possibilites[$k] Then
; On enregistre la valeur $k dans une grille temporaire
Local $resultatToTest = $resultat, $tentativeToTest = $tentative
setValeurInGrille($resultatToTest,$i,$j,$k)
; On ajoute cette case aux tentatives
$tentativeToTest[0][0] = $tentativeToTest[0][0]+1
ReDim $tentativeToTest[$tentativeToTest[0][0]+1][2]
$tentativeToTest[$tentativeToTest[0][0]][0] = $i
$tentativeToTest[$tentativeToTest[0][0]][1] = $j
; On tente de résoudre cette grille là
$resultatToTest = resoudreGrille($resultatToTest,$tentativeToTest)
Local $estGlobalementValide = estGlobalementValide($resultatToTest)
; Si la grille est correcte et totalement remplie, la grille trouvée est la (ou une) solution
If $estGlobalementValide[0] And $estGlobalementValide[1] Then Return $resultatToTest
EndIf
Next
EndIf
EndIf
Next
Next
EndSwitch
EndIf
Return $resultat
EndFunc
; Fonction de jointure de tableau
Func joinArray($tableau,$separateur="|",$ignoreFirst=False)
Local $texte = "", $first = True
For $i = cond($ignoreFirst,1,0) To UBound($tableau)-1
If Not $first Then $texte = $texte & $separateur
$first = False
$texte = $texte & $tableau[$i]
Next
Return $texte
EndFunc
; Fonction de présence dans un tableau
Func isInArray($tableau,$valeur)
For $i = 0 To UBound($tableau)-1
If $tableau[$i] = $valeur Then Return True
Next
Return False
EndFunc
- 3x3² Facile = 050310020010698540800020000007040080045000910090050700000060007076235090030089050
- 3x3² Débutant = 000400000570000103210605000390080200000701000007020016000802079905000082000009000
- 3x3² Confirmé = 005000601000700000780061900300500000059040030000100006007006120810009007500200800
- 3x3² Difficile = 002300007809000005005009046000003000090127600007480000000572013070940000540800000
- 3x3² Expert = 003040057908060200001350600800700400000008500000014002000430800410080320000000000
Son fonctionnement est simple dans la résolution, il effectue les mêmes opérations jusqu'à arriver à une grille complète :
- Il remplit d'abord les cases où il n'y a qu'une possibilité possible (selon la ligne, la colonne ou le bloc)
- Si il n'y a plus de choix possibles, il remplit les cases où une valeur possible ne peut pas aller ailleurs dans une case de la même ligne
- Si il n'y a plus de choix possibles, il remplit les cases où une valeur possible ne peut pas aller ailleurs dans une case de la même colonne
- Si il n'y a plus de choix possibles, il remplit les cases où une valeur possible ne peut pas aller ailleurs dans une case de le même bloc
- Si il n'y a plus de choix possibles, il remplit une case en "TEMPORAIRE" et continue à tenter de remplir la grille
- Si par le même algo, il arrive à une solution incorrecte (genre deux symboles identiques sur la même ligne) et qu'il ne peut pas terminer, il change la valeur de la case en temporaire par une autre valeur possible
- Si par le même algo, il arrive à une solution incomplète, il choisit une autre case en temporaire, et il lui affecte une valeur possible, et continue à tenter de remplir la grille
- Si aucune valeur possible de la grille ne donne de solution correcte, il choisit une autre case
- Si toutes les cases ont été testées pour toutes les valeurs possibles, il s’arrête, c'est qu'il n'y a pas du tout de solution possible.
EDIT 26/09/2011 : Mise à jour du code : ajout d'un système d'heuristiques, et vérification des grilles avant de pouvoir lancer une résolution.
EDIT 27/09/2011 : Mise à jour du code : correction et ajout d'un affichage de l'état de résolution en cours (mode utilisé et cases avec une hypothèse émise affichées en gris).