Информатика: Расстановка шахматных фигур
Материал из Department of Theoretical and Applied Mechanics
Версия от 00:24, 3 января 2016; Pepper (обсуждение | вклад)
Функционал программы: получение всевозможных расстановок 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 }
Краткое описание алгоритма: Функция, которая выполняет поиск расстановок, пытается поставить фигуру в каждую клетку. В случае неудачи программа отмечает клетки, в которых фигура уже побывала, но постановка не удалась, отрицательной величиной, равной по модулю шагу, на котором эта постановка была испробована. В случае пустой клетки она отмечается нулем, в случае успеха клетка отмечается положительным числом, равным шагу, соответствующему попытке постановки. Также программа аналитически просчитывает максимальное количество фигур для каждого размера доски.
Инструкция: В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей. Он вводит размер доски и тип фигуры. Если он выбирает максимальное число расстановок, то программа выводит их количество, а также предлагает вывести все расстановки на экран. Другой вариант работы программы - вывод расстановок N фигур.
Посмотреть программу можно здесь
1 #include <iostream>
2 #include <algorithm>
3 #include <exception>
4 #include <string>
5 #include <algorithm>
6
7 //пусть для определенности максимальный размер доски - 128 клеток
8 #define MAX_SIZE 128
9
10 // перечисление для определения типа фигуры
11 enum figure_type
12 {
13 KING,
14 QUEEN,
15 ROOK,
16 BISHOP,
17 KNIGHT
18 };
19
20 // класс для создания доски и расстановки фигур
21 class chess_board
22 {
23 public:
24 // конструктор (принимает только размеры)
25 chess_board(const int &size)
26 {
27 if (size >= 0 && size <= MAX_SIZE)
28 {
29 size_ = size;
30 clean_board();
31 }
32
33 else
34 {
35 std::cout << "wrong size" << std::endl;
36 throw std::string("wrong size");
37 }
38 }
39
40
41 // функция очистки доски (занулить все клетки)
42 void clean_board()
43 {
44 //обнулить счетчик количества фигур на доске
45 figures_on_board_ = 0;
46 //присвоить всем клеткам значение 0
47 for (int i = 0; i < size_; ++i)
48 {
49 for (int j = 0; j < size_; ++j)
50 {
51 board_[i][j] = 0;
52 }
53 }
54 }
55
56 // функция, принимающая размер доски
57 int get_size()
58 {
59 return size_;
60 }
61 // функция, обновляющая количество фигур на доске
62 int get_figures_number()
63 {
64 return figures_on_board_;
65 }
66
67 //функция, пытающаяся поставить фигуру на свободное место и возвращающая
68 //истину в случае успеха и ложь в случае неудачи
69 bool put_figure (const figure_type& figure, const int& x, const int& y, const int& step)
70 {
71 if (board_[x][y] > 0 || board_[x][y] < -step)
72 {
73 //если здесь уже стоит фигура или мы когда-то пытались ее сюда поставить, вернуть ложь
74 return false;
75 }
76
77 if (check_figure(figure, x, y))
78 {
79 board_[x][y] = step;
80 ++figures_on_board_;
81 return true;
82 }
83 else
84 {
85 return false;
86 }
87 }
88
89 //отметить клетку как ранее пройденную функцией
90 //вычесть единицу из количества фигур на доске
91 void remove_figure(const int& x, const int& y)
92 {
93 board_[x][y] *= -1;
94 --figures_on_board_;
95 }
96
97 //функция печати доски на экран
98 void print() const
99 {
100 using namespace std;
101 cout << "==========================================" << endl;
102 for (int i = 0; i < size_; ++i)
103 {
104 for (int j = 0; j < size_; ++j)
105 {
106 //если фигура стоит в клетке, то вывести "*", если нет - вывести "-"
107 cout << (board_[i][j] > 0?"*":"-") << " ";
108 }
109 cout << endl;
110 }
111 cout << "==========================================" << endl;
112 }
113
114 private:
115
116 //функция, проверяющая возможность или невозможность постановки фигуры на данную клетку
117 bool check_figure(const figure_type& figure, const int& x, const int& y)
118 {
119 //выбор следующего действия в зависимости от типа фигуры
120 switch (figure)
121 {
122 case KING:
123 return check_king(x, y);
124 case QUEEN:
125 return check_queen(x, y);
126 case ROOK:
127 return check_rook(x, y);
128 case BISHOP:
129 return check_bishop(x, y);
130 case KNIGHT:
131 return check_knight(x, y);
132 //в случае ошибки ввода вернуть ложь
133 default:
134 return false;
135 }
136 }
137
138 //поиск расстановок короля
139 bool check_king(const int& x, const int& y)
140 {
141 int min_x = std::max(x - 1, 0);
142 int max_x = std::min(x + 1, size_ - 1);
143 int min_y = std::max(y - 1, 0);
144 int max_y = std::min(y + 1, size_ - 1);
145
146 for (int i = min_x; i <= max_x; ++i)
147 {
148 for (int j = min_y; j <= max_y; ++j)
149 {
150 if (board_[i][j] > 0)
151 {
152 return false;
153 }
154 }
155 }
156 return true;
157 }
158
159 //поиск расстановок ладьи
160 bool check_rook(const int& x, const int& y)
161 {
162 for (int i = 0; i < size_; ++i)
163 {
164 if (board_[i][y] > 0)
165 {
166 return false;
167 }
168 }
169 for (int j = 0; j < size_; ++j)
170 {
171 if (board_[x][j] > 0)
172 {
173 return false;
174 }
175 }
176 return true;
177 }
178
179 //поиск расстановок слона
180 bool check_bishop(const int& x, const int& y)
181 {
182 bool check = true;
183
184 int k_start_1 = -std::min(x, y);
185 int k_end_1 = std::min( size_ - x, size_ - y) - 1;
186
187 int k_start_2 = -std::min( x, size_ - y - 1);
188 int k_end_2 = std::min( y, size_ - x - 1);
189
190
191 for (int k = k_start_1; k <= k_end_1; ++k)
192 {
193 check = check_coord(x + k, y + k) && check ;
194 }
195 for (int k = k_start_2; k <= k_end_2; ++k)
196 {
197 check = check_coord(x + k, y - k) && check;
198 }
199
200 return check;
201 }
202
203
204 //поиск расстановок коня
205 bool check_knight(const int& x, const int& y)
206 {
207 bool check =
208 check_coord(x - 2, y - 1) &&
209 check_coord(x - 2, y + 1) &&
210 check_coord(x - 1, y - 2) &&
211 check_coord(x - 1, y + 2) &&
212 check_coord(x + 1, y - 2) &&
213 check_coord(x + 1, y + 2) &&
214 check_coord(x + 2, y - 1) &&
215 check_coord(x + 2, y + 1);
216 return check;
217 }
218
219 //поиск расстановок королевы
220 bool check_queen(const int& x, const int& y)
221 {
222 return check_rook(x, y) && check_bishop(x, y);
223 }
224
225 //функция поиска расстановок, в случае, когда на доске что-то стоит, вернуть ложь
226 //иначе поставить вернуть истину
227 bool check_coord(const int& x, const int& y)
228 {
229 if (x >= 0 && x < size_ && y >= 0 && y < size_)
230 {
231 if (board_[x][y] > 0)
232 {
233 return false;
234 }
235 }
236 return true;
237 }
238
239 // if board_[x][y] == 0
240 // клетка свободна
241 // if board_[x][y] == s
242 // фигура была поставлена на шаге S
243 // if board_[x][y] == -s
244 // клетка свободна, но была попытка поставить фигуру на шаге S
245 int board_[MAX_SIZE][MAX_SIZE];
246 int size_;
247 int figures_on_board_;
248 };
249
250 //функция расчета максимума для любой доски в зависимости от типа фигуры
251 int get_max_figures (const figure_type& figure, const int& size)
252 {
253 switch (figure)
254 {
255 case KING:
256 return (size + 1) / 2;
257 case QUEEN:
258 if (size <= 2)
259 {
260 return 1;
261 }
262 else if (size == 3)
263 {
264 return 2;
265 }
266 else
267 {
268 return size;
269 }
270 case ROOK:
271 return size;
272 case BISHOP:
273 if (size == 1)
274 {
275 return size;
276 }
277 else
278 {
279 return 2 * (size - 1);
280 }
281 case KNIGHT:
282 if (size <= 2)
283 {
284 return size * size;
285 }
286 else
287 {
288 return (size * size + 1) / 2;
289 }
290 default:
291 return 1;
292 }
293 }
294
295 //функция для расстановки максимального числа фигур на доске
296 void place_figures_for_max(chess_board &board, const figure_type& figure, const int& max_figures, int step)
297 {
298 ++step;
299 const int size = board.get_size();
300 for (int i = 0; i < size; ++i)
301 {
302 for (int j = 0; j < size; ++j)
303 {
304 //если мы можем поставить фигуру, то добавляем к максимуму единицу и запускаем цикл снова
305 if (board.put_figure(figure, i, j, step))
306 {
307 //если число фигур на доске достигло максимума, то вывести доску
308 if (board.get_figures_number() == max_figures)
309 {
310 board.print();
311 }
312 //если число фигур не достигло максимума, продолжить выполнение функции
313 else
314 {
315 place_figures_for_max(board, figure, max_figures, step);
316 }
317 board.remove_figure(i, j);
318 }
319 }
320 }
321 }
322
323 //функция, принимающая ввод с клавиатуры как строковый тип данных
324 figure_type get_figure_type(const std::string& str)
325 {
326 using namespace std;
327
328 figure_type figure;
329 if (str == string("king"))
330 {
331 figure = KING;}
332 else if (str == string("queen"))
333 {
334 figure = QUEEN;}
335 else if (str == string("rook"))
336 {
337 figure = ROOK;
338 }
339 else if (str == string("bishop"))
340 {
341 figure = BISHOP;
342 }
343 else if (str == string("knight"))
344 {
345 figure = KNIGHT;
346 }
347 //вывести ошибку в случае неверного ввода
348 else
349 {
350 cout << "wrong figure type" << endl;
351 throw string("wrong figure type");
352 }
353
354 return figure;
355 }
356
357 int main()
358 {
359 //использовать стандартное пространств имен
360 using namespace std;
361
362 int size;
363 string type_of_figure;
364 string type_of_action;
365 figure_type figure;
366
367 cout << "Возможные фигуры: king, queen, rook, bishop, knight" << endl;
368 cout << "Возможные действия: max, placing" << endl;
369 cout << "----------------------------------------------------" << endl;
370
371 cout <<"Введите размер доски: ";
372 cin >> size;
373 chess_board board(size);
374
375 cout << "Введите тип фигуры: ";
376 cin >> type_of_figure;
377 figure = get_figure_type(type_of_figure);
378
379 cout << "Введите необходимое действие: ";
380 cin >> type_of_action;
381
382 if (type_of_action == string("max"))
383 {
384
385 int max_figures = get_max_figures(figure, size);
386 cout << "Max figures: " << max_figures << endl;
387
388 cout << "Хотите ли вы просмотреть все варианты? (yes/no) ";
389 string answer;
390 cin >> answer;
391 //если нужно вывести все расстановки, то применить непосредственно функцию поиска расстановок максимума
392 if (answer == string("yes"))
393 {
394 int step = 0;
395 place_figures_for_max(board, figure, max_figures, step);
396 }
397 }
398 //иначе если нужно расставить определенное количество фигур, то применить функцию поиска расстановок
399 //относительно введенного числа
400 else if (type_of_action == string("placing"))
401 {
402 int figures_to_place;
403 cout << "Сколько фигур нужно расставить: ";
404 cin >> figures_to_place;
405
406 int step = 0;
407 place_figures_for_max(board, figure, figures_to_place, step);
408 }
409 //иначе вывести ошибку действия
410 else
411 {
412 cout << "wrong type of action" << endl;
413 throw string("wrong type of action");
414 }
415
416 return 0;
417 }
