Algo de backtracking pour sudoku

Algo de backtracking pour sudoku - C - Programmation

Marsh Posté le 02-05-2009 à 20:22:28    

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 :
  1. int enonce[9][9]={
  2.                    {7,9,0,0,4,0,0,0,0},
  3.                    {0,0,4,0,1,0,8,7,0},
  4.                    {0,0,0,0,0,2,0,6,0},
  5.                    {0,5,6,0,0,1,0,0,3},
  6.                    {0,0,0,0,5,0,0,0,0},
  7.                    {3,0,0,8,0,0,7,1,0},
  8.                    {0,8,0,2,0,0,0,0,0},
  9.                    {0,3,5,0,8,0,1,0,0},
  10.                    {0,0,0,0,6,0,0,5,8}
  11.                   };;


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 :
  1. void    parcours(int prof)
  2. {
  3.     if (prof < 81)
  4.     {
  5.         int x=prof%9, y=prof/9;
  6.         int pav=3*(y/3)+(x/3);
  7.         (grille[y][x]) = 1;
  8.         if ((enonce[x][y]) == 0) //si la case est vide dans l'énoncé
  9.         {
  10.             while (grille[y][x] < 9) //on teste toutes les valeurs possibles pour la case
  11.             {
  12.                 if (!(l[y][(grille[y][x])] || c[x][(grille[y][x])] || pave[pav][(grille[y][x])])) //si on peut mettre une valeur
  13.                 {
  14.                    
  15.                     c[x][(grille[y][x])] = true;      /*   Ici on met             */
  16.                     l[y][(grille[y][x])] = true;      /*   à jour les tableaux    */
  17.                     pave[pav][(grille[y][x])] = true; /*   de booleens            */
  18.                    
  19.                     parcours(prof + 1); //on passe à la valeur suivante
  20.                     return ; // ici pour sortir directement de la fonction si on a fini et non revenir en arriere ...
  21.                 }
  22.                 (grille[y][x])++;
  23.                
  24.             }
  25.            
  26.             (grille[y][x])=0;  // on remet la valeur à 0
  27.             parcours(prof-1); //on retravaille avec la valeur précédente
  28.            
  29.         }
  30.         else //si dans l'énoncé la case n'est pas vide on passe à la suivante
  31.         {
  32.             parcours(prof + 1);
  33.         }
  34.     }
  35. }


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 :
 
http://img140.imageshack.us/img140/192/erreurq.jpg
 
Pouvez-vous m'aider svp ?
 
Merci d'avance.

Reply

Marsh Posté le 02-05-2009 à 20:22:28   

Reply

Marsh Posté le 03-05-2009 à 01:38:18    

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.

Reply

Marsh Posté le 03-05-2009 à 11:21:06    

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

Reply

Marsh Posté le 03-05-2009 à 11:36:00    

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
Reply

Marsh Posté le 03-05-2009 à 12:08:29    

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

Code :
  1. 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.

Reply

Marsh Posté le 03-05-2009 à 12:13:59    

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

Reply

Marsh Posté le 03-05-2009 à 12:41:48    

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

Reply

Marsh Posté le 03-05-2009 à 16:09:31    

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
Reply

Marsh Posté le 03-05-2009 à 17:02:01    

D'abord, merci pour ta réponse;

 

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

 
Code :
  1. void parcours(int prof)
  2. {
  3.     if (prof <= 81)
  4.     {
  5.         int x=prof%9, y=prof/9;
  6.         int pav=3*(y/3)+(x/3);
  7.         printf("#X->%d  Y->%d PAV->%dn",x,y,pav); //pour surveiller les valeurs de x,y, et pav
  8.         if ((enonce[y][x]) == 0) //si la case est vide dans l'énoncé
  9.         {
  10.             (grille[y][x]) = 1;
  11.             while (grille[y][x] < 9) //on teste toutes les valeurs possibles pour la case
  12.             {
  13.                 if (!(l[y][(grille[y][x])] || c[x][(grille[y][x])] || pave[pav][(grille[y][x])])) //si on peut mettre une valeur
  14.                 {
  15.                    
  16.                     c[x][(grille[y][x])] = true;      /*   Ici on met             */
  17.                     l[y][(grille[y][x])] = true;      /*   à jour les tableaux    */
  18.                     pave[pav][(grille[y][x])] = true; /*   de booleens            */
  19.                
  20.                     parcours(prof + 1); //on passe à la valeur suivante
  21.                     return ; // ici pour sortir directement de la fonction si on a fini et non revenir en arriere ...
  22.                 }
  23.                 (grille[y][x])++;   
  24.             }
  25.             l[y][(grille[y][x])]=false;
  26.             c[x][(grille[y][x])]=false;
  27.             pave[pav][(grille[y][x])]=false;
  28.             (grille[y][x])=0;  // on remet la valeur à 0
  29.         }
  30.         else //si dans l'énoncé la case n'est pas vide on passe à la suivante
  31.         {
  32.             parcours(prof + 1);
  33.         }
  34.     }
  35.     dessine_grille(win); //sert à réactualiser la fenêtre de sudoku une fois le travail effectué
  36.     return ;
  37. }


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

 
Code :
  1. #X->0  Y->0 PAV->0
  2. #X->1  Y->0 PAV->0
  3. #X->2  Y->0 PAV->0
  4. #X->3  Y->0 PAV->1
  5. #X->4  Y->0 PAV->1
  6. #X->5  Y->0 PAV->1
  7. #X->6  Y->0 PAV->2
  8. #X->7  Y->0 PAV->2


et que les solutions proposées sont fausses :D

 

@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
Reply

Marsh Posté le 03-05-2009 à 18:47:53    

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.

Reply

Marsh Posté le 03-05-2009 à 18:47:53   

Reply

Marsh Posté le 03-05-2009 à 21:50:58    

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 / %

Reply

Marsh Posté le 03-05-2009 à 22:47:30    

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é.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed