Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1360 connectés 

  FORUM HardWare.fr
  Programmation
  C

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

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

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

n°1572802
tata_moniq​ue
Posté le 09-06-2007 à 21:48:07  profilanswer
 

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
mood
Publicité
Posté le 09-06-2007 à 21:48:07  profilanswer
 

n°1572807
in_your_ph​ion
Posté le 09-06-2007 à 22:13:31  profilanswer
 

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
n°1572811
tata_moniq​ue
Posté le 09-06-2007 à 22:28:03  profilanswer
 

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. }
  36. // Fonction Colorier => Backtracking
  37. void Colorier(Liste c, int i, int j)     // Coloriage de la case
  38. {
  39.     if (Candidats[i][j] != NULL) Grille[i][j] = c->Valeur;
  40.     nbcc++;
  41.     if (nbcc == 81)     // Une solution a été trouvée
  42.     {
  43.         nbsol++;
  44.     // Ecriture du résultat dans Log.txt
  45.     int x, y;
  46.     fprintf(f, "\n-------------------------------------\n" );
  47.     for (x = 0 ; x < 9 ; x++)
  48.     {
  49.       fprintf(f, "|" );
  50.       for (y = 0 ; y < 9 ; y++)
  51.       {
  52.           fprintf(f, " %ld |", Grille[x][y]);
  53.       }
  54.       fprintf(f, "\n-------------------------------------\n" );
  55.     }
  56.     fprintf(f, "\n=== nbcc = %ld ===\n\n", nbcc);
  57.     }
  58.     else     // on traite la case suivante
  59.     {
  60.          do
  61.          {
  62.             j++;
  63.             if (j == 9)
  64.             {
  65.                j = 0;
  66.                i++;
  67.             }
  68.          }
  69.          while ( (i != 9) && (Candidats[i][j] == 0) );
  70.          if (i != 9)
  71.          {
  72.              c = Candidats[i][j];
  73.              while (c != NULL)
  74.              {
  75.                    if (Admissible(c->Valeur, i, j))
  76.                    {
  77.                        Colorier(c, i, j);
  78.                    }
  79.                    c = c->Suivant;
  80.              }
  81.          }
  82.     }
  83.     // Libération de la case
  84.     Grille[i][j] = 0;
  85.     nbcc--;
  86. }


 
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.

n°1572812
Trap D
Posté le 09-06-2007 à 22:41:32  profilanswer
 

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;
  9.      if (j < 3)
  10.        bmin = 0;
  11.      else
  12.      if (j < 6)
  13.         bmin = 3;
  14.      else
  15.      if (j < 9)
  16.         bmin = 6;


Message édité par Trap D le 09-06-2007 à 22:43:01
n°1572822
in_your_ph​ion
Posté le 10-06-2007 à 01:23:26  profilanswer
 

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
n°1572999
Ace17
Posté le 11-06-2007 à 08:01:47  profilanswer
 

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

n°1573009
Elmoricq
Modérateur
Posté le 11-06-2007 à 09:25:44  profilanswer
 

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
n°1573020
_darkalt3_
Proctopathe
Posté le 11-06-2007 à 09:48:53  profilanswer
 

Euh oui [:petrus dei]


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

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

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

 

Sujets relatifs
getElementById ne marche pas avec mon doc XML[RESOLU]Array et fonction max qui ne marche pas ...
[PHP/MYSQL] pourquoi ce script marche pas ?[Access 2000 et SQL] Count, Group by et Sort => le sort ne marche pas
Bug Menu IE 6 (marche sous FF et IE7)[Resolu] [XEmacs] Controle-Espace ne marche pas
[Site Internet] quelles questions se poser pour quelles solutions ?[resolu]icher une image dont le lien se trouve dans une base de donnée
Blabla@Programmation !! Y marche c'ui là (en attendant mieux)Parse error, je ne trouve pas la solution
Plus de sujets relatifs à : Mon solveur de s.u.d.o.k.u marche mais trouve pas toutes les solutions


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR