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
|
/**
* Echiquier.java<br />
*
* Version du 04/10/2006<br />
*/
public class Echiquier {
private int[] echiquier;
private int taille;
private int test=0;
private int etape=0;
private int back=0;
private String msg="";
/**
* Constructeur créant un tableau permettant de gérer l'emplacement des dames
* @param n Taille de l'échiquier
*/
public Echiquier(int n) {
echiquier=new int[n];
taille=n;
init();
}
/**
* Méthode permettant d'initialiser l'échiquier avec aucune reine
*/
public void init() {
for(int i=0;i<taille;i++) {
echiquier[i]=-1;
}
}
/**
* Méthode permettant de mettre sur l'échiquier une reine aux coordonnées données en paramètre
* @param ligne Numéro de la ligne ou l'on souhaite mettre la reine
* @param colonne Numéro de la colonne ou l'on souhaite mettre la reine
*/
public void putLady(int ligne,int colonne) {
echiquier[ligne]=colonne;
}
/**
* Méthode permettant de savoir si l'on peut mettre sur l'échiquier une reine aux coordonnées données en paramètre
* @param ligne Numéro de la ligne ou l'on souhaite mettre la reine
* @param colonne Numéro de la colonne ou l'on souhaite mettre la reine
* @return si la dame peut être mise
*/
public boolean canPutLady(int ligne,int colonne) {
return (!isInColumn(colonne) && !isInDiagonal(ligne,colonne));
}
/**
* Méthode permettant de remplir l'échiquier en utilisant le backtracking
* @param ligne Numéro de la ligne ou l'on souhaite mettre la reine
* @param colonne Numéro de la colonne ou l'on souhaite mettre la reine
*/
public void justDoIt(int ligne,int colonne) {
test++;
int tmp_colonne=0;
int tmp_ligne=0;
/* Si on peut mettre la reine aux indices données en paramètre on la met */
if(canPutLady(ligne,colonne)) {
putLady(ligne,colonne);
etape++;
System.out.println("************** ETAPE "+etape+" **************\n************** BACK "+back+" **************");
System.out.println(this);
/* Si ce n'est pas la dernière reine que l'on met on continue */
if(ligne+1<taille) {
justDoIt(ligne+1,0);
}
else {
return;
}
}
else {
/* Si l'indice de la colonne donnée en paramètre est inférieur à la taille-1 de l'échiquier
on peut essayer de voir si la reine peut aller sur la colonne de droite */
if(colonne+1<taille) {
justDoIt(ligne,colonne+1);
}
/*On ne peut pas mettre la reine dans la ligne mis en paramètre avec la configuration de l'échiquier actuel */
else {
/* Si la reine de la ligne du dessus n'est pas sur l'avant dernière colonne on enlève cette reine
et on essaie de la placer sur la première colonne suivant possible */
if((echiquier[ligne-1]+1)<taille) {
tmp_colonne=(echiquier[ligne-1]+1);
echiquier[ligne-1]=-1;
etape++;
back++;
System.out.println("************** ETAPE "+etape+" **************\n************** BACK "+back+" **************");
System.out.println(this);
justDoIt(ligne-1,tmp_colonne);
}
/* Sinon on recule encore d'une ligne */
else {
/* On prend la ligne du dessus et on vérifie que la colonne n'est pas la dernière */
tmp_colonne=echiquier[ligne-1];
tmp_ligne=ligne-1;
echiquier[ligne-1]=-1;
etape++;
back++;
System.out.println("************** ETAPE "+etape+" **************\n************** BACK "+back+" **************");
System.out.println(this);
/* Si ce n'est pas la dernière colonne on essaie de replacer la reine qu'on enlève à partir de la colonne suivante */
if(tmp_colonne+1<=taille) {
justDoIt(tmp_ligne-1,echiquier[tmp_ligne-1]+1);
}
/* Sinon on repart de la première colonne */
else {
justDoIt(ligne-1,0);
}
}
}
}
}
/**
* Méthode permettant de savoir si une rein est déjà poser sur la colonne passé en paramètre
* @param colonne Numéro de la colonne ou l'on souhaite mettre la reine
* @return Si une reine est déjà sur la colonne mis en paramètre
*/
public boolean isInColumn(int colonne) {
for(int i=0;i<taille;i++) {
if(echiquier[i]==colonne) {
return true;
}
}
return false;
}
/**
* Méthode permettant de savoir si une rein est déjà poser sur la diagonal de la case dont les coordonnées sont passé en paramètre
* @param ligne Numéro de la ligne de la case
* @param colonne Numéro de la colonne de la case
* @return Si une reine est déjà sur la diagonale de la case
*/
public boolean isInDiagonal(int ligne,int colonne) {
boolean existe=false;
for(int i=0;i<taille && existe==false;i++) {
if(echiquier[i]!=-1) {
int diff_ligne=ligne-i;
int diff_colonne=colonne-echiquier[i];
if(Math.abs(diff_ligne)==Math.abs(diff_colonne))
existe=true;
}
}
return existe;
}
/**
* Méthode permettant l'affichage en mode texte de l'échiquier
* @return La chaîne de caractère contenant tout l'échiquier
*/
public String toString() {
String s="";
for(int i=0;i<taille;i++) {
for(int j=0;j<taille;j++) {
if(echiquier[i]!=-1 && echiquier[i]==j) {
s+="[R]";
}
else {
s+="[*]";
}
}
s+="\n";
}
return s;
}
/** Main **/
public static void main(String [] argv) {
Echiquier echiquier=new Echiquier(8);
echiquier.justDoIt(0,0);
}
} |
Problème de N-Reine
Répondre avec citation
j'ai l'impression que ce sont en fait tes méthodes putLady() et canPutLady() qu'il faudrait optimiser. Lorsque tu passes à la pièce suivante, tu fais une récursion en incrémentant simplement la ligne ou la colonne.
)
Envoyé par @po©alypse
Partager