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, $SUDOKU_COLOR_IMPORT = 0x00BB66
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 = ClipGet()
If StringLen($chaine) <> $taille Then $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]]
; On considère que chaque case est correctement importée, couleur verte
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_IMPORT)
If Not isInArray($SUDOKU_SYMBOLES,$valeur) Then
$valeur = $SUDOKU_SYMBOLES[0]
; On considère que chaque case vide comme potentiellement correcte, couleur bleue
GUICtrlSetColor($matrice[$i][$j], $SUDOKU_COLOR_OK)
EndIf
; Si la valeur n'est pas entre 1 et $SUDOKU_DIMENSION[0], on affiche la chaine vide
displayValeurInGrille($i,$j,$valeur)
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