Sudoku

Version imprimable

14/12/2005, 21h23
Arnaud F.

Sudoku

Voila, voila, dans le cadre d'un projet de TP en informatique, on doit faire un programme permettant de résoudre un Sudoku, seulement il y a 2 ou 3 choses que je ne comprend pas dans l'énoncé....
pour trouver la solution en fait, on utilise une pile ...
" Pour chaque essai, on conserve dans une structure essai:
- la posistion de la case pour laquelle on fait l'essai
la file des prochains symboles à essayer pour cette case. Cette file est une partie de la file des candidats initiaux.
Chaque structure est conservée sur une pile d'essais appelée essais.

Voila j'en viens a ma question, comment il faut faire ce type de structure en C++ ???
Je ne vraiment pas commment il faut la faire, si quelqu'un pouvais me guider ... :?
14/12/2005, 21h38
JolyLoic

pile : std::stack
file : std::queue
14/12/2005, 21h42
xxiemeciel

Salut,

dois tu les reimplémenter ou bien peux tu utiliser la STL ?

XXiemeciel
14/12/2005, 22h26
Arnaud F.

j'ai fait une fonction "estDansLigne", une "estDansRegion" et une "estDansColonne", j'ai fait une fonction "candidat" qui fait appel au 3 fonctions précédentes pour déterminer quels sont les candidats possibles pour une case donnée... je stocke ce résultat sous forme de file...

Maintenant faut que je passe a la résolution proprement dite, et j'ai pour seule aide l'énoncé que je vous ai recopié dans le premier post ...

Citation:

Envoyé par xxiemeciel

dois tu les reimplémenter ou bien peux tu utiliser la STL ?

Comment sa ???
15/12/2005, 09h43
Aurelien.Regat-Barrel

La pile et la file sont des structures toutes prêtes en C++, dans la STL.
15/12/2005, 10h19
Matthieu Brucher

Re: Sudoku

Citation:

Envoyé par bucheron67

Voila, voila, dans le cadre d'un projet de TP en informatique, on doit faire un programme permettant de résoudre un Sudoku, seulement il y a 2 ou 3 choses que je ne comprend pas dans l'énoncé....
pour trouver la solution en fait, on utilise une pile ...
" Pour chaque essai, on conserve dans une structure essai:
- la posistion de la case pour laquelle on fait l'essai
la file des prochains symboles à essayer pour cette case. Cette file est une partie de la file des candidats initiaux.
Chaque structure est conservée sur une pile d'essais appelée essais.

Voila j'en viens a ma question, comment il faut faire ce type de structure en C++ ???
Je ne vraiment pas commment il faut la faire, si quelqu'un pouvais me guider ... :?

T'es obligé d'y aller en force brute ? C'est plus amusant de résoudre un sudoku par connaissance, avec des règles de résolution qu'en testant bêtement toutes les solutions !
15/12/2005, 16h34
d-a-v-e

J ai justement commence il y a quelques jours a ecrire un programme qui resou les sudoku par regles logiques.
J ai aussi fait un tableau a 2 index de 81 sur 9 pour tester toutes les possibilites de chaque case, si dans une case il y a que une possibilite , ou bien que une possibilite peut etre seulement dans une case cette possibilite rentre dans la case!
15/12/2005, 22h02
Arnaud F.

Eh bien "Miles" sache qu'il s'agit d'un TP noté en cours et donc on a plutot intérpet a suivre les règles imposé...

Ont doit faire une structure de pile, et faire des essais, donc voila je sais pas comment faut faire sa ...
16/12/2005, 13h32
Matthieu Brucher

C'est vraiment tordu comme énoncé et vraiment pas génial du tout. Je ne dirai rien sur ton prof... Le pire, c'est que j'ai du mal à voir ce qu'il veut que vous fassiez exactement tellement la phrase est floue !
Je ne vois vraiment pas où une liste est indispensable dans la structure essai, une liste qui contiendrai la liste des prochaines valeurs possibles, normalement on utilise une pile pour parcourir un arbre en profondeur, l'arbre ici, je le vois comme étant l'arbre des grilles possibles, la profondeur étant le nombre de cases fixées suppélemntaires, et si on arrive à la profondeur 81, la grille est résolue...
16/12/2005, 17h47
Arnaud F.

Bon ben le mieux a faire je crois, c'est de voir a la rentrée ce qu'il attendait exactement, en attendant, ben merci quand meme...

en fait, je viens de comprendre, c'est chaud mais bon: j'ai une autre question a posé:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 struct position { int lig; int col; }; struct essai { position pos; queue<int> q; }; void resoudre(int grille[9][9]) { essai e; stack<essai> p; queue<int> f; for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { int s=essai.top().q.size(); if(grille[i][j]==0) { e.pos.lig=i; e.pos.col=j;
Y a une suite évidemment, mais j'aiumerais savoir pourquoi quand je compile il me dis que le

Code:

e.pos.lig=i;

il me dit que "expected primary-expression before "." token

Je comprend pas pourquoi il me met cela a chaque ligne ou j'ai plus d'un point (par ex e.pos.col)

16/12/2005, 21h32
Jean-Marc.Bourguet
Quand tu as d'autre question, ouvre un nouveau fil...

Quand tu postes du code avec un problème, essaie de poster un code minimum (enlève tout ce qui n'est pas nécessaire), montrant le problème mais n'en ayant pas d'autres (ici il manque les inclusions, la fin de la fonction).
Citation:
Envoyé par bucheron67

Code:

1 2 3 4 5 6 7 struct essai { position pos; queue<int> q; }; int s=essai.top().q.size();
essai est un type, pas un objet.

Citation:

Je comprend pas pourquoi il me met cela a chaque ligne ou j'ai plus d'un point (par ex e.pos.col)

Par contre là ça me semble correct.
16/12/2005, 21h44
Arnaud F.

euh oui, je sais pour le

Citation:

int s=essai.top().q.size();

je l'ai enlevé, c'etait juste un test ...

mais je ne comprend pas pourquoi il me dis a chaque fois que j'ai une chose du genre

Citation:

essai.top().q.pop();

, qu'il me dise qu'il y a une erreur a la compilation, c'est possible que sa vienne du compilateur ???

(dsl pour le dernier post, premiere fois que je post un code... :oops: )

Citation:

Envoyé par bucheron67

je ne comprend pas pourquoi il me dis a chaque fois que j'ai une chose du genre

Citation:

essai.top().q.pop();

Si tu as un problème avec essai, c'est normal, c'est un nom de type. Si tu as un problème avec e.pos.lig=i;, c'est a priori pas normal. J'ai pris ton code et l'ai complèté comme suit:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <queue> #include <stack> using namespace std; struct position { int lig; int col; }; struct essai { position pos; queue<int> q; }; void resoudre(int grille[9][9]) { essai e; stack<essai> p; queue<int> f; for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { if(grille[i][j]==0) { e.pos.lig=i; e.pos.col=j; } } } }
je n'ai pas de problème de compilation. Si tu en as, poste le code complet qui permet de le reproduire et indique précisément quel message d'erreur tu as.

16/12/2005, 22h25
Arnaud F.

Je sais pas comment faire pour poster le source en complet sans faire qu'utiliser les balises code, et vu que le programme fait une centaine de ligne, j'aimerais ne pas les poster ici...

En tout cas le message d'erreur est le suivant:

Code:

... primary-expression before " . " token

Il me met cette erreur a chaque fois qu'il rencontre une ligne du type

Code:

e.pos.lig=i;

ou

Code:

e.top().q.pop();
17/12/2005, 08h25
Jean-Marc.Bourguet

Citation:

Envoyé par bucheron67

Je sais pas comment faire pour poster le source en complet sans faire qu'utiliser les balises code

Quel est le problème des balises codes?

Citation:

et vu que le programme fait une centaine de ligne, j'aimerais ne pas les poster ici...

Et bien tu commences par supprimer ce qui n'a pas de rapport avec ton problème.

Citation:

Il me met cette erreur a chaque fois qu'il rencontre une ligne du type

Code:

e.pos.lig=i;

ou

Code:

e.top().q.pop();

Sans voir les déclarations de tous ces noms, il est impossible de se prononcer. J'ai donné du code qui compile sans problème, l'as-tu essayé?

J'ai essayé ce que tu ma proposé et sa ne marche pas :x , voila mon code...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cassert>
 
using namespace std;
 
struct position
{
	int lig;
	int col;
};
struct essai
{
	position pos;
	queue<int> q;
};
 
void resoudre(int grille[9][9])
{
	essai e;
	stack<essai> p;
	queue<int> f;
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			if(grille[i][j]==0)
			{
				e.pos.lig=i;
				e.pos.col=j;
				e.q=candidats(e.pos,grille);
				essai.push(e);
			}
			while(!essai.empty())
 
 			{
 
				if (essai.top().q.size()==1)
 
				{
					grille[essai.pos.lig][essai.pos.col]=essai.top().q.front();
 
					essai.pop();  
 
				}
			}
		}
	}
}
int main()
 
{
 
	int grille[9][9]={0};
	saisie(grille);
	afficher(grille);
	resoudre(grille);
 
}

Voila la procedure qui ne marche pas (je l'ai pas encore terminée, mais sa devrait la compiler quand meme ...
J'ai regardé, le

Code:

1
2
e.pos.lig=i;
e.pos.col=j;

ne pose plus de probleme à la compilation, c'est la suite qui pose probleme, les lignes d'apres ...

17/12/2005, 15h11
Arnaud F.

mouarf, je suis vraiment un mauvais, j'appelle ma pile p et quand je l'utilise je met "sssai" pas etonnat que sa marche pas, dsl du dérangement et merci a tous...
8) :oops: