Bonjour,

dans le cadre d'un TP, nous devons faire un résolveur de Sudoku en utilisant la méthode du backtracking.

J'avoue n'avoir pas très bien compris cette manière de faire mais nous avons un algorithme de base pour le backtracking en français que je respecte. J'ai déjà essayer de lire des trucs sur internet pour m'aider à comprendre où je bloque mais rien à faire.

Au niveau du programme que j'ai fait, il me rempli une petite partie de la grille mais s'arrête à la fin de la ligne 1 et rempli quelques autres cases par ci par là.

SUPPRESSION DU CODE

Voici le résultat :

En haut, la grille de base et en bas, ce qui est censé être la solution

En espérant que vous puissiez m'aider,

Merci d'avance,

Fulash

-
Edité par Fulash 20 septembre 2016 à 21:57:44

Salut,

Pourquoi est-ce que ta méthode remplir grille ne prend en paramètre qu'un numéro de colonne et pas aussi le numéro de ligne ?

Actuellement ton code prend une colonne, remplit un chiffre dans cette colonne et passe à la colonne suivante.

Autre conseil, essaie de donner d'autre nom que i,j,k et num, d'ailleurs ça t'éviterait d'avoir à commenter " i = numéro de colonne".

Et je ferais aussi des sous fonctions pour essayer de rendre plus lisible par exemple if ( pasDansLigne(val, numLigne, numColonne, grille) && pasDansColonne(val, numLigne, numColonne, grille) && pasDansRegion(val, numLigne, numColonne, grille))

Salut macaque et merci pour ta réponse.

Au niveau des paramètres, je me suis basé sur un autre exercice du même genre où on parcourait aussi un tableau à 2 dimension mais je crois que je vais faire comme tu m'as dit.

macaque a écrit:

Actuellement ton code prend une colonne, remplit un chiffre dans cette colonne et passe à la colonne suivante.

Je ne comprend pas bien pourquoi. Il y a une boucle tant que pour faire parcourir toutes les lignes et la récursivité s'execute tant qu'on a pas rempli toute les colonnes. Me suis-je perdu dans mon code?

macaque a écrit:

Autre conseil, essaie de donner d'autre nom que i,j,k et num, d'ailleurs ça t'éviterait d'avoir à commenter " i = numéro de colonne".

Pour les noms de variables je me comprends, j'avais rajouter ce commentaire pour vous mais je vais y penser.

Merci 

Fulash a écrit:

macaque a écrit:

Autre conseil, essaie de donner d'autre nom que i,j,k et num, d'ailleurs ça t'éviterait d'avoir à commenter " i = numéro de colonne".

Pour les noms de variables je me comprends, j'avais rajouter ce commentaire pour vous mais je vais y penser.

C'est un projet "poubelle" (Je veux dire par là que tu n'ira sans doutes pas relire le code plus tard), mais je te conseil de commencer dès maintenant à bien nommer tes variables car par expérience, tu perdra beaucoup de temps à comprendre des codes avec des noms un peux trop simpliste, alors qu'a l'époque je savais à quoi cela correspondait.

A l'intérieur de ta boucle sur les lignes, tu appelles ta récursivement la méthode sur la colonne suivante. Mais tu le fais pour chaque ligne, pas après avoir rempli toutes les lignes. Et puis si jamais tu arrives sur une solution, tu ne t'arrête pas.

Utilise le debuger ou rajoute des traces pour comprendre ce qu'il se passe.

Je t'aide sans doute un peu trop, mais voilà un squelette plus lisible (j'ai pas vérifier si ça marche, avec un peu de chance il y a des erreurs que tu devras corriger) :

/** Retourne vrai si la grille a pu être remplie, faux sinon */
boolean remplirGrille(int numCase, Grille grille) {

    if (numCase >= 81) {
        return true;
    }

    int numLigne = numCase % 9;
    int numColonne = numCase / 9;

    if ( estRempli(numLigne, numColonne, grille ) ) {
        return remplirGrille(numCase+1, grille);
    }

    List<Integer> listeValeursPossibles = choisirValeursPossiblesPourCellulle( numLigne, numColonne, grille );

    for (int valeurPossible : listeValeursPossibles) {
        grille.set(valeurPossible, numLigne, numColonne);
        if (remplirGrille(numCase+1, grille)) {
            return true;
        }
    }
    grille.effacer(numLigne, numColonne);
    return false;
}

boolean remplirGrille(Grille grille) {
    remplirGrille(0, grille);
}

-
Edité par macaque 20 septembre 2016 à 12:15:13

Merci pour ton aide,

je vais essayer d'adapter ça et de le faire à ma manière.

Je vous tiens au courant.