diakt027
Messages postés1Date d'inscriptionsamedi 3 janvier 2009StatutMembreDernière intervention 3 mai 2010
-
3 mai 2010 à 11:58
l0r3nz1
Messages postés218Date d'inscriptionmercredi 20 février 2008StatutMembreDernière intervention17 mars 2012
-
3 mai 2010 à 14:42
Bonjour tout le monde
J'ai un grand besoin de vos savoirs .
Je dois développer un programme en java qui résout les grilles de sudoku, et la je bloque.
J'ai essayer une méthode de backtracking et n'ayant pas réussit j'ai voulu me lancer dans la récursivité, et la je bloque encore.
Ligne de code :
public Valeur[][] creerGrille(Valeur[][] maGrille){
int valeurEnCours;
Valeur uneGrille[][] = new Valeur[9][9];
boolean valeurTrouvee;
uneGrille = maGrille;
nbGrille++;
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
valeurEnCours = -1;
if (uneGrille[i][j].getValeur() == 0){
for (int y = 0; y < uneGrille[i][j].getValeursPossible().size() - 1; y++){
valeurEnCours = (Integer)uneGrille[i][j].getValeursPossible().get(y);
if ((ligne(valeurEnCours, uneGrille, i)) || (colonne(valeurEnCours, uneGrille, j)) || (miniCarre(getMiniCarre(i, j), valeurEnCours))){
valeurTrouvee = false;
}
else
{
valeurTrouvee = true;
uneGrille[i][j].setValeur(valeurEnCours);
creerGrille(uneGrille);
}
if (valeurTrouvee)
return null;
}
}
}
}
System.out.println("Solution numero : " + nbGrille);
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
if (uneGrille[i][j].getValeur() == 0){
return null;
}
}
}
return (uneGrille);
}
Et le programme ne remonte jamais quand il s'aperçoit qu'une solution n'es pas la bonne pour passer a une autre.. j'ai du oublier une liste de teste ou autres choses je ne sais plus quoi faire..
Ou alors si quelqu'un a un lien vers une résolution en back ou recursif pas trop complexe pour que je puisse tirer leçon de mes erreurs ce serait parfait
l0r3nz1
Messages postés218Date d'inscriptionmercredi 20 février 2008StatutMembreDernière intervention17 mars 2012 3 mai 2010 à 14:40
tu devrais plutôt utiliser les objets tu t'en sortirais mieux.
un objet case qui a comme valeur une ligne une colonne, une case des listes de valeurs (ligne colonne case) et une valeur avec un booléen, "juste". un truc dans le genre, ce sera plus claire que des boucles a répétition.
il y a la méthode brutale qui est de tester toutes les solutions, en utilisant des objets contenant certaines variables toujours bien sur. un objet "grille_sudoku" de départ qui génère toutes les objets "grille_sudoku" possibles et vérifie pour chaque grille, chaque case si les conditions correspondent à une grille valide.
l'exécution risque d'être un peu lente, il faut optimiser le truc bien sur.