Résolution d'une grille Sudoku par backtracking (java implémentation)

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