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