Discussion :

[SettingUp]

Bonsoir, j'ai pour projet de programmer un résolveur de Sudoku en utilisant la notion de Pile en java.

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
package sudokuBis;
 
public class ResolSudoku {
 
	private Pile valeur= new Pile(1000000);// je ne suis pas bien sur de savoir qu'elle valeur affecter à la pile
	private Pile pos_i= new Pile(1000000);
	private Pile pos_j=new Pile(1000000);
	private int x=1;
	private int erreur=0; 
	private int i=0;
	private int j=0;
 
 
 
// 	
//
//	
 
	public ResolSudoku(int sudoku[][]) // 
	{	
		while(true) 
		{	
			if(erreur==0)
			{//On parcourt les cases du sudoku jusqu'à tomber sur une case vide (==0)
				i=0;
				j=0;
				while(i<9)
				{
					while(j<9)
					{
						if(sudoku[i][j]==0) 
						{
							break;
						}
						j++;
					}
                                        //On vérifie si on est sortit de la boucle car on a trouvé une case vide ou parce qu'on en a trouvé aucune
					if(j==9)
					{
						j=0;
						i++;
					}
					else 
					{
						break;
					}
 
				}
                               // on est à une case vide du sudoku (==0) OU on finit la boucle sans avoir trouvé de cases vides (donc sudoku complété)
 
				if(i==9)
				{
					break;
				}
 
				else 
				{
					valide(sudoku,i,j,x);//fonction permettant d'affecter une valeur à une case vide du sudoku (détaillée plus bas)
					i=0;
					j=0;
					x=1;
 
				}
			}	
 
			if(erreur==1)// on est à un moment ou aucune valeur testée n'a fonctionnée sur la case utilisée
			{
				x=valeur.pop();// on retourne à x la valeur précédente retenue dans la pile 
				x=x+1//on augmente cette valeur de 1 (de manière à ce que la recherche du bon x se fasse à partir de cette nouvelle valeur)
                                i=pos_i.pop();// de même pour i et j pour se placer à la bonne case
				j=pos_j.pop();	
				valide(sudoku,i,j,x);// on relance la méthode "valide" avec ces paramètres, on est donc placé à l'ancienne case du sudoku avec son ancien x et on essaie à partir de cet x de trouver une nouvelle "bonne" valeur
 
			}
		}	
		//On arrive ici quand on sort du while(true) donc quand toutes les cases sont remplies on affiche alors le sudoku
		for(int m=0;m<9;m++)
		{
			for(int n=0;n<9;n++)
			{
				System.out.print(sudoku[m][n]);
			}
			System.out.println();
		}	
 
	}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
	private void valide(int sudoku[][], int i, int j, int x)
	{
		while(x<=9)// on cherche pour x de 1 à 9 inclus une valeur qui n'est pas présente dans la ligne, dans la colonne ou dans le bloc de la case où on se trouve
		{
			if(verifLigne(sudoku,i,x) && verifCol(sudoku,j,x) && verifBloc(sudoku,i,j,x))// La valeur semble être correcte
			{
				sudoku[i][j]=x;// on implémente cette valeur à la case de notre sudoku				
				break;
			}
			x++;
		}	
 
		//sort de la boucle soit parce que on a trouvé une valeur possible OU aucune valeur n'a été trouvée. DONC ON VERIFIE DANS QUEL CAS ON SE TROUVE	
			if(x==10)// on a trouvé aucune valeur possible on réinitialise la valeur de la case à 0 et on met "erreur" à 1.
			{	
				x=0; 	
				sudoku[i][j]=0;
				erreur=1;
			}
			else//tout est bon on repart dans la boucle de départ avec erreur=0
			{
				pos_i.push(i);// on implémente la valeur de i en haut de cette pile
				pos_j.push(j);// on implémente la valeur de j en haut de cette pile
				valeur.push(x);// on implémente la valeur trouvée en haut de cette pile
				erreur=0;
			}
	}
 
//////////////////////////////////////////////////////
///////////// ::::::::::::::::::::::::////////////////détail des fonctions permettant de vérifier si le chiffre choisi n'est bien pas sur une ligne, sur une colonne ou sur un bloc
//////////////////////////////////////////////////////
 
	private boolean verifLigne(int sudoku[][], int i,int x)
	{
		int j=0;
		while(j<9)
		{
			if(sudoku[i][j]==x)
			{
				return false;
			}
			j++;
		}
		return true;
	}
 
 
	private boolean verifCol(int sudoku[][], int j,int x)
	{
		int i=0;
		while(i<9)
		{
			if(sudoku[i][j]==x)
			{
				return false;
			}
			i++;
		}
		return true;
	}
 
 
	private	boolean verifBloc(int sudoku[][], int i,int j, int x)
	{
		int ligb=i-(i%3); 
		int colb=j-(j%3);	
		i=ligb;
		j=colb;
 
		while(i<ligb+3)
		{
			j=colb;
			while(j<colb+3)
			{
				if(sudoku[i][j]==x)
				{
					return false;
				}
				j++;
			}
			i++;			
		}
		return true;		
	}		
}

Voilà le code, j'ai donc testé en entrant plusieurs grilles de sudoku. ça à fonctionné sur certaines mais pas sur d'autres. De ce que je comprends (après plusieurs test où je printf les valeurs de x et de la pile correspondant à divers endroits) le problème survient lorsque le programme remonte jusqu'à la première case et la première valeur puis teste toutes les valeurs et aucune ne fonctionne, il essaie donc de dépiler à partir de la .. ce qui est impossible puisque la liste est vide arrivé à ce moment là..
Je rajoute aussi le code de la pile

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
package sudokuBis;
 
public class Pile {
 
	private int Taille; 
	private int[] listePile; 
	private int top;
 
 
	public Pile(int x) 
		{
		Taille = x;    
		listePile = new int[Taille]; 
		this.top = 0;
	    }
 
	   public void push(int j) // à la position suivante de la piste on place la valeur j
	   		{ 
		   	  listePile[++top] = j;
	   		}
 
	   public int pop() // on se place à la position précédente de la liste 
	   		{ 							
		      return listePile[top--];
	   		}
 
 
	   public int valeurTop() //on retourne la valeur de la position la plus haute de la pile 
	   		{
		      return listePile[top];
	   		}
}

Voilà, j'espère être suffisamment clair, Merci d'avance de votre aide !

[joel.drigo]

Salut,

Une ArrayIndexOutOfBoundException arrive quand on cherche à accéder à un index inexistant dans un tableau. Déjà regarder sur quelle ligne ça se passe, pour savoir de quel tableau il s'agit. Le message contient également l'index accédé, celui en dehors des bornes justement.

Il y un problème dans ta pile. Si on fait un pop alors que la pile est vide, on obtient quand même une valeur, fausse forcément, puisqu'on devrait avoir une exception. Le fait de faire ++top fait qu'on crame un élément (l'index 0). Tu pourrais faire démarrer top à -1 par exemple.
Dimensionner la pile à 1000000 va consommer de la mémoire en correspondance. Avec un tableau, on est obligé de le dimensionner pour pouvoir l'utiliser. Si tu ne peux pas utiliser autre chose qu'un tableau (par exemple une ArrayDeque te permettrait de gérer une pile), l'autre solution serait de faire un petit tableau, et d'en créer un plus grand au besoin (créer un nouveau tableau plus grand, copier le tableau courant dedans, remplacer le tableau courant par le nouveau), ce que fait justement une ArrayDeque en interne.

[SettingUp]

Alors j'ai modifié la valeur de top pour le faire démarrer à -1 comme tu me l'a conseillé.
J'ai aussi modifié quelques noms de variables et d'attributs de classe pour rendre le tout plus lisible et ai commenté la ligne où l'erreur survient, voilà 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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
package sudokuBis;
 
public class ResolSudoku {
 
	private Pile valeurPile= new Pile(1000000);// je ne suis pas bien sur de savoir qu\'elle valeur affecter à la pile
	private Pile pos_i= new Pile(1000000);
	private Pile pos_j=new Pile(1000000);
	private int valeurSud=1;
	private boolean erreur=false; //sert à savoir si on est tombé sur une erreur (besoin de dépiler) ou si on peut simplement continuer à avancer dans la grille de sudoku
	private int ligneSud=0;
	private int colonSud=0;
 
 
 
 
	public ResolSudoku(int sudoku[][]) 
	{	
		while(true) 
		{	
			if(erreur==false)
			{//On parcourt les cases du sudoku jusqu'à tomber sur une case vide (==0)
				ligneSud=0;
				colonSud=0;
				while(ligneSud<9)
				{
					while(colonSud<9)
					{
						if(sudoku[ligneSud][colonSud]==0) 
						{
							break;
						}
						colonSud++;
					}
			//On vérifie si on est sortit de la boucle car on a trouvé une case vide ou parce qu'on en a trouvé aucune
					if(colonSud==9)
					{
						colonSud=0;
						ligneSud++;
					}
					else 
					{
						break;
					}
 
				}
			//on est à une case vide du sudoku (=0) OU on finit la boucle sans avoir trouvé de cases vides (donc sudoku complété)
 
				if(ligneSud==9)
				{
					break;
				}
 
				else 
				{
					valide(sudoku,ligneSud,colonSud,valeurSud);//fonction permettant d'affecter une valeur à une case vide du sudoku (détaillée plus bas)
 
			//On réinitialise la case pour effectuer une nouvelle recherche de case vide et on réinitilise la valeur trouvée
					ligneSud=0;
					colonSud=0;
					valeurSud=1;
 
				}
			}	
 
			if(erreur==true)// on est à un moment ou aucune valeur testée n'a fonctionnée sur la case utilisée
			{
 
/*PROBLEME, c'est sur cette ligne que survient le problème ->*/		valeurSud=valeurPile.pop();// on retourne à "valeurSud" la valeur précédente retenue dans la pile 
				ligneSud=pos_i.pop();
				colonSud=pos_j.pop();
				valeurSud=valeurSud+1;//on augmente cette valeur de 1 (de manière à ce que la recherche du bon x se fasse à partir de cette nouvelle valeur)
				sudoku[ligneSud][colonSud]=0;// on réinitialise la où on se trouve à 0
				valide(sudoku,ligneSud,colonSud,valeurSud);// on relance la méthode "valide" avec ces paramètres, on est donc placé à l\'ancienne case du sudoku avec son ancienne valeur et on essaie à partir de cette valeur d'en trouver une nouvelle "bonne" 
 
			}
		}	
			//On arrive ici quand on sort du while(true) donc quand toutes les cases sont remplies on affiche alors le sudoku
		for(int m=0;m<9;m++)
		{
			for(int n=0;n<9;n++)
			{
				System.out.print(sudoku[m][n]);
			}
			System.out.println();
		}	
 
	}
 
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
	private void valide(int sudoku[][], int lig, int col, int valeur)
	{
		while(valeur<=9)// on cherche pour valeur de 1 à 9 inclus une valeur qui n\'est pas présente dans la ligne, dans la colonne ou dans le bloc de la case où on se trouve
 
		{
			if(verifLigne(sudoku,lig,valeur) && verifCol(sudoku,col,valeur) && verifBloc(sudoku,lig,col,valeur))// La valeur semble être correcte
			{
				sudoku[lig][col]=valeur;//on ajoute cette valeur à la case de notre sudoku				
				break;
			}
			valeur++;
		}	
 
		//sort de la boucle soit parce que on a trouvé une valeur possible OU aucune valeur n'a été trouvée. DONC ON VERIFIE DANS QUEL CAS ON SE TROUVE	
			if(valeur==10)// on a trouvé aucune valeur possible
			{	 	
				sudoku[lig][col]=0;
				erreur=true;
			}
			else//on a trouvé une valeur possible
			{
				pos_i.push(lig);// on ajoute la valeur de la ligne en haut de cette pile
				pos_j.push(col);// on ajoute la valeur de la colonne en haut de cette pile
				valeurPile.push(valeur);// on ajoute la valeur trouvée en haut de cette pile
				erreur=false;
			}
	}
 
//////////////////////////////////////////////////////
///////////// ::::::::::::::::::::::::////////////////détail des fonctions permettant de vérifier si le chiffre choisi n\'est bien pas sur une ligne, sur une colonne ou sur un bloc
//////////////////////////////////////////////////////
 
//parcours la ligne et renvoie false si la valeur qu'on vérifie est déjà sur la ligne, sinon renvoie true (incrémente colonne mais change pas de ligne)
	private boolean verifLigne(int sudoku[][], int lig,int valeur)
	{
		int j=0;
		while(j<9)
		{
			if(sudoku[lig][j]==valeur)
			{
				return false;
			}
			j++;
		}
		return true;
	}
 
//parcours la colonne et renvoie false si la valeur qu'on vérifie est déjà sur la colonne, sinon renvoie true (incrémente ligne mais change pas de colonne)
	private boolean verifCol(int sudoku[][], int col,int valeur)
	{
		int i=0;
		while(i<9)
		{
			if(sudoku[i][col]==valeur)
			{
				return false;
			}
			i++;
		}
		return true;
	}
 
 
//parcours le bloc et renvoie false si la valeur qu'on vérifie est déjà sur le bloc, sinon renvoie true
	private	boolean verifBloc(int sudoku[][], int lig,int col, int valeur)
	{
		int ligb=lig-(lig%3); 
		int colb=col-(col%3);	
		lig=ligb;
		col=colb;
 
		while(lig<ligb+3)
		{
			col=colb;
			while(col<colb+3)
			{
				if(sudoku[lig][col]==valeur)
				{
					return false;
				}
				col++;
			}
			lig++;			
		}
		return true;		
	}		
}

Cependant, j'ai toujours le même problème lorsque la pile arrive à la première case remplie, la première valeur, ne trouve aucune valeur possible et cherche donc encore à dépiler (impossible) .
Merci de ton aide !

[joel.drigo]

Est-ce que tu n’essaierais pas ton programme avec des grilles de taille différente de 9×9 (donc un tableau de 10×10 dans ton cas) ?

Comme dans ton code tu gères la taille de grille en dur, forcément ça ne peut pas fonctionner pour des grilles de taille différente. Il vaut mieux parcourir des tableaux en bornant sur leur taille (tab.length). Pensez que dans un tableau, les index vont de 0 à taille-1. Dans ton code, avec un tableau 10×10, on a une ligne et une colonne remplie de 0 en bordure droite et en bas (que tu n'affiche pas, puisque ta boucle d'affichage borne sur <9).

Attention aussi à ce genre de code :

Code :

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

1
2
3
4
5
6
while(lig<ligb+3)
		{
			col=colb;
			while(col<colb+3)
			{
				if(sudoku[lig][col]==valeur)

On peut facilement déborder du tableau.

C'est difficile pour moi de te dire où ça ne va pas, parce que je ne sais pas comment tu testes. Avec quelle grille.

[joel.drigo]

J'ai essayé avec une grille aléatoire :

Code :

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

1
2
3
4
5
6
7
8
9
		int[][] grid = new int[10][10];
 
		ResolSudoku sudoku = new ResolSudoku(grid);
 
		for(int i=0; i<9*9 && i<100; i++) {
			grid[ThreadLocalRandom.current().nextInt(0, 10)][ThreadLocalRandom.current().nextInt(0, 10)]=0;
		}
 
		ResolSudoku sudoku2 = new ResolSudoku(grid);

Il semble en effet que certaines grilles provoquent l'erreur.

On voit déjà qu'il y a un problème si error est true dès le début : la pile n'est pas remplie, donc vide, et donc pop fait forcément une erreur. Ce qui n'est pas logique c'est qu'on push seulement si erreur est false, alors qu'avec erreur=true, le seul moyen que la pile ne soit pas vide, c'est qu'on n'ait pas eu d'erreur avant, ou qu'on ait pas tout dépiler entre temps (on peut voir qu'on passe plusieurs fois dans le traitement d'erreur, et donc on dépile).

Tu peux me donner l'algorithme que tu implémentes ?

[joel.drigo]

En essayant avec une grille qui plante :

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
		grid = new int[10][10];
		String init=
		"103006000"+
		"457819023"+
		"089230045"+
		"200000957"+
		"360790210"+
		"790104368"+
		"036941800"+
		"842673501"+
		"901582436";
		for(int j=0; j<9; j++) {
		for(int i=0; i<9 ; i++) {
			grid[j][i]=init.charAt(j*9+i)-'0';
		}

Et en traçant les accès pile :

push [0][1]=2
push [0][3]=4
push [0][4]=5
push [0][6]=7
push [0][7]=8
push [0][8]=9
push [1][6]=6
push [2][0]=6
push [2][5]=7
push [2][6]=1
push [3][1]=1
push [3][2]=4
push [3][3]=3
push [3][4]=6
push [3][5]=8
push [4][2]=5
pop [4][2]=5
push [4][2]=8
pop [4][2]=8
pop [3][5]=8
pop [3][4]=6
pop [3][3]=3
pop [3][2]=4
push [3][2]=8
pop [3][2]=8
pop [3][1]=1
pop [2][6]=1
pop [2][5]=7
pop [2][0]=6
pop [1][6]=6
pop [0][8]=9
pop [0][7]=8
push [0][7]=9
pop [0][7]=9
pop [0][6]=7
pop [0][4]=5
pop [0][3]=4
pop [0][1]=2
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at sudokuBis.Pile.pop(Pile.java:24)
at sudokuBis.ResolSudoku.<init>(ResolSudoku.java:85)
at sudokuBis.Main.main(Main.java:54)

on peut comprendre le problème et plus ou moins l'algorithme.

Globalement, on essaye successivement les valeurs de 1 à 9 pour la première case trouvée à 0. Si on trouve une configuration qui fonctionne, on recommence. Si on ne trouve pas (erreur=true), on essaye donc la valeur suivante. Sauf que si aucune configuration n'est trouvable sur cette première case à 0, on continue d'essayer de trouver alors que la pile est vide, puisque toutes les configurations possibles ont été testées, donc "popées".

La solution est déjà de pouvoir tester si la pile est vide. Lorsqu'elle est vide, c'est qu'aucune configuration ne peut être trouvée en partant de cette case, il faut donc passer à la case suivante à 0 et recommencer. Si à la fin, on n'arrive pas à trouver de configuration, alors la grille est insoluble.

Dans pile :

Code :

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

1
2
3
public boolean isEmpty(){
		   return top==-1;
}

Ne réinitialise pas ligneSud et colonSud si erreur=false, mais avant de boucler, s'il n'y a pas eu d'erreur. En cas d'erreur, si la pile est vide, passe à une case suivante, en repassant valeurSud=1 (si on sort de la grille, alors on a tout essayé, et donc la grille est insoluble).

[SettingUp]

Je gère la taille de la grille en dur, puisque la finalité de mon projet consiste à afficher un sudoku (interface graphique) "classique" (c 'est à dire 9 blocs de 3*3 cases). Donc puisque je récupère la grille de sudoku entrée par l'utilisateur dans l'interface graphique, à aucun moment je suis sensé avoir une grille différente de la taille (9*9).
Pour l'instant je n'ai pas tout à fait terminé mon interface graphique donc j'effectue simplement mon test avec le code suivant:

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
package sudokuBis;
 
 
 
public class mainsudoku {
 
	public static void main(String[] args) {
 
		//Grille_sudoku oui = new Grille_sudoku(); Mon interface graphique
 
		//grille de sudoku de Test
		int sudokutest[][] = {{3,5,0, 0,0,0, 0,8,1},
							  {0,0,0, 0,4,6, 0,0,3},
							  {4,0,0, 8,0,0, 0,9,0},
 
							  {5,0,0, 0,0,0, 8,0,0},
							  {0,1,0, 0,6,0, 0,3,0},
							  {0,0,9, 0,0,0, 0,0,5},
 
							  {0,9,0, 0,0,3, 0,0,8},
							  {7,0,0, 9,2,0, 0,0,0},
							  {1,8,0, 0,0,0, 0,7,2}};
 
		//j'affiche ma grille de sudoku de test
		for(int i=0;i<9;i++)
		{
			for(int j=0;j<9;j++)
			{
				System.out.print(sudokutest[i][j]);
			}
			System.out.println();
		}
 
		//J'appelle la méthode ResolSudoku
		ResolSudoku a = new ResolSudoku(sudokutest);
 
	}
}

Je ne comprends pas vraiment comment erreur pourrait être à true dès le début (à moins que la grille de sudoku donnée soit fausse mais je gererai les exceptions plus tard) puisque dans la première case où on va il y a forcement une valeur possible.
Je ne suis pas sur de comprendre ce que tu souhaites quand tu me demande l'algorithme que j'implémente, désolé