Partie résolution du sudoku, aide svp [Fermé]

Signaler
-
mamiemando
Messages postés
29238
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mars 2020
-
Bonsoir,

je suis entrain de faire un prog de c++ pour résoudre un sudoku.je le fais pour m'entrainer...

Voila j'ai un problème, il résoud que la premiere ligne sur les 9, ils continuent pas, je comprend pas....

voici le code:

#include <iostream>
#include <queue>
#include <stack>

using std::stack;
using std::queue;

struct position
{
int lig;
int col;
};

queue <int> candidat(position & pos,const int grille [9][9]);

struct essai
{
int lig;
int col;
queue<int>fl;
};

void solution(position & pos,int grille[9][9])
{
essai fi;
stack<essai>es;
queue<int>f;

int i=0;
int j=0;
while(i<9)
{



while(j<9)
{


if(grille[i][j]==0)
{
pos.lig=i;
pos.col=j;
f=candidat(pos,grille);

// std::cout<<f.front()<<std::endl;

if(f.empty())
{
es.pop();
i=(es.top()).lig;
j=(es.top()).col;
f=((es.top()).fl);
grille[i][j]=f.front();
f.pop();
fi.lig=i;
fi.lig=j;
fi.fl=f;

}
else
{


grille[i][j]=f.front();

f.pop();
fi.lig=i;
fi.col=j;
fi.fl=f;
es.push(fi);

}




}
j++;
}
i++;

}


}

si vous avez des questions, n'hesitez pas...
merci de m'aider ...

7 réponses

Messages postés
29238
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mars 2020
6 812
Ben commence par mettre :
1) un peu d'indentation (par exemple en utilisant les balises codes mises à ta disposition, au dessus de la boite dans laquelle tu saisis tes messages)
2) des vrais noms de variables (un peu plus que deux lettre)
3) un peu de commentaire

Comme ça on pourra essayer de voir ce que tu fais ;-)

Par ailleurs il faudrait qu'on ait un fichier qui compile parce que là on a même pas de main pour voir dans quel ordre tu appelles tes fonctions !

@+
bonjour, pour l'indentation ca marche pas quand on copie colle ici

#include <iostream>
#include <queue>
#include <stack>

using std::stack;
using std::queue;

struct position
{
int lig;
int col;
};

queue <int> candidat(position & pos,const int grille [9][9]);

struct essai
{
int lig;
int col;
queue<int>fl;
};

void solution(position & pos,int grille[9][9])
{
          essai fi;
          stack<essai>es;
          queue<int>f;

         int i=0;
         int j=0;
         while(i<9)
        {



              while(j<9)
             {


                     if(grille[i][j]==0)
                     {
                            pos.lig=i;
                            pos.col=j;
                            f=candidat(pos,grille);



                          if(f.empty())
                           {
                                 es.pop();
                                  i=(es.top()).lig;
                                  j=(es.top()).col;
                                  f=((es.top()).fl);
                                  grille[i][j]=f.front();
                                 f.pop();
                                fi.lig=i;
                                fi.lig=j;
                                fi.fl=f;
 
                                }
                                 else
                                 {


                                       grille[i][j]=f.front();

                                       f.pop();
                                       fi.lig=i;
                                       fi.col=j;
                                       fi.fl=f;
                                       es.push(fi);

                                  }




}
j++;
}
i++;

}


} 


je suis désolé, j'avais bien indenté mon programme mais dans cette boite de message, c trop dur de le faire correctement...

Je vous explique comment le programme fonctionne...

En faite il y a 3 fonctions booléenes, estDansLigne,estDansColonne,estDansRegion qui recherche si la valeur est dans la ligne, la colonne, la région, si oui, la fonction renvoi vrai...

Ces 3 fonctions sont utilisés dans la fonction candidat qui renvoi la file des candidats possibles, les chiffres possibles...

Puis ce candidat est utilisé dans la procédure sol.

On parcoure le tableau de 9*9, si la case est égale à 0, on cherche le nombre de candidats, on insere la premiere valeur à la place du 0, on supprime la valeur de tete de la file, et on met la position, ligne, colonne, et la file dans une structure, et on met cette structure sur une pile de structure.
Si il n'y a pas de candidat pour une case, on dépile la pile, et on ressaye le prochain candidat de la file, si y en a tj pas, on dépile tj....

Voila un peu l'explication...

Dans la main, y a que appelez la procédure, et la fonction affichage qui affiche le tableau...

Je vous remercie de votre aide
Messages postés
29238
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mars 2020
6 812
En fait il nous faudrait tout le code pour débugger. Notamment la fonction candidat. Quelques petites suggestions (même si ça ne changera rien) : remplace les :
int i=0;
while(i<9){
  ...
  i++
}

par :
for(unsigned int i=0;i<9;++i){
...
}


Par ailleurs plutôt que de travailler sur des int[9][9] :
queue <int> candidat(position & pos,const int grille [9][9]);

je travaillerais plutôt sur des vector, passés en référence pour que le programme soit plus optimisé ;-)
std::queue <int> candidat(position & pos,std::vector<std::vector<int> > & grille);


Pour la rcherche, tu es parti sur une approche "brute forcing" ce qui est à peu de chause près un branch & bound (cf cours de recherche opérationelle). Tu as moyen d'accélerer ton programme en coupant des branches de ton arbre de recherche sans avoir à les explorer (critère de coupe) (ici par exemple ne pas mettre un nombre s'il ne valide pas les contraintes imposées par les règles du sudoku. Je ne sais pas si tu as pris ce point en compte dans ta fonction candidat.

Voilà quelques pistes, j'espère que ça t'aidera. Si tu as besoin encore d'un coup de main je te donne rendez vous après les vacances de Noël ;-)

Bonne chance
Bonsoir, merci de votre réponse...
j'utilise pas des vector car je n'ai pas encore appris ceci en c++.
j'ai pas mis des for a la place des while car je modifie i et j, les compteurs et c pas admis par les for, ca fait totalement buger le programme...
en faite le problème est qu'il rempli que la premiere ligne, donc je me demande si y a pas un problème au niveau des boucles, ca reste sur la premiere ligne...
encore merci
> Franck
Tu serais pas en dut info à Illkirch par hazard ???

Je te file le code qui marche. Mais j'ai pas encore fais la boucle qui donnes toutes les solutions possibles.

while(i<9)
{
j=0;

while(j<9)
{

if(grille[i][j]==0)
{
//On initialise les données de la pile
e.pos_case.lig=i;
e.pos_case.col=j;
e.candidats=candidats(e.pos_case,grille);

/*
Tant que notre file de candidats est vide et que la pile des essais
n'est pas vide, on récupère le sommet de pile, on dépile, on assigne
à i et à j la valeurs de la position précédente et on remet la case à 0.
*/
while(e.candidats.empty() and !essais.empty())
{

e=essais.top();
essais.pop();
i=e.pos_case.lig;
j=e.pos_case.col;
grille[i][j]=0;


}

/*
Si notre file de candidat n'est pas vide, on assigne la première valeur
de la file à la position courante dans la grille, on défile et on
mémorise le tout dans la pile.
*/
if(!e.candidats.empty())
{

grille[i][j]=e.candidats.front();
e.candidats.pop();
essais.push(e);

}

}


j=j+1;


}

i=i+1;

}
bon je v essayer ca... j'ai un peu fais autrement, je verrais bien...
je te tiens au courant...
Messages postés
1072
Date d'inscription
dimanche 11 février 2001
Statut
Membre
Dernière intervention
29 janvier 2006
206
Je viens de programmer (en Javascript) un "solveur" de grille, dont l'algorithme me semble très basique.
Pour chaque case à 0 (non encore remplie), on élimine les chiffres déjà présents dans la ligne, dans la colonne et dans la zone.

S'il en reste plusieurs (candidats), on cherche une autre case.
S'il n'en reste qu'un, c'est la solution pour cette case.
S'il n'en reste aucun, c'est qu'il y a une erreur dont la grille originelle, ou dans la solution intermédiaire.

http://ardenneaparis.free.fr/mesScripts/sudoku.htm
Messages postés
1072
Date d'inscription
dimanche 11 février 2001
Statut
Membre
Dernière intervention
29 janvier 2006
206
Je crains d'avoir été un peu léger !!! Ce qui fonctionnait avec les grilles "faciles" ne suffit pas avec cette simple .
Il faut en ajouter d'autres comme placer un chiffre déjà présent sur 2 lignes (ou 2 colonnes) et une stratégie combinant les différentes règles...
Messages postés
29238
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mars 2020
6 812
Non ça ne marche pas comme approche, car si tu fais une mauvaise supposition (un choix qui te conduira forcément à un echec), ton algorithme ne trouvera jamais la solution.

Je t'invite à regarder ce qu'est un Branch & bound et à t'intéresser au problématiques de recherche opérationnelle, par exemple les CSP (constraint satisfaction program)... si tu aimes les maths ;-)

Bonne chance