Partie résolution du sudoku, aide svp Fermé

Question

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 #include #include using std::stack; using std::queue; struct position { int lig; int col; }; queue candidat(position & pos,const int grille [9][9]); struct essai { int lig; int col; queuefl; }; void solution(position & pos,int grille[9][9]) { essai fi; stackes; queuef; 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<

mamiemando · Answer

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 !@+

Alain15 · Answer

bonjour, pour l'indentation ca marche pas quand on copie colle ici #include #include #include using std::stack; using std::queue; struct position { int lig; int col; }; queue candidat(position & pos,const int grille [9][9]); struct essai { int lig; int col; queuefl; }; void solution(position & pos,int grille[9][9]) { essai fi; stackes; queuef; 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 · Answer

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 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 candidat(position & pos,std::vector > & 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

Franck · Answer

bon je v essayer ca... j'ai un peu fais autrement, je verrais bien...je te tiens au courant...

Marden · Answer

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

Marden · Answer

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...

mamiemando · Answer

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

Partie résolution du sudoku, aide svp

7 réponses

Discussions similaires