Algo de backtracking pour sudoku

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Algo de backtracking pour sudoku

cybkiller

Un clavier AZERTY en vaut deux

Salut à vous,

J'ai un sudoku à faire pour un projet de fin d'année et je bloque sur cet algo :

Voici la grille "énoncé" (0 correspond à une case vide) :

Code :

int enonce[9][9]={
{7,9,0,0,4,0,0,0,0},
{0,0,4,0,1,0,8,7,0},
{0,0,0,0,0,2,0,6,0},
{0,5,6,0,0,1,0,0,3},
{0,0,0,0,5,0,0,0,0},
{3,0,0,8,0,0,7,1,0},
{0,8,0,2,0,0,0,0,0},
{0,3,5,0,8,0,1,0,0},
{0,0,0,0,6,0,0,5,8}
};;

Dans le programme, je dois vérifier l'énoncé (fonctionne) et le copierdans un tableau 9*9 qui s'appelle "grille", c'est dans ce tableau queje travaille; à aucun moment je ne dois modifier enonce.
J'ai aussi 3 tableaux de booléens : c[9][10] l[9][10] et pave[9][10] tels que :
Pave[i][j] vrai ssi j est présent dans le pavé n°i.
l[i][j] vrai ssi j est présent dans la ligne n° i.
c[i][j] vrai ssi j est présent dans la colonne n° i.

Voici ma fonction :

Code :

void parcours(int prof)
{
if (prof < 81)
{
int x=prof%9, y=prof/9;
int pav=3*(y/3)+(x/3);
(grille[y][x]) = 1;
if ((enonce[x][y]) == 0) //si la case est vide dans l'énoncé
{
while (grille[y][x] < 9) //on teste toutes les valeurs possibles pour la case
{
if (!(l[y][(grille[y][x])] || c[x][(grille[y][x])] || pave[pav][(grille[y][x])])) //si on peut mettre une valeur
{
c[x][(grille[y][x])] = true; /* Ici on met */
l[y][(grille[y][x])] = true; /* à jour les tableaux */
pave[pav][(grille[y][x])] = true; /* de booleens */
parcours(prof + 1); //on passe à la valeur suivante
return ; // ici pour sortir directement de la fonction si on a fini et non revenir en arriere ...
}
(grille[y][x])++;
}
(grille[y][x])=0; // on remet la valeur à 0
parcours(prof-1); //on retravaille avec la valeur précédente
}
else //si dans l'énoncé la case n'est pas vide on passe à la suivante
{
parcours(prof + 1);
}
}
}

Cette fonction est recursive et "prof" permet de transmettre la position à laquelle on se trouve, sachant que :

- prof % 9 = la colonne (x)
- prof / 9 = la ligne (y)

on obtient le pavé correspondant en faisant 3*(y /3) + x/3 .

(ce sont des divisions entières)
donc pour les pavés ils sont numérotés de 0 à 8 de gauche à droite puis de haut en bas.

Le programme se compile sans problème mais à l'execution j'ai cette erreur :

Pouvez-vous m'aider svp ?

Merci d'avance.

Publicité

billgatesanonym

Il faudrait débugguer, soit avec un debuggeur et en suivant pas à pas, soit en écrivant des traces dans un fichier et en étudiant ces traces.

Je n'ai jamais programmé de Sudoku, mais j'ai fait plusieurs programmes qui fonctionnaient avec des arbres de recherche, et j'ai toujours utilisé un appel récursif avec une profondeur plus grande, comme sur la ligne 19, mais jamais avec une profondeur plus petite, comme sur la ligne 27, et je crains donc que cette dernière soit fautive.

Un Programmeur

Quelques pistes:
-> avoir la fonction qui retourne une valeur indiquant si une solution a été trouvée ou pas.
-> remettre a jour tes tableaux de booleens après la ligne 26.
-> supprimer la ligne 27
-> le return de la ligne 20 doit être conditionnel sur la valeur de retour de l'appel de la ligne 19

masklinn

í dag viðrar vel til loftárása

FWIW si tu fais de la résolution de sudoku tu devrais checker la solution "CPS" de Norvig (http://norvig.com/sudoku.html)

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

cybkiller

Un clavier AZERTY en vaut deux

@billgatesanonym:

Le programme met l'erreur au moment où il rencontre cette ligne :

Code :

if (!(l[y][(grille[y][x])] || c[x][(grille[y][x])] || pave[pav][(grille[y][x])]))

(Endroit localisé à l'aide de printf)

@Un programmeur:

Vu que c'est un projet de fin d'année, et que la "base" du code m'a été donnée, je suis extrêmement limité : ce n'est pas comme si j'écrivais le sudoku; on m'impose les prototypes des fonctions donc ici l'entier prof.

Il me semblait que si le programme atteignait la ligne 26 les tableaux de booléens ne seraient pas modifiés, la seule modification étant (grille[y][x]) = 1; à la ligne 7. Dîtes moi si je me trompe.

Si je supprime la ligne 27, comment l'algo peut-il revenir en arrière ? il faut que je lui envoie la valeur de la case précédente pour qu'il puisse retravailler dessus

Pourriez-vous m'expliquer le return à mettre en condition l20, je pensais que le fais qu'il soit dans le grand IF suffisait.
@Masklinn

Je suis malheureusement contraint à un code précis pour mon devoir.

Merci à tous pour vos réponses.

Un Programmeur

Je te conseille de revoir ce qu'est la récursivité.

cybkiller

Un clavier AZERTY en vaut deux

Je regarderais bien mes cours, mais étant en fac et avec la LRU, j'ai eu environ 1 mois de cours ...

billgatesanonym

Citation :

Le programme met l'erreur au moment où il rencontre cette ligne :
if (!(l[y][(grille[y][x])] || c[x][(grille[y][x])] || pave[pav][(grille[y][x])]))

C'est bien de l'avoir localisée. Maintenant il faut se demander ce qui ne va pas sur cette ligne. En fait, elle est assez banale. Le problème est vraisemblablement causé par des valeurs abbérantes de l'un des indices ou de plusieurs indices. Donc il faudrait voir ce que contiennent les variables y, x, pav juste avant cette ligne. Il y a sans doute l'une d'elles qui est en dehors des limites. Il faudrait chercher comment l'une de ses variables pourrait contenir une valeur hors limite. Il y a deux hypothèses. Soit une mauvaise mise à jour de ces variables, soit un effet secondaire malheureux qui serait dû à "l'explosion de la pile", ce qui est un phénomène que l'on rencontre avec les fonctions récursives mal maîtrisées.

Citation :

Si je supprime la ligne 27, comment l'algo peut-il revenir en arrière ?

Le programme revient en arrière avec le return de la ligne 20 ou celui de la ligne 36 (qui est implicite, mais qui aurait pû être mis explicitement pour que le code soit plus clair). La variable prof est passée par valeur, et non pas par référence. Cela implique qu'après le return et la sortie de la fonction, cette variable prof retrouvera sa valeur d'avant.

Message édité par billgatesanonym le 03-05-2009 à 16:11:08

cybkiller

Un clavier AZERTY en vaut deux

D'abord, merci pour ta réponse;

J'ai appliqué les divers changements, voici la fonction :

Code :

void parcours(int prof)
{
if (prof <= 81)
{
int x=prof%9, y=prof/9;
int pav=3*(y/3)+(x/3);
printf("#X->%d Y->%d PAV->%dn",x,y,pav); //pour surveiller les valeurs de x,y, et pav
if ((enonce[y][x]) == 0) //si la case est vide dans l'énoncé
{
(grille[y][x]) = 1;
while (grille[y][x] < 9) //on teste toutes les valeurs possibles pour la case
{
if (!(l[y][(grille[y][x])] || c[x][(grille[y][x])] || pave[pav][(grille[y][x])])) //si on peut mettre une valeur
{
c[x][(grille[y][x])] = true; /* Ici on met */
l[y][(grille[y][x])] = true; /* à jour les tableaux */
pave[pav][(grille[y][x])] = true; /* de booleens */
parcours(prof + 1); //on passe à la valeur suivante
return ; // ici pour sortir directement de la fonction si on a fini et non revenir en arriere ...
}
(grille[y][x])++;
}
l[y][(grille[y][x])]=false;
c[x][(grille[y][x])]=false;
pave[pav][(grille[y][x])]=false;
(grille[y][x])=0; // on remet la valeur à 0
}
else //si dans l'énoncé la case n'est pas vide on passe à la suivante
{
parcours(prof + 1);
}
}
dessine_grille(win); //sert à réactualiser la fenêtre de sudoku une fois le travail effectué
return ;
}

Sur la console, rien d'anormal hormis qu'il ne traite que les 8 premières valeurs :

Code :

#X->0 Y->0 PAV->0
#X->1 Y->0 PAV->0
#X->2 Y->0 PAV->0
#X->3 Y->0 PAV->1
#X->4 Y->0 PAV->1
#X->5 Y->0 PAV->1
#X->6 Y->0 PAV->2
#X->7 Y->0 PAV->2

et que les solutions proposées sont fausses

@billgatesanonym : vois-tu ce qui ne va pas ?

edit: si je réexécute la fonction, il ne me "solutionne" plus que 3 cases puis 2 (ne descend pas en dessous de 2 "solutions" ).

Message édité par cybkiller le 03-05-2009 à 17:14:47

billgatesanonym

Si ça ne plante plus, c'est déjà un progrès énorme. Bravo !

Mais, je suis désolé, je n'ai pas le temps de regarder en détail.

Cependant, Monsieur Un programmeur, qui n'est pas mauvais, semble avoir repéré des choses intéressantes ; par exemple, l'utilité de réinitialiser les booléens.

Publicité

Joel F

Real men use unique_ptr

pourquoi gérer la profondeur de recursivité avec une seule valeur alros que tu est clairement en 2D. Ta fonction pourrais prendre un profx, profx et évité de te vautrer dans tes / %

cybkiller

Un clavier AZERTY en vaut deux

Si ça ne tenait qu'à moi, il y aurait en effet deux valeurs ...
Cependant, je dois m'en tenir aux déclarations des fonctions de l'énoncé.

FORUM HardWare.fr

Programmation

Algo de backtracking pour sudoku

Sujets relatifs
[Résolu] Algo de création d'une clé de validation	Algo / concepts de correction du flou
Sudoku	Algo de transformation de courbes (composées d'un nb fini de points)
sudoku en C !	[Algo][Java] Appli de compta
Quel est le meilleur moyen de réaliser une grille de sudoku avec GTK ?	recherche algo pour optimiser une recherche dans un graphe cyclique
Demande de conseils pour un algo	aide algo sur les matrices
Plus de sujets relatifs à : Algo de backtracking pour sudoku

Page générée en 0.106 secondes