Mon solveur de s.u.d.o.k.u marche mais trouve pas toutes les solutions

Mon solveur de s.u.d.o.k.u marche mais trouve pas toutes les solutions - C - Programmation

Marsh Posté le 09-06-2007 à 21:48:07    

Bonjour à tous,
 
Donc voilà, j'ai terminé de coder mon solveur de sudoku.
 
Le principe du programme :
 
Il est basé sur le principe de backtracking à partir d'une liste de candidats.
 
En gros, au début du programme, il remplit pour chaque case d'un tableau 9x9 (la grille de sudoku) une liste chainée représentant chaque "candidat" d'une case, càd chaque nombre possible pour cette case.
 
L'algorithme de backtracking en lui même est un algo récursif qui remplit la première case avec le premier candidat de cette case, puis passe à la case à remplir suivante et est rappelé lui même sur cette case.
 
Il va donc essayer toutes les possibilités pour toutes les cases et est censé trouver toutes les solutions possibles d'une grille donnée.
 
Le problème :
 
Seulement mon programme trouve toujours (sur plusieurs grilles testées) au moins une solution, mais jamais l'ensemble des solutions de la grille traitée.  
 
J'ai pour exemple 3 grilles possédant respectivement 1, 18 et 9474 solutions (toutes 3 composées des mêmes chiffres, avec quelques-uns enlevés pour les grilles à 18 et 9474 solutions).
 
Lorsque je traite la première grille, pas de problème, il trouve l'unique solution.
Pour la deuxième, il m'en trouve également une seule.
Et pour la dernière il m'en trouve 3800 et des poussières.
 
Ayant déjà testé mon programme dans tous les sens et étant à court d'idées, j'aimerais savoir si vous aviez des propositions sur l'origine du problème.

Message cité 1 fois
Message édité par tata_monique le 09-06-2007 à 22:28:49
Reply

Marsh Posté le 09-06-2007 à 21:48:07   

Reply

Marsh Posté le 09-06-2007 à 22:13:31    

tata_monique a écrit :

Bonjour à tous,

 

Donc voilà, j'ai terminé de coder mon solveur de sudoku.

 

Le principe du programme :

 

Il est basé sur le principe de backtracking à partir d'une liste de candidats.

 

En gros, au début du programme, il remplit pour chaque case d'un tableau 9x9 (la grille de sudoku) une liste chainée représentant chaque "candidat" d'une case, càd chaque nombre possible pour cette case.

 

L'algorithme de backtracking en lui même est un algo récursif qui remplit la première case avec le premier candidat de cette case, puis passe à la case à remplir suivante et est rappelé lui même sur cette case.

 

Il va donc essayer toutes les possibilités pour toutes les cases et est censé trouver toutes les solutions possibles d'une grille donnée.

 

Le problème :

 

Seulement mon programme trouve toujours (sur plusieurs grilles testées) au moins une solution, mais jamais l'ensemble des solutions de la grille traitée.

 

J'ai pour exemple 3 grilles possédant respectivement 1, 18 et 9474 solutions (toutes 3 composées des mêmes chiffres, avec quelques-uns enlevés pour les grilles à 18 et 9474 solutions).

 

Lorsque je traite la première grille, pas de problème, il trouve l'unique solution.
Pour la deuxième, il m'en trouve également une seule.
Et pour la dernière il m'en trouve 3800 et des poussières.

 

Ayant déjà testé mon programme dans tous les sens et étant à court d'idées, j'aimerais savoir si vous aviez des propositions sur l'origine du problème.

 

salut tata_monique,
je pense que ton problème peut avoir des origines diverses et variées, relatives au comptage du nombre de solutions jusqu'à l'algo lui même .... Peux tu poster le code ? Ou le plus important si c'est long


Message édité par in_your_phion le 09-06-2007 à 22:14:05
Reply

Marsh Posté le 09-06-2007 à 22:28:03    

Ce programme représente un de mes projets de fin d'année donc je vais éviter de poster l'intégralité.
Néanmoins voilà les deux fonctions principales, en priant pour que mes "collègues" soient ne tombent pas dessus.
 

Code :
  1. Boolean Admissible(int c, int i, int j)
  2. {
  3.      int a,b,amin,bmin;
  4.      for (a = 0; a < 9; a++)
  5.      {
  6.          if (Grille[i][a] == c)
  7.          {
  8.              return faux;
  9.          }
  10.      }
  11.      for (a = 0; a < 9; a++)
  12.      {
  13.          if (Grille[a][j] == c)
  14.          {
  15.              return faux;
  16.          }
  17.      }
  18.      if (i < 3) amin = 0;
  19.      if ((i >= 3) && (i < 6)) amin = 3;
  20.      if ((i >= 6) && (i < 9)) amin = 6;
  21.      if (j < 3) bmin = 0;
  22.      if ((j >= 3) && (j < 6)) bmin = 3;
  23.      if ((j >= 6) && (j < 9)) bmin = 6;
  24.      for (a = amin; a < (amin + 3); a++)
  25.      {
  26.          for (b = bmin; b < (bmin + 3); b++)
  27.          {
  28.              if (Grille[a][b] == c)
  29.              {
  30.                    return faux;
  31.              }
  32.          }
  33.      }
  34.      return vrai;
  35. }
  37. // Fonction Colorier => Backtracking
  39. void Colorier(Liste c, int i, int j)     // Coloriage de la case
  40. {
  41.     if (Candidats[i][j] != NULL) Grille[i][j] = c->Valeur;
  42.     nbcc++;
  44.     if (nbcc == 81)     // Une solution a été trouvée
  45.     {
  46.         nbsol++;
  48.     // Ecriture du résultat dans Log.txt
  49.     int x, y;
  50.     fprintf(f, "\n-------------------------------------\n" );
  51.     for (x = 0 ; x < 9 ; x++)
  52.     {
  53.       fprintf(f, "|" );
  54.       for (y = 0 ; y < 9 ; y++)
  55.       {
  56.           fprintf(f, " %ld |", Grille[x][y]);
  57.       }
  58.       fprintf(f, "\n-------------------------------------\n" );
  59.     }
  60.     fprintf(f, "\n=== nbcc = %ld ===\n\n", nbcc);
  62.     }
  63.     else     // on traite la case suivante
  64.     {
  65.          do
  66.          {
  67.             j++;
  68.             if (j == 9)
  69.             {
  70.                j = 0;
  71.                i++;
  72.             }
  73.          }
  74.          while ( (i != 9) && (Candidats[i][j] == 0) );
  75.          if (i != 9)
  76.          {
  77.              c = Candidats[i][j];
  78.              while (c != NULL)
  79.              {
  80.                    if (Admissible(c->Valeur, i, j))
  81.                    {
  82.                        Colorier(c, i, j);
  83.                    }
  84.                    c = c->Suivant;
  85.              }
  86.          }
  87.     }
  89.     // Libération de la case
  90.     Grille[i][j] = 0;
  91.     nbcc--;
  92. }


 
Les variables globales nbcc et nbsol désignent respectivement le Nombre de Cases Coloriées (donc si == 81 la grille est finie) et le Nombre de Solutions.
 
Grille est un tableau d'entiers de 9x9
Candidats est un tableau de pointeur de 9x9 dont chaque pointeur pointe vers une liste chainée des candidats de la case concernée.

Reply

Marsh Posté le 09-06-2007 à 22:41:32    

Ce que je te dis ne corrigera pas ton pr blème mais te permettra de gagner un peu de temps :
Tu peux remplacer

Code :
  1. if (i < 3) amin = 0;
  2.      if ((i >= 3) && (i < 6)) amin = 3;
  3.      if ((i >= 6) && (i < 9)) amin = 6;
  4.      if (j < 3) bmin = 0;
  5.      if ((j >= 3) && (j < 6)) bmin = 3;
  6.      if ((j >= 6) && (j < 9)) bmin = 6;

par

Code :
  1. if (j < 3)
  2.           bmin = 0;
  3.       else
  4.       if (i < 6)
  5.         amin = 3;
  6.      else
  7.      if (i < 9)
  8.         amin = 6;
  10.      if (j < 3)
  11.        bmin = 0;
  12.      else
  13.      if (j < 6)
  14.         bmin = 3;
  15.      else
  16.      if (j < 9)
  17.         bmin = 6;


Message édité par Trap D le 09-06-2007 à 22:43:01
Reply

Marsh Posté le 10-06-2007 à 01:23:26    

humpf je suis pas sûr de tout comprendre car je ne connais pas l'algo et je ne vois pas ou sont déclarées (en global ?) les tableaus Candidats et Grille....

 

Un truc que je ne comprend pas, j'espère que je ne dis pas de conneries  :sweat:, dans la fonction Colorier() :

 

tu fais un test avec :

Code :
  1. if (Candidats[i][j] != NULL)
 

Ce qui à mon sens voudrait dire que Candidant est un tableau de pointeurs, dans le style de

Code :
  1. int * Candidats[m][n];
 

Or, plus loin tu fais un test sur une valeur :

Code :
  1. while ( (i != 9) && (Candidats[i][j] == 0) );
 

Sinon pour le printf si tu es sous linux tu peux utiliser la redirection standard ">", c'est plus simple que de créer un fichier avec un fopen(), etc...


Message édité par in_your_phion le 10-06-2007 à 01:23:58
Reply

Marsh Posté le 11-06-2007 à 08:01:47    

Tu le fermes correctement ton fichier de sortie? Ca me fait penser a un probleme de flush ton truc.

Reply

Marsh Posté le 11-06-2007 à 09:25:44    

On peut savoir pourquoi tu as effacé ton précédent topic ? [:petrus dei]


Message édité par Elmoricq le 11-06-2007 à 09:26:04
Reply

Marsh Posté le 11-06-2007 à 09:48:53    

Euh oui [:petrus dei]


---------------
Töp of the plöp
Reply

Sujets relatifs:

Leave a Replay

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