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

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Mon solveur de s.u.d.o.k.u marche mais trouve pas toutes les solutions

tata_monique

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

Publicité

in_your_phion

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

tata_monique

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 :

Boolean Admissible(int c, int i, int j)
{
int a,b,amin,bmin;
for (a = 0; a < 9; a++)
{
if (Grille[i][a] == c)
{
return faux;
}
}
for (a = 0; a < 9; a++)
{
if (Grille[a][j] == c)
{
return faux;
}
}
if (i < 3) amin = 0;
if ((i >= 3) && (i < 6)) amin = 3;
if ((i >= 6) && (i < 9)) amin = 6;
if (j < 3) bmin = 0;
if ((j >= 3) && (j < 6)) bmin = 3;
if ((j >= 6) && (j < 9)) bmin = 6;
for (a = amin; a < (amin + 3); a++)
{
for (b = bmin; b < (bmin + 3); b++)
{
if (Grille[a][b] == c)
{
return faux;
}
}
}
return vrai;
}
// Fonction Colorier => Backtracking
void Colorier(Liste c, int i, int j) // Coloriage de la case
{
if (Candidats[i][j] != NULL) Grille[i][j] = c->Valeur;
nbcc++;
if (nbcc == 81) // Une solution a été trouvée
{
nbsol++;
// Ecriture du résultat dans Log.txt
int x, y;
fprintf(f, "\n-------------------------------------\n" );
for (x = 0 ; x < 9 ; x++)
{
fprintf(f, "|" );
for (y = 0 ; y < 9 ; y++)
{
fprintf(f, " %ld |", Grille[x][y]);
}
fprintf(f, "\n-------------------------------------\n" );
}
fprintf(f, "\n=== nbcc = %ld ===\n\n", nbcc);
}
else // on traite la case suivante
{
do
{
j++;
if (j == 9)
{
j = 0;
i++;
}
}
while ( (i != 9) && (Candidats[i][j] == 0) );
if (i != 9)
{
c = Candidats[i][j];
while (c != NULL)
{
if (Admissible(c->Valeur, i, j))
{
Colorier(c, i, j);
}
c = c->Suivant;
}
}
}
// Libération de la case
Grille[i][j] = 0;
nbcc--;
}

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.

Trap D

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 :

if (i < 3) amin = 0;
if ((i >= 3) && (i < 6)) amin = 3;
if ((i >= 6) && (i < 9)) amin = 6;
if (j < 3) bmin = 0;
if ((j >= 3) && (j < 6)) bmin = 3;
if ((j >= 6) && (j < 9)) bmin = 6;

par

Code :

if (j < 3)
bmin = 0;
else
if (i < 6)
amin = 3;
else
if (i < 9)
amin = 6;
if (j < 3)
bmin = 0;
else
if (j < 6)
bmin = 3;
else
if (j < 9)
bmin = 6;

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

in_your_phion

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 :

if (Candidats[i][j] != NULL)

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

Code :

int * Candidats[m][n];

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

Code :

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

Ace17

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

Elmoricq

Modérateur

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

_darkalt3_

Proctopathe

Euh oui [:petrus dei]

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

FORUM HardWare.fr

Programmation

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

Page générée en 0.079 secondes