J'ai grandement besoin d'aide sur un problème , qui pour certains , peut paraitre assez bête :-)
Je programme en JAVA, un Solveur de Sudoku .. pour cela, je met en pratique une idée très simple :
Le Sudoku est representé par un tableau d'entiers à deux dimensions .
J'essaye de faire une fonction récursive , qui Teste toutes les solutions possibles pour une case , s'arrete lorsqu'elle rencontre un problème ( c'est a dire pas de solution pour une case ) , et revient "en arrière" (noeud d'avant) puis continue le parcours/remplissage du tableau dans le cas contraire .
De cette manière , en résolvant une grille , on doit avoir un Arbre avec des branches dont certaines << s'arrètent >> (celles pour lesquelles on a buté sur une case) , et l'une (ou plusieurs s'il y à plusieurs solutions ..) avec la solution : 81 branches !
C'est assez simple , mais je bute sur un problème (de programmation je pense..) , je n'arrive pas à traduire cette récursivité en JAVA..
Lorsque le Solveur rencontre une case a problème , il ne " revient pas en arrière " , ne test pas d'autres solutions pour la case qui la précède .
Pourriez-vous m'éclairer , et me dire en quoi ma récursion fausse ?
public boolean Resolve(int[][] vals){
/* 1) on verifie si le sudoku est totalement résolu */
if(toutestok(vals)) { Affiche(vals); return true; }
else { // il manque des elements dans la grille
for(int i=0;i<10;i++)
for(int j=0;j<10;j++){
if(vals[j][i]==-1){ /* si est une case inconnue (sont égales à -1) */
/* pour chaque case, on test l'insertion des nb de 1 -> 9 */
boolean found=false; // dit si oui ou non, une solution pour cette case a été trouvée */
for(int nb=0;nb<10;nb++){
/* Si NB vérifie les 3 conditions (ligne,colonne,carré..).. */
if(verifConditions(nb,j,i,vals)){
found=true; // on a trouvé une solution pour la case
int[][] tempvals=new int[10][10];
tempvals=vals; // On copie la grille courante dans un tableau temporaire
tempvals[j][i]=nb; // On y insère la solution
Resolve(tempvals); // On rappelle Resolve( ) , avec la solution pour la case ( i , j )
} // if nb
} // for nb
if(!found){ /* si malgres les 10 tests,pas de solution, on arrete la recherche sur cette branche */
return false; }
} // si case à changer
} // for j
} // si manque des éléments
return true;
} // resolution
Comme dit plus haut , lors de l'execution ... l'algorithme semble ne pas être récursif , il ne revient pas "en arriere" pour tester d'autres valeurs sur la/les cases precedentes .
Si vous auriez une idée de ce qui ne va pas dans mon code , n'hesitez pas à m'eclairer , je vous en serais d'une grande reconnaissance ;-)
Merci d'avance !
Oups, juste oublié de preciser (ça ne change pas grand chose, mais on sait jamais !) :
Vous l'avez peut etre remarqué dans le code , ce n'est pas un Sudoku 9x9 mais un Soduku 10x10 (chiffres de 0 à 9) .
