Partie résolution du sudoku, aide svp
Fermé
Alain15
-
21 déc. 2005 à 19:52
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 16 janv. 2006 à 20:41
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 16 janv. 2006 à 20:41
A voir également:
- Partie résolution du sudoku, aide svp
- Partie entière en c ✓ - Forum C
- Flouter une partie d'une photo - Guide
- Resolution 1366x768 - Forum TV & Vidéo
- Télécharger sudoku gratuit pour mobile - Télécharger - Puzzle & Réflexion
- Recherche de partie infini warzone 2 - Forum Jeux PC
7 réponses
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
22 déc. 2005 à 00:42
22 déc. 2005 à 00:42
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 !
@+
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
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
#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
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
22 déc. 2005 à 19:42
22 déc. 2005 à 19:42
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 :
par :
Par ailleurs plutôt que de travailler sur des int[9][9] :
je travaillerais plutôt sur des vector, passés en référence pour que le programme soit plus optimisé ;-)
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
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
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
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;
}
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;
}
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Marden
Messages postés
1072
Date d'inscription
dimanche 11 février 2001
Statut
Membre
Dernière intervention
29 janvier 2006
208
7 janv. 2006 à 15:59
7 janv. 2006 à 15:59
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
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
Marden
Messages postés
1072
Date d'inscription
dimanche 11 février 2001
Statut
Membre
Dernière intervention
29 janvier 2006
208
8 janv. 2006 à 00:58
8 janv. 2006 à 00:58
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...
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...
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
16 janv. 2006 à 20:41
16 janv. 2006 à 20:41
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
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
