Информатика: Расстановка шахматных фигур
Функционал программы: получение всевозможных расстановок 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 }
Краткое описание алгоритма:если шахматную доску представить в виде одной строчки(вторую поставить следом за первой, третью за второй и тд), то получится двоичное число. Максимальное число которое может получиться если 111...111 перевести в десятичное ,это число М*М. Тогда абсолютно ВСЕ варианты расстановки фигур это двоичные записи чисел от 0 до М*М. В программе есть цикл, который рассматривает каждый вариант для числа от 0 до М*М, переводит его в двоичную форму. Программа рассматривает каждую клетку, где стоит фигура. Если эта фигура бьет других, то цикл прерывается, нам такой вариант не подходит. Если никакая фигура не бьет никакую другую, то идет подсчет количества фигур на доске. Если фигур столько, сколько нужно, то вывод на экран.
Инструкция: На экране показано соответствие каждому номеру типа фигуры. Пользователь выбирает тип фигуры, испольуя номер. Дальше нужно ввести размер доски. Затем на экране появляется два варианта количества фигур на доске: максимальное или введенное пользователем. Пользователь выбирает вариант. Если второй, то затем надо будет ввести количество фигур. Программа
Краткое описание алгоритма: Для каждой фигуры написана отдельная функция, выполняющая поиск расстановок. После выбора типа фигуры, соответствующая функция выполняет поиск возможных расстановок. Она проходя по строкам двумерного массива пытается поставить фигуру в каждую клетку. Проходя по массиву она маркирует клетки, ставит 0 (если клетка свободна), 1 (если клетка находится под ударом), 2 (если клетка занята). Программа аналитически считает максимальное количество фигур для заданного размера доски, возможное число расстановок для заданных типа фигуры, размера доски и количества фигур.
Инструкция: При запуске программы появляется меню, в котором каждому типу фигуры сопоставлен номер, с помощью которого пользователь и выбирает тип фигуры. Затем пользователю на выбор предлагается 2 режима работы программы: первый выводит число возможных расстановок на экран, а список возможных расстановок в отдельный файл (при этом пользователь дополнительно выбирает число фигур); второй выводит на экран максимальное число фигур выбранного типа, которые можно расставить на заданной доске.
Посмотреть программу можно тут
