Информатика: Расстановка шахматных фигур — различия между версиями
Материал из Department of Theoretical and Applied Mechanics
| Строка 3: | Строка 3: | ||
'''Функционал программы''': получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n; | '''Функционал программы''': получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n; | ||
| + | |||
'''Идея алгоритма''': рекурсивно вызывается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается. | '''Идея алгоритма''': рекурсивно вызывается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается. | ||
Версия 22:44, 22 декабря 2015
Функционал программы: получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n;
Идея алгоритма: рекурсивно вызывается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается.
Скачать можно тут.
1 #include <iostream>
2 #include <math.h>
3 #include <cmath>
4
5 using namespace std;
6
7 int n,type, *a, *stak, variant, maxst = 0;
8
9 void king(int x, int &top) //отметить битые клетки королем
10 {
11 // 012
12 // 345
13 // 678
14
15 //0
16 if (((x % n) > 1) && ((x / n) > 1))
17 {
18 int ii = x - n - 1;
19 if (a[ii] != -2)
20 {
21 a[ii]++;
22 stak[top] = ii;
23 top++;
24 }
25 }
26
27 //1
28 if ((x / n) > 0)
29 {
30 int ii = x - n;
31 if (a[ii] != -2)
32 {
33 a[ii]++;
34 stak[top] = ii;
35 top++;
36 }
37 }
38
39 //2
40 if (((x % n) < (n - 1)) && ((x / n) > 0))
41 {
42 int ii = x - n + 1;
43 if (a[ii] != -2)
44 {
45 a[ii]++;
46 stak[top] = ii;
47 top++;
48 }
49 }
50
51 //3
52 if ((x % n) > 0)
53 {
54 int ii = x - 1;
55 if (a[ii] != -2)
56 {
57 a[ii]++;
58 stak[top] = ii;
59 top++;
60 }
61 }
62
63 //5
64 if ((x % n) < (n - 1))
65 {
66 int ii = x + 1;
67 if (a[ii] != -2)
68 {
69 a[ii]++;
70 stak[top] = ii;
71 top++;
72 }
73 }
74
75 //6
76 if (((x % n ) > 0) && ((x / n) < (n - 1)))
77 {
78 int ii = x + n - 1;
79 if (a[ii] != -2)
80 {
81 a[ii]++;
82 stak[top] = ii;
83 top++;
84 }
85 }
86
87 //7
88 if ((x / n ) < (n - 1))
89 {
90 int ii = x + n;
91 if (a[ii] != -2)
92 {
93 a[ii]++;
94 stak[top] = ii;
95 top++;
96 }
97 }
98
99 //8
100 if (((x % n ) < (n - 1)) && ((x / n) < (n - 1)))
101 {
102 int ii = x + n + 1;
103 if (a[ii] != -2)
104 {
105 a[ii]++;
106 stak[top] = ii;
107 top++;
108 }
109 }
110 }
111
112 void bishop(int x, int &top) //отметить битые клетки слоном
113 {
114 //вверх влево
115 for (int i = (x - (n + 1)); ((i >= 0) && ((i%n) != (n-1))); i -= (n+1))
116 {
117 if (a[i] != -2)
118 {
119 a[i]++;
120 stak[top] = i;
121 top++;
122 }
123 }
124
125 //вниз вправо
126 for (int i = (x + (n + 1)); ((i < n*n) && ((i%n) != 0)); i += (n+1))
127 {
128 if (a[i] != -2)
129 {
130 a[i]++;
131 stak[top] = i;
132 top++;
133 }
134 }
135
136 //вверх вправо
137 for (int i = x - (n - 1); ((i >= 0) && ((i%n) != 0)); i -= (n-1))
138 {
139 if (a[i] != -2)
140 {
141 a[i]++;
142 stak[top] = i;
143 top++;
144 }
145 }
146
147 //вниз влево
148 for (int i = x + (n - 1); ((i < n*n) && ((i%n) != (n-1))); i += (n-1))
149 {
150 if (a[i] != -2)
151 {
152 a[i]++;
153 stak[top] = i;
154 top++;
155 }
156 }
157 }
158
159 void knight(int x, int &top) //отметить битые клетки конем
160 {
161 if (((x%n) > 0) && (x/n) > 1)
162 {
163 int ii = x - 2*n - 1;
164 if (a[ii] != -2)
165 {
166 a[ii]++;
167 stak[top] = ii;
168 top++;
169 }
170 }
171
172 if (((x%n) > 1) && (x/n) > 0)
173 {
174 int ii = x - n - 2;
175 if (a[ii] != -2)
176 {
177 a[ii]++;
178 stak[top] = ii;
179 top++;
180 }
181 }
182
183 if (((x%n) > 1) && (x/n) < (n - 1))
184 {
185 int ii = x + n - 2;
186 if (a[ii] != -2)
187 {
188 a[ii]++;
189 stak[top] = ii;
190 top++;
191 }
192 }
193
194 if (((x%n) > 0) && (x/n) < (n - 2))
195 {
196 int ii = x + 2*n - 1;
197 if (a[ii] != -2)
198 {
199 a[ii]++;
200 stak[top] = ii;
201 top++;
202 }
203 }
204
205 if (((x%n) < (n - 1)) && (x/n) < (n - 2))
206 {
207 int ii = x + 2*n + 1;
208 if (a[ii] != -2)
209 {
210 a[ii]++;
211 stak[top] = ii;
212 top++;
213 }
214 }
215
216 if (((x%n) < (n - 2)) && (x/n) < (n - 1))
217 {
218 int ii = x + n + 2;
219 if (a[ii] != -2)
220 {
221 a[ii]++;
222 stak[top] = ii;
223 top++;
224 }
225 }
226
227 if (((x%n) < (n - 2)) && (x/n) < 0)
228 {
229 int ii = x - n + 2;
230 if (a[ii] != -2)
231 {
232 a[ii]++;
233 stak[top] = ii;
234 top++;
235 }
236 }
237
238 if (((x%n) < (n - 1)) && (x/n) < 1)
239 {
240 int ii = x - 2*n + 1;
241 if (a[ii] != -2)
242 {
243 a[ii]++;
244 stak[top] = ii;
245 top++;
246 }
247 }
248 }
249
250 void rook(int x, int &top) //отметить битые клетки ладьей
251 {
252 int k = x - (x % n);
253 while ((k/n) == (x/n))
254 {
255
256 if ((k != x) && (a[k] != -2))
257 {
258 a[k]++;
259 stak[top] = k;
260 top++;
261 }
262 k ++;
263 }
264
265 k = (x % n);
266 while (((k/n)) != n)
267 {
268 if ((k != x) && (a[k] != -2))
269 {
270 a[k]++;
271 stak[top] = k;
272 top++;
273 }
274 k += n;
275 }
276
277 }
278 void set_figure(int x, int &top) //ставим фигуры на доску
279 {
280 //отмечаем "битые" клетки
281 switch (type)
282 {
283 //король
284 case 1:
285 {
286 king(x,top);
287 break;
288 }
289
290 //слон
291 case 2:
292 {
293 bishop(x,top);
294 break;
295 }
296
297 //конь
298 case 3:
299 {
300 knight(x,top);
301 break;
302 }
303 //ладья
304 case 4:
305 {
306 rook(x,top);
307 break;
308 }
309 //ферзь
310 case 5:
311 {
312 rook(x,top);
313 bishop(x,top);
314 break;
315 }
316 }
317
318 //отмечаем,что в данной клетке стоит фигура
319 a[x] = -1;
320 stak[top] = x;
321 top++;
322 }
323
324 void step(int top,int x,int st)
325 {
326 int xtop = top;
327 switch (variant)
328 {
329 case 1:
330 {
331 if (st != (n - 1))
332 {
333 set_figure(x,top);
334 for (int i = 0; i < (n*n); i++)
335 if (a[i] == 0)
336 step(top,i,st + 1);
337 }
338 else[[:File:Шахматы.rar]]
339 {
340 set_figure(x,top);
341 cout << endl;
342 for (int i = 0; i < (n*n); i++)
343 {
344 cout.width(3);
345 if (((i % n) == 0) && (i != 0))
346 cout << endl;
347 if (a[i] == -1)
348 cout << 1;
349 else
350 cout << 0;
351 }
352 cout << endl;
353 }
354 break;
355 }
356 case 2:
357 {
358 set_figure(x,top);
359 if ((st+1) > maxst)
360 maxst = st + 1;
361 for (int i = 0; i < (n*n); i++)
362 if (a[i] == 0)
363 step(top,i,st+1);
364 break;
365 }
366 }
367
368
369
370 // обратный ход
371 for (int i = xtop; i < top; i++)
372 {
373 if ((a[stak[i]] != -1) && (a[stak[i]] != -2))
374 a[stak[i]]--;
375 else
376 //не забываем отметить,что фигура уже здесь стояла(чтобы избежать повторов)
377 if (a[stak[i]] == -1)
378 a[stak[i]] = -2;
379 // cerr << " Back " << stak[i] << endl;
380 }
381 }
382
383 int main()
384 {
385
386 //cin >> n >> type >> variant;
387 n = 5;
388 type = 4;
389 variant = 1;
390 a = new int[n*n];
391 stak = new int[n*n*4];
392
393 for (int i = 0; i < (n*n); i++)
394 {
395 for (int j = 0; j < (n*n); j++)
396 a[j] = 0;
397 if (variant == 1)
398 cout << "__________________________________" << endl;
399 step(0,i,0);
400 }
401 if (variant == 2)
402 cout << maxst;
403 return 0;
404 }
