Résolution Sudoku, demande aide...

**Alain15** · 22/12/2005, 15h12

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:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
#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++;
 
	}
 
 
}

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...
merci de m'aider...

Alain

**reggae** · 23/12/2005, 16h11

http://www.developpez.net/forums/viewtopic.php?t=432651

**Alain15** · 23/12/2005, 18h17

jai dja regardé, mais j'ai pas le meme problème...

merci

**Matthieu Brucher** · 23/12/2005, 18h46

En même temps, si tu ne réinitialises pas j à la deuxième boucle, il a peu de chances de parcourir tout le tableau.
Pour éviter ces ennuis, il y a une instruction géniale : for.

**Arnaud F.** · 26/12/2005, 18h46

Dis moi tu serais ps en DUT info???

comme par hasard, j'utilise les meme fonctions et les meme noms de variables et les meme structures

lol, si ta besoin d'aide, je peux t'aider

et puis oui, les boucles for sont tellement plus impl et pratique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
for (int i=0; i<9 ; i++)
{
     for (int j=0; j<9; j++)
      {
         ...

et puis tu recherche tes candidats mais tu ne les met pas dans la pile d'essais, pas bien ^^ et puis il y a une faute dans ton code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
               fi.lig=i; 
               fi.lig=j; 
               fi.fl=f;

c'est pas plutot :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
               fi.lig=i; 
               fi.col=j; 
               fi.fl=f;

sa peux venir de la

enfin non presque sur meme

**Alain15** · 26/12/2005, 21h36

salut,

oui je suis en dut info.
J'ai fait le prog du sudo mais il remplit que la premiere ligne...
je comprend vraiment pas...

si t'aurais le tps de juste poster la partie solution pr voir d'où vient l'erreur ca serait sympa...

**Matthieu Brucher** · 26/12/2005, 22h02

Envoyé par Miles

En même temps, si tu ne réinitialises pas j à la deuxième boucle, il a peu de chances de parcourir tout le tableau.
Pour éviter ces ennuis, il y a une instruction géniale : for.

Alain, si t'es aveugle, préviens moi, que je ne réécrives pas inutilement les solutions...

**Alain15** · 27/12/2005, 09h48

je suis pas aveugle lol

mais j'ai mis fort au début, mais vu que je change la valeur de i et j dans la boucle en fonction de la pile, ca bug lorsque je lance le programme...
j'aimis while, pas de problème...
le seul problème c'est qu'il parcoure une seul ligne...
ou vois tu que j'initialise" pas la boule pour j??

int i=0;
int j=0;

**Matthieu Brucher** · 27/12/2005, 10h23

Tu l'intialises une fois à l'extérieur de ta boucle principale, il te faut le réinitialiser à l'intérieur.
Tu as déjà fait une exécution pas à pas dans un débuggeur de ton programme ?
Et pourquoi tu ne fais pas comme bucheron en prenant des boucles for ? Parce que c'est ça ton problème, tu crois initialiser j au bon moment, mais c'est clairement pas le bon moment quand tu passes un peu de temps à lire ce que tu as écrit.

**Alain15** · 27/12/2005, 10h34

je viens de mettre un for... mais quand je mets ca, quand le prog démarre, il bug, puis apres le message killed apparait...
je poste dans 10min le code source...

je vous remercie

**Alain15** · 27/12/2005, 10h57

voici le code source de ma partie solution et de ma partie candidat...
qu'est ce qui est pas bon la dedans:

sol.cpp
-----------------------------------------------------------------------------------------

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
#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;
	int j;
	for(i=0;i<9;i++)
	{
 
 
 
		for(j=0;j<9;j++)
		{
 
 
			if(grille[i][j]==0)
			{
				pos.lig=i;
				pos.col=j;
				f=candidat(pos,grille);
 
				while(f.empty() && !es.empty())
				{
 
					i=(es.top()).lig;
 					j=(es.top()).col;;
					grille[i][j]=0;
					f.pop();
 					fi.lig=i;
					fi.lig=j;
					fi.fl=f;
 
				}
 
				if(!f.empty())
				{
 
 
					grille[i][j]=f.front();
 
					f.pop();
					fi.lig=i;
					fi.col=j;
					fi.fl=f;
					es.push(fi);
 
				}
 
 
 
 
			}
 
		}
 
 
	}
 
 
}

candidat.cpp
--------------------------------------------------------------

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/*Nom du fichier: candidat.cpp --Renvoi la file de candidats pour la case de position pos dans la grille de sudoku*/
#include <iostream>
#include <queue>
 
using std::queue;
 
struct position
{
	int lig;
	int col;
};    
 
bool estDansRegion(position & pos,const int val,const int grille[9][9]);
bool estDansLigne(const int lig,const int val,const int grille[9][9]);
bool estDansColonne(const int col,const int val,const int grille[9][9]);
 
queue <int> candidat(position & pos,const int grille [9][9])
{
 
	queue<int>p; //instanciation
 
	int i=1;
	bool edl;
	bool edc;
	bool edr;
 
	while(i<=9)
	{
		edl=estDansLigne(pos.lig,i,grille);
		edc=estDansColonne(pos.col,i,grille);
		edr=estDansRegion(pos,i,grille);
 
		if(!edl && !edc && !edr)//si la valeur i n'est ni dans la ligne,ni dans la colonne,ni dans la region,on rajoute l'entier dans la file.
		{
			p.push(i);
		}
	i++;
	}
 
return p;
}

Je mets par hasard aussi region.cpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/*Nom du fichier: region.cpp -- Renvoi vrai si le symbole val est dans la region de la case de position pos dans la grille de sudoku */
#include <iostream>
#include <cassert>
 
struct position
{
	int lig;
	int col;
};      
 
bool estDansRegion(position & pos,const int val,const int grille[9][9])
{
	assert(pos.lig>=0 && pos.lig<=9);
	assert(pos.col>=0 && pos.col<=9);
	bool b=false;
	int j=(pos.lig/3)*3;
	int i=(pos.col/3)*3;
 
	for(int k=0;k<3 && !b;k++)
	{
 
		for(int l=0;l<3 && !b;l++)
		{
 
			b=(grille[j][i]==val);
 
		i++;	
		}
	j++;	
	}
 
return b;
 
}

je vous remercie de m'indiquer le ou les erreurs...

merci

[/code]

**Arnaud F.** · 27/12/2005, 15h13

Pourquoi tu demande de l'aide si t'en tiens pas compte...

Je crois vraiment que t'es aveugle, je t'ai posté la solution , y a une faute dans ton prog et je l'ai corrigé dans mon ancien post, j'ai vu que tu n'y a pas remedier dans ton code ... relis le

Lees boucles FOR marche tres bien!!! et puis, je te signal au passage que dans ta structures essais, ce n'est pas
struct essai
{
int lig;
int col;
queue fi;
};[/code]

Mais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
struct essai
{
    position pos;
   queue fi;
};

En esperant que tu relira mes posts, je te salue

**Alain15** · 27/12/2005, 15h42

ben voila pour la structure, je trouve mieux de faire comme ca... autrement j'aime pas trop et ca me fait des segmentations fault...

bon je v juste changer l'erreur que j'ai fait, signaler plus haut...

**Alain15** · 27/12/2005, 16h31

j'ai un peu changé et modifié qquelque chose, mais bon y a pas de résultat, je suis obligé d'arreter le processus

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
#include <iostream>
#include <queue>
#include <stack>
 
using std::stack;
using std::queue;
 
struct position
{
	int lig;
	int col;
};      
 
 
struct essai
{
	position pos;
	queue<int>fl;
};
 
queue <int> candidat(essai fi,const int grille [9][9]);
 
void solution(essai fi,int grille[9][9])
{
stack<essai>es;
 
 
	for(int i=0;i<9;i++)
	{
 
 
 
		for(int j=0;j<9;j++)
		{
 
 
			if(grille[i][j]==0)
			{
				fi.pos.lig=i;
				fi.pos.col=j;
				fi.fl=candidat(fi,grille);
 
				while(fi.fl.empty() && !es.empty())
				{
 
					i=((es.top()).pos).lig;
 					j=((es.top()).pos).col;;
					grille[i][j]=0;
					es.top();
 
				}
 
				if(!fi.fl.empty())
				{
 
 
					grille[i][j]=fi.fl.front();
 
					fi.fl.pop();
					es.push(fi);
 
				}
 
 
 
 
			}
 
		}
 
 
	}
 
 
}

merci[/code]

**Alain15** · 27/12/2005, 19h40

la méthode que je dois utilisé pr ce sudoku est vraiment nulle, y a en a des plus simples...

ca m'enerve y a tj des erreurs arg...

**Arnaud F.** · 27/12/2005, 21h57

je sais que la methode est nulle, mais bon, c'est comme sa, et puis tu vois t'a réussi a compiler avec les boucles for, par contre je comprend pas pourquoi tu met en entrée une variable de type essai,

et puis pour ta fonction candidat aussi ... je vois pas ce que sa fait la...

Tu peux juste me montrer ta fonction candidat??? parce que moi j'ai en entrée une variable de type position et la grille, rien d'autre, ton bug peux venir du fait que tu recherche mal tes candidats et puis place des "cout" aussi histoire de faire des tests et de voir ou sa bug

j'ai regardé ta fonction candidat de l'un de tes derneirs post, elle est vraiment bizzare en fait, moi la mienne c'est celle la et elle fonctionne tres bien

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue<int> candidats(const position& pos, const int grille[9][9])
{
	queue<int> f;
	bool b,c,d;
	for(int i=1; i<10; i++)
	{
		b=estDansLigne(pos,i,grille);
		c=estDansColonne(pos,i,grille);
		d=estDansRegion(pos,i,grille);
		if(!b && !c && !d)
		{
			f.push(i);
		}
	}
	return f;
}

**Alain15** · 28/12/2005, 11h06

nan ma fonction candidat est pas bizarre, mais tu vois par exemple pour est dans ligne, je donne a la fonction que le numéro de la ligne, ca sert a rien de renvoyer la structure complete, c'est pour ca que tu vois pos.lig par exemple...

Sache aussi que je fais tout en compilation séparé.

Je mets une entrée de variable de type essai car c la dedans que se trouve la position pos.

La fonction candidat est la car c de la compilation séparé,il faut déclaré tout les fichiers qu'on utilise dans la fonction.

bon j'ai essayé 53000 trucs différents, le résultat ou bien ca fini pas, un segmentation fault ou que la premiere ligne...

tu pourrais juste me montrer ta estdansregion car j'ai un doute la dessus, ca se peut que c ca qui fait bugger...

cordialement Alain

**Alain15** · 28/12/2005, 19h36

y a t'il des pros de la programmation?

**reggae** · 28/12/2005, 19h55

Il doit y en avoir pas mal dans les parages...

**Arnaud F.** · 28/12/2005, 20h01

sur le sujet, regarde les entrées de la fonction candidat, tu verra les entrées qu'il faut y mettre, et puis je suis pas comme sa, je te montre ma candidat et ma estDansRegion, sache qu'elle fonctionne sans probleme

Ma résolution de sudoku fonctionne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool estDansRegion(const position& pos, const int val, const int grille[9][9])
{
	int res;
	bool b=false;
	int baseCol=pos.col-(pos.col%3);
	int baseLig=pos.lig-(pos.lig%3);
	for (int i=baseLig;i<(baseLig+3);i++)
	{
		for(int j=baseCol;j<(baseCol+3);j++)
		{
			if(grille[i][j]==val)
			{
				b=true;
			}
		}
    }
    return b;
}

voila pour la région et pour lacandidat, j'ai sa:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue<int> candidats(const position& pos, const int grille[9][9])
{
	queue<int> f;
	bool b,c,d;
	for(int i=1; i<10; i++)
	{
		b=estDansLigne(pos,i,grille);
		c=estDansColonne(pos,i,grille);
		d=estDansRegion(pos,i,grille);
		if(!b && !c && !d)
		{
			f.push(i);
		}
	}
	return f;
}

Résolution Sudoku, demande aide...

C++

Discussions similaires

Partager

Partager