J'ai repris un article que j'ai posté sur mon ancien blog sur 1free:
"
Sudoku solver
Dans ce qui suit on va essayer de proposer des solutions pour la resolution des grilles du jeu Sudoku.
solutions
I. Le backtracking
Algorithme
Fonction resourdreGrille(var entier[][] matrice, var entier posX, var entier posY,int valeurEnCours) : boolean
x1 : Entier
y1 : Entier
Debut
Si x >= 9 Alors
return true
FinSi
matrice[x][y]:= valeurEnCours
x1:= x
y1:= y
calculElementProchain(x1,y1)
Si(verifGrille(matrice) ET resoudreGrille(x1,y1,1)) Alors
return true
Sinon
{
Si (valeurEnCours < 9) Alors
{
valeurEnCours := valeurEnCours + 1
return esourdreGrille(x,y,valeurEnCours)
}
Sinon
{
matrice[x][y]:= 0
return false
}
FinSi
}
FinSi
Fin
Indications
Principe : Implementation du backtracking au Sudoku, cet algorithme fonctionne selon ce princip
On cherche la première case vide
On cherche la premiere valeur qui peut affectée a la case sans violer les règles du jeu
2 cas :
Il n'y a pas de valeurs : la grille proposée n'admet pas de solutions ?-> Mauvais chemin : On retourne à la case precedante on prend la valeur correcte suivante et on réitaire
Il y a : On affecte la valeur et on passe a la prochaine case libre et on réitaire!
verifGrille(entier[][]) est une fonction qui verifie l'etat de la matrice à une itération (verifie les regles du jeu) et retourne un boolean indiquant l'etat de la grille calculElementProchain(var entier x,var entier y): retourne l'element prochain concerné par l'alogrithme (une case non pré renseignée)
Code Source en java
Cliquez ici pour voir la source en java
Exemple de résolution
Grille Initiale solution
0 0 0 0 0 7 0 8 0 1 9 6 3 2 7 4 8 5
0 0 7 0 5 0 0 0 0 8 4 7 6 5 9 3 2 1
2 0 0 0 0 1 9 0 0 2 3 5 8 4 1 9 6 7
0 8 2 0 0 4 0 7 3 6 8 2 1 9 4 5 7 3
9 0 0 5 0 8 0 0 4 ---- 9 7 3 5 6 8 2 1 4
4 5 0 2 0 0 6 9 0 4 5 1 2 7 3 6 9 8
0 0 9 7 0 0 0 0 2 5 1 9 7 3 6 8 4 2
0 0 0 0 8 0 1 0 0 7 2 4 9 8 5 1 3 6
0 6 0 4 0 0 0 0 0 3 6 8 4 1 2 7 5 9
"
Applet d'Essai
Code source
