Solveur de Sudoku en Java

Version imprimable

Bonjour a tous,
D'abord je voudrais m'excuser pour l'absence d'accents dans mon message, mais j'ai un probleme avec mon clavier en ce moment...

Je suis en train de programmer un solveur de grilles Sudoku. Il propose a l'utilisateur de remplir les elements de la grille a resoudre puis de la soumettre a la recherche de la solution.
Actuellement, je suis en train de reflechir a l'algorithme de resolution. Un ami specialiste m'a dit ceci:

Citation:

Les cases vides du tableaux contiennent 0 par defaut. Le programme va parcourir le tableau et va essayer dans chaque case, de mettre un chiffre entre 1 et 9. Si 1 ne marche pas, il essaie 2 sur la meme case, ainsi de suite jusqu'a 9.

S'il arrive a mettre un chiffre dans la case, il passe a la suivante, jusqu'a arriver a la derniere.

S'il n'arrive a mettre aucun chiffre dans la case, il ajoute 1 au contenu de la case precedente, 2 si la valeur obtenue dans la case precedente ne marche pas, ainsi de suite jusqu'a ce que l'addition atteigne 9. S'il arrive a modifier le chiffre dans la case precedente, il essaie de nouveau d'en caser un dans la case sur laquelle il est, sinon il cherche a modifier le chiffre de 2 cases en arriere, ainsi de suite jusqu'a atteindre la premiere case. Ce jusqu'a ce qu'il arrive a trouver une valeur acceptable dans une case, a ce moment-la, il "repart en avant".

S'il n'arrive pas (plus) a mettre de chiffre dans la premiere case, le programme s'arrete en disant qu'il n'y a pas de solution.

J'ai donc traduit ses dires en ceci:
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 public static void resolution (int x, int y, int n, int[][] matrice) { for (int i=n; n<10; i++) { if ((!doublon_ligne(x,n,0,9, matrice))&&(!doublon_colonne(y,n,0,9, matrice))&&(!doublon_carre(x,y,n,matrice))) { matrice[x][y]=n; } } } public static void resolution_totale (int[][] matrice) { for (int x=0; x<9; x++) { for (int y=0; y<9; y++) { resolution(x,y,1,matrice); if (matrice[x][y]==0) { if (x>0) { resolution(x-1,y,matrice[x-1][y]+1,matrice); while (!((x!=9)&&(y!=9)&&(matrice[x][y]!=0))) { resolution_totale(matrice); } } else { if (y>0) { resolution(8,y-1,matrice[8][y-1]+1,matrice); while (!((x!=9)&&(y!=9)&&(matrice[x][y]!=0))) { resolution_totale(matrice); } } else { System.out.println("Pas de solution"); } } } } } }
Ici, les fonctions doublon_xxx servent a reperer si oui ou non il y a un doublon dans la colonne, la ligne ou la region (en Sudoku les carres 3x3 du tableau, dans lesquels il ne peut pas y avoir 2 fois le meme chiffre). Je suis sur et certain que ces fonctions remplissent correctement leur role, l'erreur etant dans la partie publiee.

resolution sert a resoudre le contenu d'une seule case et resolution_totale, le tableau entier.

J'ai deja modifie pas mal de fois mon code, mais je n'arrive plus a trouver mon erreur.
Je m'en remets donc a vous chers specialistes du forum, afin de savoir si j'ai traduit correctement le francais ci-dessus en algo, et si d'ailleurs, ce principe est juste pour la resolution d'une grille de Sudoku.

Quand je fais tourner cet algo: Le PC mouline et rien ne s'affiche.
Mais je pense savoir que c'est parce que je lui demande de recommencer a resoudre le tableau depuis le debut a chaque fois qu'il modifie une valeur, ce qui est tres long.
Vrai?

Merci d'avance pour votre aide.

04/06/2009, 09h11
Patriarch24

Pour trouver un algorithme efficace, je te conseille google, qui donne des solutions d'algorithmes pour résoudre un sudoku valide (c'est-à-dire à solution unique) en moins d'une seconde.
Pour plus d'infos : http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku
04/06/2009, 15h49
dinobogan
Dommage : tu as commencé à faire du récursif, sans aller jusqu'au bout :roll:
Ta fonction récursive devrait avoir des paramètres en plus : position de la case actuellement à modifier.
Il faudrait une méthode qui renvoie un booléen pour savoir si oui ou non le chiffre ajouter est potentiellement bon ou pas du tout bon.
Ton algorithme est simplifiable. Les deux boucles "for" de parcours sont à supprimer et remplacer dans ta méthode récursive par :
Code:

1 2 3 4 5 6 7 8 9 10 11 ++x; if( x >= 9 ) { x = 0; ++y; } if( y >= 9 ) { //la solution est trouvée }
04/06/2009, 16h28
wax78

Tu peux, aussi, si tu est motivé, utiliser un système de programmation par contrainte style Choco.

Dont voici un exemple avec la resolution du sudoku http://www.emn.fr/x-info/choco-solve..._a_sudoku_grid

Merci à tous pour votre réponse, désolé pour le retard.
J'ai regardé vos codes sur les liens et j'arrive à les interpreter, mais notre enseignant refuse qu'on copie/reformule des codes trouvés sur Internet. Je suis donc obligé de poursuivre le mien, vu que bien qu'il soit un peu lourd, il est trop tard pour tout recommencer, je dois rendre le projet dans 3 jours!

Voici 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
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 public static boolean doublon_ligne (int x, int n, int s, int z, int[][] matrice)
  {
    int pip=(-1);
    boolean answer = false;
 
    for (int i=s; i<z; i++)
      {
	if (matrice[x][i]==n)
	  {
	    pip = i;
	  }
      }
 
    if (pip != (-1))
      {
	answer = true;
      }
 
    return(answer);
  }
 
  public static boolean doublon_colonne (int y, int n, int s, int z, int[][] matrice)
  {
    int pip=(-1);
    boolean answer = false;
 
    for (int i=s; i<z; i++)
      {
	if (matrice[i][y]==n)
	  {
	    pip = i;
	  }
      }
    if (pip != (-1))
      {
	answer = true;
      }
 
    return(answer);
  }
 
 
 
  public static void display_grid (int [][] matrice)
  {
    for (int i=0; i<matrice.length; i++)
      {
	for (int j=0; j<matrice.length; j++)
	  {
	    System.out.print(matrice[i][j]+" ");
	  }
	System.out.println("");
      }
  }
 
  public static int premiere_case (int x)
  {
    if (x<3)
      {
	return(0);
      }
    else
      {
	if (x<6)
	  {
	    return(3);
	  }
	else
	  {
	    return(6);
	  }
      }
  }
 
  public static boolean doublon_carre (int x, int y, int n, int[][] matrice)
  {
    int fin_x = x+2;
    int fin_y = y+2;
 
    if (doublon_ligne(premiere_case(x),n,premiere_case(x),premiere_case(x)+3,matrice)||(doublon_colonne(premiere_case(y),n,premiere_case(y),
													premiere_case(y)+3,matrice)))
	{
	  return(true);
	}
    else
      {
	if (doublon_ligne(premiere_case(x)+1,n,premiere_case(x)+1,premiere_case(x)+3,matrice)||(doublon_colonne(premiere_case(y)+1,n,premiere_case(y)+1,
														premiere_case(y)+3,matrice)))
	  {
	    return(true);
	  }
	else
	  {
	    if (matrice[premiere_case(x)+2][premiere_case(y)+2]==n)
	      {
		return(true);
	      }
	    else
	      {
		return(false);
	      }
	  }
      }
  }
 
  public static int bk_x (int x)
  {
    if (x>0)
      {
	return(x-1);
      }
    else
      {
	return(8);
      }
  }
 
  public static int bk_y (int x, int y)
  {
    if (x>0)
      {
	return(y);
      }
    else
      {
	return(y-1);
      }	 
  }
 
 
  public static void remplace_avant(int x, int y, int[][] matrice)
  {
    if (matrice[x][y]!=9)
      {
	matrice[x][y]=matrice[x][y]+1;
      }
    else
      {
	if ((x!=0)||(y!=0))
	  {
	    remplace_avant(bk_x(x),bk_y(x,y),matrice);
	  }
      }
  }
 
  public static int next_x (int x)
  {
    if (x<8)
      {
	return(x+1);
      }
    else
      {
	return(8);
      }
  }
 
  public static int next_y (int y, int x)
  {
    if (y<8)
      {
	return(y+1);
      }
    else
      {
	return(0);
      }
  }
 
  public static void resolution (int x, int y, int[][] matrice)
  { 
    int i=1;
    while ((matrice[x][y]==0)&&(i<10))
      {
	for (; i<10; i++)
	  {
	    if ((!doublon_ligne(x,i,0,9, matrice))&&(!doublon_colonne(y,i,0,9, matrice))&&
		(!doublon_carre(x,y,i,matrice)))
	      {
		matrice[x][y]=i;
	      }
	  }
      }
    if (matrice[x][y]==0)
      {
	if ((x==0)&&(y==0))
	  {
	    System.out.println("Pas de solution");
	  }
	else
	  {
	    remplace_avant(x,y,matrice);
	    resolution(x,y,matrice);
	  }
      }
    else
      {
	if ((x!=8)||(y!=8))
	  {
	    resolution(next_x(x),next_y(y,x),matrice);
	  }
      }
 
  if (matrice[x][y]==0)
    {
      if ((x!=0)||(y!=0))
	{
	    remplace_avant(x,y,matrice);
	    resolution(x,y,matrice);
	}
      else
	{
	  System.out.println("Pas de solution");
	}
    }
  }
 
  public static void resolution_totale (int[][] matrice)
  {
    for(int x=0; x<9; x++)
      {
	for (int y=0; y<9; y++)
	  {
	    resolution(x,y,matrice);
	  }
      }
  }

PS: Ce n'est pas le code en entier, il y a au dessus la partie qui permet à l'utilisateur de remplir la grille. Vous n'etes pas obligés de relire tout, juste les dernières procédures/méthodes de résolution.

Je l'ai revérifié et reformulé plusieurs fois mais je ne comprends pas le résultat qu'il me donne pour une grille vide donnée en paramètre:

Code:

1
2
3
4
5
6
7
8
9
10
 
9 6 4 3 7 1 2 1 1 
1 8 5 7 2 3 1 1 1 
1 1 7 4 3 2 1 1 1 
2 1 1 9 6 4 3 7 1 
1 1 1 1 8 5 7 2 3 
1 1 1 1 1 7 4 3 2 
3 7 1 1 1 1 9 6 4 
7 1 3 2 1 1 1 8 5 
4 3 2 1 1 1 1 1 7

Voilà, le seul problème qu'il reste, c'est tout ces 1 dans la grille, alors que le code me parrait pourtant correct (la preuve, c'est que je l'ai effacé et recodé plusieurs fois). Je n'arrive pas à trouver l'erreur.
Je sais que je vous donne beaucoup à lire, mais vous etes vraiment mon dernier espoir. Votre forum m'a déjà sauvé plus d'une fois et je n'ai aucun proche qui s'y comprenne... :)

Ah oui non, y a des doublons dans les carrés aussi.

Je viens de modifier une erreur dans la procédure remplace_avant et de modifier la suite:

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
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
  public static void remplace_avant(int x, int y, int[][] matrice)
  {
    if (matrice[x][y]!=9)
      {
	if ((!doublon_ligne(x,matrice[x][y]+1,0,9, matrice))&&(!doublon_colonne(y,matrice[x][y]+1,0,9, matrice))&&
	    (!doublon_carre(x,y,matrice[x][y]+1,matrice)))
	  {
	    matrice[x][y]=matrice[x][y]+1;
	  }
	else
	  {
	    if ((x!=0)||(y!=0))
	      {
		remplace_avant(bk_x(x),bk_y(x,y),matrice);
	      }
	  }
      }
    else
      {
	if ((x!=0)||(y!=0))
	  {
	    remplace_avant(bk_x(x),bk_y(x,y),matrice);
	  }
      }
  } 
  
  public static int next_x (int x)
  {
    if (x<8)
      {
	return(x+1);
      }
    else
      {
	return(8);
      }
  }
  
  public static int next_y (int y, int x)
  {
    if (y<8)
      {
	return(y+1);
      }
    else
      {
	return(0);
      }
  }
  
  public static void resolution (int x, int y, int[][] matrice)
  { 
    while ((matrice[x][y]==0)&&(i=10))
      {
	for (int i=1; i<10; i++)
	  {
	    if ((!doublon_ligne(x,i,0,9, matrice))&&(!doublon_colonne(y,i,0,9, matrice))&&
		(!doublon_carre(x,y,i,matrice)))
	      {
		matrice[x][y]=i;
	      }
	  }
      }
    if (matrice[x][y]==0)
      {
	if ((x==0)&&(y==0))
	  {
	    System.out.println("Pas de solution");
	  }
	else
	  {
	    remplace_avant(bk_x(x),bk_y(x,y),matrice);
	    resolution(x,y,matrice);
	  } //Stack overflow ici!?
      }
    else
      {
	if ((x!=8)||(y!=8))
	  {
	    resolution(next_x(x),next_y(y,x),matrice);
	  }
      }
  
  if (matrice[x][y]==0)
    {
      if ((x!=0)||(y!=0))
	{
	    remplace_avant(x,y,matrice);
	    resolution(x,y,matrice);
	}
      else
	{
	  System.out.println("Pas de solution");
	}
    }
  }

  public static void resolution_totale (int[][] matrice)
  {
    for(int x=0; x<9; x++)
      {
	for (int y=0; y<9; y++)
	  {
	    resolution(x,y,matrice);
	  }
      }
  }
}

Résultat: Stack overflow, à la ligne colorée en rouge. Et là vraiment je ne trouve plus!

PRESQUE FINI!

C'est bon j'ai fini par m'apercevoir qu'il y a un probleme avec les fonctions bk_x et bk_y.

Voici mon nouveau code de resolution:
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 public static void remplace_avant(int x, int y, int[][] matrice) { if ((!doublon_ligne(x,matrice[x][y]+1,0,9, matrice))&&(!doublon_colonne(y,matrice[x][y]+1,0,9, matrice))&& (!doublon_carre(x,y,matrice[x][y]+1,matrice))&&(matrice[x][y]!=9)) { matrice[x][y]=matrice[x][y]+1; } else { if ((x!=0)||(y!=0)) { if (y>0) { remplace_avant(x,y-1,matrice); } else { remplace_avant(x-1,8,matrice); } } else { System.out.println("Pas de solution!"); System.exit(0); } } } public static void resolution (int x, int y, int[][] matrice) { int i=1; while ((matrice[x][y]==0)&&(i<10)) { { if ((!doublon_ligne(x,i,0,9, matrice))&&(!doublon_colonne(y,i,0,9, matrice))&& (!doublon_carre(x,y,i,matrice))) { matrice[x][y]=i; display_grid(matrice); } i=i+1; } } if (matrice[x][y]==0) { if (y>0) { remplace_avant(x,y-1,matrice); } else { remplace_avant(x-1,8,matrice); } resolution(x,y,matrice); } else { if ((x!=8)||(y!=8)) { if (y<8) { resolution(x,y+1, matrice); } else { resolution(x+1,0, matrice); } } } } public static void resolution_totale (int[][] matrice) { for(int x=0; x<9; x++) { for (int y=0; y<9; y++) { resolution(x,y,matrice); } } } }
Resultat:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 +-----+-----+-----+ |1 2 4|3 5 6|7 9 8| |5 6 7|8 3 9|0 0 0| |0 0 3|0 0 0|0 0 0| +-----+-----+-----+ |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| +-----+-----+-----+ |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 0| |0 0 0|0 0 0|0 0 9| +-----+-----+-----+ Pas de solution!
avec que un 1 dans la premiere case, 3 dans la 3eme, et 9 dans la 9eme, en parametre.

Je pense que j'y suis presque, sauf que le code s'arrete a la case (1,6).
Pas de stack overflow, il s'arrete, c'est tout!

Le principe de mon code est le suivant:

Citation:

Sur la case sur laquelle tu es, essaie de mettre les nombres de 1 a 9 et arrete des que tu as mis un nombre dans la case. A ce moment-la, etudie la case suivante.

Si tu n'arrives pas a mettre un chiffre dans la case, appelle la fonction remplissage_avant.

remplissage_avant: Si le contenu de ma case precedente est different de 9 et que je peux ajouter 1 a son contenu, je le fais. Si je ne peux pas ajouter 1 a son contenu, quelle que soit la raison, j'essaie avec la case d'avant. Ainsi de suite... si je n'arrive pas a modifier la premiere case, je retourne "Pas de solution!" et j'arrete le programme!

Le probleme c'est que meme avec une grille vide passee en parametre, le programme s'arrete au milieu de la grille et me dit "Pas de solution!"!?

Quelqu'un peut me donner un dernier coup de pouce?