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 !