Информатика: Расстановка шахматных фигур
Материал из Department of Theoretical and Applied Mechanics
Версия от 00:49, 17 января 2016; Белоусова Екатерина (обсуждение | вклад)
Функционал программы: получение всевозможных расстановок 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 режима работы программы: первый выводит число возможных расстановок на экран, а список возможных расстановок в отдельный файл (при этом пользователь дополнительно выбирает число фигур); второй выводит на экран максимальное число фигур выбранного типа, которые можно расставить на заданной доске.
Посмотреть программу можно тут
Краткое описание алгоритма: Доска представлена в виде динамического массива, по ходу программы, в зависимости от алгоритмов для разных фигур, функции заполняют доску числами 0-место свободно, 1-находится под ударом и 2-занято фигурой, потом массив преобразовывается к нормальному виду 0 и 1-фигура. Так программа прогоняет все возможные варианты расстановок. Также программа аналитически просчитывает максимальное количество фигур для каждого размера доски.
Инструкция: Сначала программа просит выбрать фигуру, с которой будем работать. Затем 2 варианта развития событий: 1 - вывод в файл всех расстановок, 2 - максимальное количество фигур. В зависимости от выбора, в первом случае еще нужно ввести количество фигур, и программа запишет в файл все возможные варианты и выведет на экран число расстановок, а во втором - на экране появится максимальное кол-во фигур. Скачать можно тут.
1 '''[[Белоусова Екатерина]]'''
2
3 '''Краткое описание алгоритма''': доска представлена в виде динамического массива, заполненного 1 и 0. 1-стоит фигура, 0-пустое место. Программа при помощи рекурсии вызывает функцию, которая ставит фигуру в пустую клетку и проверяет, находится ли эта фигура под ударом других.
4
5 '''Инструкция''': пользователь вводит четный размер доски М*М, затем выбирает, какую фигуру он хочет расставить на этой доске, после чего ему предлагается выбрать количество фигур(в скобках указывается максимальное количество фигур, которые можно расставить на доске М*М).Программа выводит на экран всевозможные расстановки, пронумеровывая каждую, и сохраняет их в файл.
6
7 Скачать можно [http://tm.spbstu.ru/Файл:задача_1.zip тут].
8
9 <div class="mw-collapsible mw-collapsed" style="width:100%" >
10 <syntaxhighlight lang="cpp" line start="1" enclose="div">
11 #include <iostream>
12 #include <stdlib.h>
13 #include <stdio.h>
14 #include <string>
15 #include <cstring>
16 #include <fstream>
17 #include <locale.h>
18 #include<iomanip>
19 #include<math.h>
20
21 using namespace std;
22
23
24 int n, figureID, figura, maxCount; /// n - размер доски, figureID - номер фигуры, figura - колическтво фигур, maxCount - максимальное возможное количество фигур
25 int results_count = 0; /// определяем тип и задаем начальное значение results_count(номер результата)
26 int **mass; /// определяем двумерный массив
27
28 ///создаем массив размером n*n
29 int** create_mass(int n)
30 {
31
32 int **mass = new int* [n];
33 for (int a=0; a<n; ++a)
34 {
35 mass[a] = new int [n];
36 memset((char*)mass[a],0,n*sizeof(int)); ///зануление массива
37 }
38
39 return mass;
40
41 }
42
43 ///функция вывода массива
44 void output_mass ()
45 {
46
47 for (int a=0; a<n; ++a)///заполнение ячеек массива от 0 до n по горизонтали
48 {
49
50 for(int b=0; b<n; ++b)///заполнение ячеек массива от 0 до n по вертикали
51 {
52 cout << mass[a][b]<<" "; ///вывод массива на экран
53 }
54
55 cout << '\n';
56
57 }
58
59 cout << "Result #" << ++results_count <<"\n\n"; /// вывод номера результата
60
61 }
62
63 void zapis (char Zapis[] ) ///функции записи решений в файл
64 {
65 ofstream fout(Zapis, ios::app);///запись в фаил "Zapis"
66
67 for (int x=0; x<n; ++x)///заполнение ячеек массива от 0 до n по горизонтали
68 {
69 for(int y=0; y<n; ++y)///заполнение ячеек массива от 0 до n по вертикали
70 {
71 fout<< mass[x][y]<<" "; ///вывод решений в файл
72 }
73 fout<<'\n';
74 }
75 fout<<"\n\n";
76 fout.close();
77 }
78
79 ///проверяем наличие фигуры в строке а
80 bool isEmptyHorisontal(int a)
81 {
82
83 for(int i=0; i<n; ++i)///создаем цикл от 0 до n
84 {
85 if(mass[a][i])///в каждой ячейке массива [a][i]
86 {
87 return false;///неверно
88 }
89 }
90
91 return true;///в остальных случаях верно
92
93 }
94
95 ///проверяем наличие фигур в столбце b
96 bool isEmptyVertical(int b)
97 {
98
99 for(int i=0; i<n; ++i)///создаем цикл от 0 до n
100 {
101 if(mass[i][b])///в каждой ячейке массива [i][b]
102 {
103 return false;///неверно
104 }
105 }
106
107 return true;///в остальных случаях верно
108
109 }
110
111 ///проверяем наличие фигур на диагоналях
112 bool isEmptyDiagonales(int a, int b)
113 {
114
115 for(int i=1; a-i>=0 && b-i>=0; ++i)///диагональ влево-вверх
116 {
117 if(mass[a-i][b-i])///в каждой ячейке массива [a-i][b-i]
118 {
119 return false;///неверно
120 }
121 }
122
123 for(int i=1; a+i<n && b+i<n; ++i)///диагональ вправо-вниз
124 {
125 if(mass[a+i][b+i])///в каждой ячейке массива [a+i][b+i]
126 {
127 return false;///неверно
128 }
129 }
130
131 for(int i=1; a+i<n && b-i>=0; ++i)///диагональ влево-вниз
132 {
133 if(mass[a+i][b-i])///в каждой ячейке массива [a+i][b-i]
134 {
135 return false;///неверно
136 }
137 }
138
139 for(int i=1; a-i>=0 && b+i<n; ++i)///диагональ вправо-вверх
140 {
141 if(mass[a-i][b+i])///в каждой ячейке массива [a-i][b+i]
142 {
143 return false;///неверно
144 }
145 }
146
147 return true;///в остальных случаях верно
148
149 }
150
151 ///проверяем наличие фигур по горизонтали, вертикали и диагоналям
152 bool tryQueen(int a, int b)
153 {
154
155 if (!isEmptyHorisontal(a) || !isEmptyVertical(b) || !isEmptyDiagonales(a,b))///если не выполняются эти условия,
156 ///т.е. постановка фигуры не удовлетворяет расстановке
157 ///по горизонтали, или по вертикали, или по диагонали
158 return false;///неверно
159
160 return true;///в остальных случаях верно
161
162 }
163
164 /// функция поиска результатов решений.
165 /// row - номер очередной строки в которую нужно поставить очередного ферзя.
166 /// count - количество фигур, поставленое к данному моменту
167 void setQueen(int row, int count)
168 {
169
170 for(int column=0; column<n; ++column)///двигаемся по столбцу сверху вниз
171 {
172
173 if(tryQueen(row, column))/// проверка, если поставить ферзя в ячейку [row][column],
174 ///будет ли он единственным в этих строке, столбце и диагоналях
175 {
176 mass[row][column]=1;
177
178 if(count+1==figura) /// нужное количество фигур поставлено
179 {
180 output_mass(); /// вызов функции вывода массива на экран
181 zapis("Zapis");///записываем в файл
182 }
183
184 else
185 {
186 for(int i = row + 1; i<n; i++)/// ставим следующего ферзя в одну из следующих строк
187 setQueen(i,count+1);///и повторяем цикл
188 }
189
190 mass[row][column]=0;
191
192 }
193
194 }
195
196 }
197
198 bool tryRook(int a, int b)///проверка на наличие фигур по вертикали и горизонтали
199 {
200
201 if (!isEmptyHorisontal(a) || !isEmptyVertical(b))///если не выполняются эти условия,
202 ///т.е. постановка фигуры не удовлетворяет расстановке
203 ///по горизонтали, или по вертикали
204 return false;///неверно
205
206 return true;///в остальных случаях верно
207
208 }
209
210 /// функция поиска результатов решений.
211 /// row - номер очередной строки в которую нужно поставить очередную ладью
212 /// count - количество фигур, поставленое к данному моменту
213 void setRook(int row, int count)
214 {
215
216 for(int column=0; column<n; ++column)///двигаемся по столбцу сверху вниз
217 {
218
219 if(tryRook(row, column))/// проверка, если поставить ладью в A[row][column], будет ли она единственной в этих строке и столбце
220 {
221
222 mass[row][column]=1;
223
224 if(count+1==figura) /// нужное количество фигур поставлено
225 {
226 output_mass(); /// вызов функции вывода массива на экран
227 zapis("Zapis");///записываем в файл
228 }
229
230 else
231 {
232 for(int i = row + 1; i<n; i++)/// ставим следующую ладью в одну из следующих строк
233 setRook(i,count+1);///и повторяем цикл
234 }
235
236 mass[row][column]=0;
237
238 }
239
240 }
241
242 }
243
244 bool tryElephant(int a, int b) ///проверка на наличие фигур по диагоналям.
245 {
246
247 if (!isEmptyDiagonales(a,b))///если не выполняется это условие,
248 ///т.е. постановка фигуры не удовлетворяет расстановке по диагоналям
249 return false;
250
251 return true;
252
253 }
254
255 /// функция поиска результатов решений.
256 /// diagonale - номер диагонали в которую нужно поставить очередного слона
257 /// count - количество фигур, поставленое к данному моменту
258 void setElephant(int diagonale, int count)
259 {
260
261 int a, b; /// опорная точка диагонали (крайняя левая)
262
263 if (diagonale < n)///если номер диагонали меньше n
264 {
265 a = diagonale;///значению а присвоить значенье номера диагонали
266 b = 0;///значению b присвоить значение 0
267 }
268
269 else///иначе
270 {
271 a = n-1;///значению а присвоить значение n-1
272 b =(diagonale % n)+1;///значению b присвоить значение целого частного от деления номера диагонали на n прибавив к нему 1
273 }
274
275 /// перебираем все "столбцы" текущей диагонали
276 for(int dcolumn=0; a-dcolumn>=0 && b+dcolumn < n; ++dcolumn)
277 {
278
279 /// рассчёт координат клетки по координатам крайней точки диагонали и "столбца" в диагонали
280 int x = a-dcolumn;
281 int y = b+dcolumn;
282
283 if(tryElephant(x, y))/// проверка, если поставить слона в A[row][column], будет ли он единственным по диагоналям
284 {
285
286 mass[x][y]=1;
287
288 if(count+1==figura) /// нужное количество фигур поставлено
289 {
290 output_mass(); /// вызов функции вывода массива на экран
291 zapis("Zapis");///запись в файл
292 }
293
294 else
295 {
296 for(int i = diagonale + 1; i<2*n-1; i++)/// ставим следующего слона в одну из следующих диагоналей
297 setElephant(i,count+1);///и повторяем цикл
298 }
299
300 mass[x][y]=0;
301
302 }
303
304 }
305
306 }
307
308 /// проверка на наличие фигуры на позиции x,y
309 bool isFigure(int x, int y)
310 {
311 return 0 <= x && x < n && 0 <= y && y < n && mass[x][y];
312 }
313
314 ///проверка на наличие короля в квадрате 3 на 3
315 bool tryKing(int a, int b)
316 {
317
318 for(int i = a-1; i <= a+1; i++)///для ячеек находящихся слева и справа от поставленного короля
319 {
320 for(int j = b-1; j <= b+1; j++)///для ячеек находящихся снизу и сверху от поставленного короля
321 {
322 if (isFigure(i,j))///если выполняется это условие
323 return false;///неверно
324 }
325 }
326
327 return true;///в остальных случаях верно
328
329 }
330
331 ///функция поиска результатов решений
332 /// count - количество фигур, поставленое к данному моменту
333 ///x,y - позиция, начиная с которой разрешено ставить фигуры (все предшествующие позиции уже точно определены)
334 void setKing(int count, int x, int y)
335 {
336
337 if(count==figura)///figura - количество фигур, вводимых пользователями.
338 {
339 output_mass();/// вызов функции вывода массива на экран
340 zapis("Zapis");///записываем в файл
341 return;
342 }
343
344 if (x == n) /// строки закончились
345 return;
346
347 /// обрабатываем текущую строку
348 for (int j=y; j<n; ++j)
349 {
350
351 if(tryKing(x, j))
352 {
353 mass[x][j]=1;
354 /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки
355 int nextX = x, nextY = j+1;
356
357 if (nextY == n)///если столбец последний
358 {
359 nextY = 0;///идем сначала по столбцам
360 nextX++;///к строке прибавляем 1
361 }
362
363 /// ставим следующего короля
364 setKing(count+1,nextX,nextY);
365 mass[x][j]=0;
366
367 }
368
369 }
370
371 /// обрабатываем прямоугольник ниже текущей строки
372 for(int i=x+1; i<n; ++i)
373 {
374
375 for (int j=0; j<n; ++j)
376 {
377
378 if(tryKing(i, j))
379 {
380 mass[i][j]=1;
381 /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки
382 int nextX = i, nextY = j+1;
383
384 if (nextY == n)///если столбец последний
385 {
386 nextY = 0;///идем сначала по столбцам
387 nextX++;///к строке прибавляем 1
388 }
389
390 /// ставим следующего короля
391 setKing(count+1,nextX,nextY);
392 mass[i][j]=0;
393
394 }
395
396 }
397
398 }
399
400 }
401
402 bool tryHorse(int a, int b) ///проверка на коней по всем направлениям
403 {
404
405 if (isFigure(a-1,b-2) || isFigure(a-1,b+2) || isFigure(a+1,b-2) || isFigure(a+1,b+2) || isFigure(a-2,b-1) || isFigure(a-2,b+1) || isFigure(a+2,b-1) || isFigure(a+2,b+1))
406 ///если выполняются эти условия,
407 ///т.е. фигара стоит на одной из этих позиций
408 return false;///неверно
409
410 return true;///в остальных случаях верно
411
412 }
413
414 ///функция поиска результатов решений
415 /// count - количество фигур, поставленое к данному моменту.
416 void setHorse(int count, int x, int y)
417 {
418
419 if(count==figura)///figura - количество фигур, вводимых пользователями.
420 {
421 output_mass();/// вызов функции вывода массива на экран
422 zapis("Zapis");///записываем в файл
423 return;
424 }
425
426 if (x == n)/// строки закончились
427 return;
428
429 /// обрабатываем текущую строку
430 for (int j=y; j<n; ++j)
431 {
432
433 if(tryHorse(x, j))
434 {
435
436 mass[x][j]=1;
437 /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки
438 int nextX = x, nextY = j+1;
439
440 if (nextY == n)///если столбец последний
441 {
442 nextY = 0;///идем сначала по столбцам
443 nextX++;///к строке прибавляем 1
444 }
445
446 /// ставим следующего коня
447 setHorse(count+1,nextX,nextY);
448 mass[x][j]=0;
449
450 }
451
452 }
453
454 /// обрабатываем прямоугольник ниже текущей строки
455 for(int i=x+1; i<n; ++i)
456 {
457
458 for (int j=0; j<n; ++j)
459 {
460
461 if(tryHorse(i, j))
462 {
463
464 mass[i][j]=1;
465 /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки
466 int nextX = i, nextY = j+1;
467
468 if (nextY == n)///если столбец последний
469 {
470 nextY = 0;///идем сначала по столбцам
471 nextX++;///к строке прибавляем 1
472 }
473
474 setHorse(count+1,nextX,nextY);
475 mass[i][j]=0;
476
477 }
478
479 }
480
481 }
482
483 }
484
485 int main()
486 {
487 setlocale(LC_ALL,"RUS");
488
489 ofstream Zapis("Zapis", ios::trunc);///сохраняем в файл
490 Zapis.close();
491
492 do
493 {
494 cout << "Введите размер доски (четный): ";
495 cin >> n; ///ввод пользователем размера доски
496 }while (n%2 != 0);
497
498 mass=create_mass(n); ///создаём двумерный массив
499
500 cout<<"Queen-1, Rook-2, Elephant-3, King-4, Horse-5"<< endl;
501 cin >> figureID; ///выбор пользователем фигуры
502
503 /// устанавливаем максимальное количество в зависимости от фигуры
504 if (figureID==1)
505 maxCount=n;
506 if (figureID==2)
507 maxCount=n;
508 if (figureID==3)
509 maxCount=2*n-2;
510 if (figureID==4)
511 maxCount=(n*n)/4;
512 if (figureID==5)
513 maxCount=(n*n)/2;
514
515 /// запрашиваем количество фигур
516 do
517 {
518 cout << "Введите количество фигур (максимальное количество - " << maxCount << "): ";
519 cin >> figura;
520 }while (figura>maxCount);
521
522 /// запускаем перебор
523 if (figureID==1)
524 {
525 for(int i = 0; i<n; i++)
526 setQueen(i,0);
527 zapis("Zapis");
528 }
529 if (figureID==2)
530 {
531 for(int i = 0; i<n; i++)
532 setRook(i,0);
533 zapis("Zapis");
534 }
535 if (figureID==3)
536 {
537 for(int i = 0; i<2*n-1; i++)
538 setElephant(i,0);
539 zapis("Zapis");
540 }
541 if (figureID==4)
542 {
543 setKing(0,0,0);
544 zapis("Zapis");
545 }
546 if (figureID==5)
547 {
548 setHorse(0,0,0);
549 zapis("Zapis");
550 }
551 system("PAUSE");
552 }
