Информатика: Расстановка шахматных фигур — различия между версиями
Материал из Department of Theoretical and Applied Mechanics
Loban9614 (обсуждение | вклад) |
Loban9614 (обсуждение | вклад) |
||
| Строка 3370: | Строка 3370: | ||
cout << func(n, k, 0, v, 0, 0, fig, task); | cout << func(n, k, 0, v, 0, 0, fig, task); | ||
} | } | ||
| + | </syntaxhighlight> | ||
| + | </div> | ||
| + | |||
| + | '''[[Лобанов Илья]]''' | ||
| + | |||
| + | '''Описание алгоритма''': | ||
| + | |||
| + | Программа проверяет возможность расстановки фигур на доске M*M . При выводе на экран на экран клетки,занятые фигурами ,помечаются буквами,соответствующими первой букве типа фигуры. Также программа считает максимальное число фигур определенного типа,которые можно расставить на доске. | ||
| + | |||
| + | '''Инструкция''' | ||
| + | В окне консоли пользователю предлагается выбрать 2 типа работы программы, затем пользователь вводит размер доски(четный),тип и количество фигур,которые необходимо разместить на доске.В зависимости от режима работы программы ,будет выведено либо максимально возможное число расстановок фигур,либо максимальное число фигур. | ||
| + | Скачать можно тут [[http://tm.spbstu.ru/File:ConsoleApplication54.rar]] | ||
Версия 18:34, 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 до М*М, переводит его в двоичную форму. Программа рассматривает каждую клетку, где стоит фигура. Если эта фигура бьет других, то цикл прерывается, нам такой вариант не подходит. Если никакая фигура не бьет никакую другую, то идет подсчет количества фигур на доске. Если фигур столько, сколько нужно, то вывод на экран.
Инструкция: На экране показано соответствие каждому номеру типа фигуры. Пользователь выбирает тип фигуры, испольуя номер. Дальше нужно ввести размер доски. Затем на экране появляется два варианта количества фигур на доске: максимальное или введенное пользователем. Пользователь выбирает вариант. Если второй, то затем надо будет ввести количество фигур. Программа
1
2 #include <cstring>
3 #include <iostream>
4 #include"math.h"
5 #include <fstream>
6 using namespace std;
7
8 int M, N; // M-размер доски, N-коичество шахмат.
9 int sum;//нужно в процессе для подсчета количества шахмат
10 int **ChessBoard= new int* [M];
11
12 void ChessBoards(int k) //создание доски, k-число, которое переводим в двоичную запись, чтобы отобразить на доске расстановку фигур, 1-фигура есть, 0-нет.
13 {
14 for (int i=0; i<M; i++) //создание массива
15 {
16 ChessBoard[i] = new int[M];
17 }
18 for (int x=(M-1); x>=0; x=x-1)//заполнение массива фигурами (переводя k в двоичную форму)
19 {
20 for (int y=(M-1); y>=0; y=y-1)
21 {
22 ChessBoard[x][y]=(k%2);
23 k=k/2;
24 }
25 }
26 }
27 void print (char filename[] ) ///создание функции вывода массива в файл
28 {
29 ofstream fout(filename, ios::app);
30
31 for (int x=0; x<M; ++x)
32 {
33 for(int y=0; y<M; ++y)
34 {
35 fout << ChessBoard[x][y]<<" "; ///вывод массива в файл
36 }
37 fout <<'\n';
38
39 }
40 fout <<"\n\n";
41
42 fout.close();
43 }
44
45
46
47 bool CheckHorse(int x, int y)//проверка для коня в клетке с номером x, y
48 {
49
50 if (((x+1)<M) && ((y+2)<M) && (ChessBoard[x+1][y+2]==1))//если в клетке, куда может сходить конь (х+1,у+2) уже есть фигура, то этот вариант не подходит, так как один конь бьет другого.
51 {
52 return false;
53
54 }
55 else if (((x+1)<M ) && ((y-2)>=0) && (ChessBoard[x+1][y-2]==1))//то же самое и в остальных случаях проверяем бьет ли один конь другого.
56 {
57 return false;
58
59 }
60 else if (((x-1)>=0) && ((y+2)<M) && (ChessBoard[x-1][y+2]==1))
61 {
62 return false;
63 }
64 else if (((x-1)>=0) && ((y-2)>=0) && (ChessBoard[x-1][y-2]==1))
65 {
66 return false;
67 }
68 else if (((x+2)<M) && ((y+1)<M) && (ChessBoard[x+2][y+1]==1))
69 {
70 return false;
71 }
72 else if (((x+2)<M ) && ((y-1)>=0) && (ChessBoard[x+2][y-1]==1))
73 {
74 return false;
75 }
76 else if (((x-2)>=0 ) && ((y+1)<M) && (ChessBoard[x-2][y+1]==1))
77 {
78 return false;
79 }
80 else if (((x-2)>=0 ) && ((y-1)>=0) && (ChessBoard[x-2][y-1]==1))
81 {
82 return false;
83 }
84 else //в итоге, если конь, стоящий в данной клетке никого не бьет, то этот вариант подходит
85 {
86 return true;
87 }
88 }
89
90 int Horse(int k)//k-то число которое нужно будет перевести в двоичную форму, это делается в main'е
91 //в этой функции считаем количество фигур, если он равно введенному или максимальному,то доска подходит и выводится в файл (все это в main'е)
92 {
93 for (int x=0; x<M; x++)
94 {
95 int y;
96 for (y=0; y<M; y++)
97 {
98 if (ChessBoard[x][y]==1)//если в данной клетке стоит конь, то нужно проверить,
99 // бьет оно кого-то или нет...
100 //если в клетке нет коня, то ее проверять не нужно
101 {
102 if (CheckHorse(x,y))//...делаем это с помощью этой функции,если конь в данной клетке х;у
103 //никого не бьет, то прибавляем 1 к количеству шахмат на доске и считаем дальше
104 {
105 sum=sum+1;
106 }
107 else //а если бьет, то выходим из цикла, на данной этапе выйдем только из внуреннего
108 {
109 sum=0;//количество фигур обнуляем
110 break;
111 }
112 }
113 }
114 if (y<M)//если из внутреннего цикла вышли раньше, значит у досчитался не до конца,
115 //то есть он меньше своего максимального значения М
116 {
117
118 break;//тогда выходим и из внешнего цикла
119 }
120 }
121 return sum; //возвращаем количество фигур
122 }
123
124 bool CheckKing(int x, int y) //все то же самое для проверки короля, стоящего в клетке х,у
125 {
126
127 if (((x+1)<M) && ((y+1)<M) && (ChessBoard[x+1][y+1])==1)//если в клетке куда может сходить король
128 //уже есть фигура, то клетка не подходит и т.д
129 {
130 return false;
131
132 }
133 else if (((x+1)<M ) && (ChessBoard[x+1][y]==1))
134 {
135 return false;
136
137 }
138 else if (((x+1)<M) && ((y-1)>=0) && (ChessBoard[x+1][y-1]==1))
139 {
140 return false;
141 }
142 else if (((x-1)>=0) && ((y-1)>=0) && (ChessBoard[x-1][y-1]==1))
143 {
144 return false;
145 }
146 else if (((x-1)>=0) && ((y+1)<M) && (ChessBoard[x-1][y+1]==1))
147 {
148 return false;
149 }
150 else if (((x-1)>=0) && (ChessBoard[x-1][y]==1))
151 {
152 return false;
153 }
154 else if (((y+1)<M) && (ChessBoard[x][y+1]==1))
155 {
156 return false;
157 }
158 else if (((y-1)>=0) && (ChessBoard[x][y-1]==1))
159 {
160 return false;
161 }
162 else
163 {
164 return true;
165 }
166 }
167
168 int King(int k) //так же как и для коня, проверяем каждую клетку
169 //подходит-прибавляем к количеству фигур sum единичку, нет-обнуляем сумму и выходим из цикла
170 {
171 for (int x=0; x<M; x++)
172 {
173 int y;
174 for (y=0; y<M; y++)
175 {
176 if (ChessBoard[x][y]==1)
177 {
178 if (CheckKing(x,y))
179 {
180 sum=sum+1;
181 }
182 else
183 {
184 sum=0;
185 break;
186 }
187 }
188 }
189 if (y<M)
190 {
191 break;
192 }
193 }
194 return sum;
195 }
196
197 int CheckQueen(int x, int y)///проверка для королевы, принцип тот же, королева стит в клеке x,y
198 ///1 значит как true в bool (как в коне или короле), 0 - false
199 { int returnn=1;//начала true, дальше если будет false, то return примет значение 0, а если все пдходит
200 ///то так и стается 1
201 int m;
202 for (m=1; m<M; m++)
203 { //проверяем для диагоналей
204 ///если по диагонале клетки х,у стоит еще королва, то такой вариант не подходит, выходим из цикла
205 ///разбито на 4 услвия, так как если не разбивать, то клетка в кторой стоит данная королева
206 ///тоже будет считаться и выходить из цикла
207 if (((x+m)<M)&&((y+m)<M))
208 {
209 if (ChessBoard[x+m][y+m]==1)
210 {returnn=0;
211 break;
212 }
213 }
214 if (((x-m)>=0)&&((y+m)<M))
215 {
216 if (ChessBoard[x-m][y+m]==1)
217 {returnn=0;
218 break;}
219 }
220 if (((x+m)<M)&&((y-m)>=0))
221 {
222 if (ChessBoard[x+m][y-m]==1)
223 {returnn=0;
224 break;}
225 }
226 if (((x-m)>=0)&&((y-m)>=0))
227 { if (ChessBoard[x-m][y-m]==1)
228 {returnn=0;
229 break;}
230 }
231 if (m!=x) ///тут считаем по вертикали и горизонтали, так как длаем в цикле для m, то m меняется
232 ///и в какой-то момент может стать х, и тогда роверятьбуде клетку в которой стоит ДАННАЯ и выходить
233 ///это не нужно так что выходим только если m не равен x
234 {
235 if (ChessBoard[m][y]==1) //если по горизонтали есть какая-о клетка, где стоит королева, то выходим
236 {
237 returnn=0;
238 break;
239 }
240 }
241 if (m!=y)//то же по вертикали
242 {
243 if (ChessBoard[x][m]==1)
244 {
245 returnn=0;
246 break;
247 }
248 }
249 }
250 return returnn;
251 }
252
253 int Queen(int k)//тут также как и для коня и короля
254 {
255 for (int x=0; x<M; x++)
256 {
257 int y;
258 for (y=0; y<M; y++)
259 {
260 if (ChessBoard[x][y]==1)//если в клетке королева, проверяем подходи ли она нам
261 {
262 if (CheckQueen(x,y))
263 {
264 sum=sum+1;
265 }
266 else
267 {
268 sum=0;
269 break;
270 }
271 }
272 }
273 if (y<M)
274 {
275 break;
276 }
277 }
278 return sum;
279 }
280
281 int CheckRook(int x, int y)///ладья, просто берем ту часть из проверки королевы, где проверка по горизонтали и вертикали
282 { int returnn=1;
283 int m;
284 for (m=0; m<M; m++)
285
286 {
287 if (m!=x)
288 {
289 if (ChessBoard[m][y]==1)
290 {
291 returnn=0;
292 break;
293 }
294 }
295 if (m!=y)
296 {
297 if (ChessBoard[x][m]==1)
298 {
299 returnn=0;
300 break;
301 }
302 }
303 }
304
305
306 return returnn;
307 }
308
309 int Rook(int k)//все то же самое, количество фигур на доске
310 {
311 for (int x=0; x<M; x++)
312 {
313 int y;
314 for (y=0; y<M; y++)
315 {
316 if (ChessBoard[x][y]==1)
317 {
318 if (CheckRook(x,y)==1)
319 {
320 sum=sum+1;
321
322 }
323 else
324 {
325 sum=0;
326 break;
327 }
328 }
329 }
330 if (y<M)
331 {
332 break;
333 }
334 }
335
336 return sum;
337 }
338
339 int CheckElephant(int x, int y)//для слона берем ту часть прроверки королевы, где по диагонали
340 { int returnn=1;
341 for (int i=1; i<M; i++)
342 {
343 if (((x+i)<M)&&((y+i)<M))
344 {
345 if (ChessBoard[x+i][y+i]==1)
346 {returnn=0;
347 break;
348 }
349 }
350 if (((x-i)>=0)&&((y+i)<M))
351 {
352 if (ChessBoard[x-i][y+i]==1)
353 {returnn=0;
354 break;}
355 }
356 if (((x+i)<M)&&((y-i)>=0))
357 {if (ChessBoard[x+i][y-i]==1)
358 {returnn=0;
359 break;}
360 }
361 if (((x-i)>=0)&&((y-i)>=0))
362 { if (ChessBoard[x-i][y-i]==1)
363 {returnn=0;
364 break;}
365 }
366 }
367 return returnn;
368 }
369
370 int Elephant(int k)///считаем кличесво фигур
371 {
372 for (int x=0; x<M; x++)
373 {
374 int y;
375 for (y=0; y<M; y++)
376 {
377 if (ChessBoard[x][y]==1)
378 {
379 if (CheckElephant(x,y))
380 {
381 sum=sum+1;
382 }
383 else
384 {
385 sum=0;
386 break;
387 }
388 }
389 }
390 if (y<M)
391 {
392 break;
393 }
394 }
395 return sum;
396 }
397
398 int main ()
399 {
400 ofstream MyFile("MyFile", ios::trunc);
401 MyFile.close(); // очищаем файл, чтоб при новой записи не было из рошлого запуска
402
403 int figure, z;
404 cout<<"enter a figure 1-queen, 2-king, 3-rook , 4-horse or 5-elephant ";
405 cin>>figure;///тип фигуры, 1 - королевА, 2-король,3-ладья,4-конь,6-слон
406 cout << "\n enter a size of a board M - even number ";///ввести ЧЕТНЫЙ размер доски М
407 cin >> M;
408 if ( M%2 != 0)///проверка М на четность, с помощью остатка от деления на 2
409 {
410 while (M%2 != 0)
411 {
412 cout<<" you need EVEN number, enter one more time ";
413 cin>>M;
414 }
415 }
416
417 cout<<"\n choose 1- max amount or 2 - your amount of figures ";
418 cin>>z;///z-один из вариантов 1-максимаьное число фигур на доске,2-пользователь сам вводит
419
420 switch (figure)///выбираем фигуру
421 {
422 case 1:///королева
423 {
424 if (z==2)///пользоватеь сам вводит количество
425 {
426 cout<<"\n enter an amount of figures ";
427 cin >> N;///ввести количество
428 if (N>M)///проверка на то, сможет ли такое количество уместиться на доске в правильном виде
429 {
430 while (N>M)
431 {
432 cout<<" too many figures, enter one more time ";
433 cin>>N;
434 }
435 }
436 ///вот ниже i- те числа которые нужно перевести в двоичную форму
437 for (int i=0; i<=pow(2,(M*M)); i++)///каждый i-новый вариант расстановик фигур
438 {
439 sum=0;
440 int k=i;
441 ChessBoards(k);
442 if (Queen(k)==N)///если в данной варианте фигур столько. сколько ввел пользователь, то выводим
443 {
444 print("MyFile");
445 }
446 }
447 }
448 else ///вариант максимального числа фигур на доске
449 { ///так же как и в предыдущем пункте, только количество фигур N максимально,
450 /// в случае королевы оно равно размеру доски
451 N=M;
452 for (int i=0; i<=pow(2,(M*M)); i++)
453 {
454 sum=0;
455 int k=i;
456 ChessBoards(k);
457 if (Queen(k)==N)
458 {
459 print("MyFile");
460 }
461 }
462 }
463
464 break;
465 }
466 case 2:///то же самое для короля
467 {
468 if (z==2)
469 {
470 cout<<"\n enter an amount of figures ";
471 cin >> N;
472 if ( N>(M*M)/4)
473 {
474 while (N>(M*M)/4)
475 {
476 cout<<" too many figures, enter one more time ";
477 cin>>N;
478 }
479 }
480 for (int i=0; i<=pow(2,(M*M)); i++)
481 {
482 sum=0;
483 int k=i;
484 ChessBoards(k);
485 if (King(k)==N)
486 {
487 print("MyFile");
488 }
489 }
490 }
491 else
492 {
493 N=(M*M)/4;
494 for (int i=0; i<=pow(2,(M*M)); i++)
495 {
496 sum=0;
497 int k=i;
498 ChessBoards(k);
499 if (King(k)==N)
500 {
501 print("MyFile");
502 }
503 }
504 }
505 break;
506 }
507 case 3:///для ладьи
508 {
509 if (z==2)
510 {
511 cout<<"\n enter an amount of figures ";
512 cin >> N;
513 if (N>M)
514 {
515 while (N>M)
516 {
517 cout<<" too many figures, enter one more time ";
518 cin>>N;
519 }
520 }
521
522 for (int i=0; i<=pow(2,(M*M)); i++)
523 {
524 sum=0;
525 int k=i;
526 ChessBoards(k);
527 if (Rook(k)==N)
528 {
529 print("MyFile");
530 }
531 }
532 }
533 else
534 {
535 N=M;
536 for (int i=0; i<=pow(2,(M*M)); i++)
537 {
538 sum=0;
539 int k=i;
540 ChessBoards(k);
541 if (Rook(k)==N)
542 {
543 print("MyFile");
544 }
545 }
546 }
547 break;
548 }
549 case 4:///конь
550 {
551 if (z==2)
552 {
553 cout<<"\n enter an amount of figures ";
554 cin >> N;
555 if (N>(M*M)/2)
556 {
557 while (N>(M*M)/2)
558 {
559 cout<<" too many figures, enter one more time ";
560 cin>>N;
561 }
562 }
563
564 for (int i=0; i<=pow(2,(M*M)); i++)
565 {
566 sum=0;
567 int k=i;
568 ChessBoards(k);
569 if (Horse(k)==N)
570 {
571 print("MyFile");
572 }
573 }
574 }
575 else
576 {
577 N=(M*M)/2;
578 for (int i=0; i<=pow(2,(M*M)); i++)
579 {
580 sum=0;
581 int k=i;
582 ChessBoards(k);
583 if (Horse(k)==N)
584 {
585 print("MyFile");
586 }
587 }
588 }
589 break;
590 }
591 case 5:///слон
592 {
593 if (z==2)
594 {
595 cout<<"\n enter an amount of figures ";
596 cin >> N;
597 if (N>2*M-2)
598 {
599 while (N>2*M-2)
600 {
601 cout<<" too many figures, enter one more time ";
602 cin>>N;
603 }
604 }
605 for (int i=0; i<=pow(2,(M*M)); i++)
606 {
607 sum=0;
608 int k=i;
609 ChessBoards(k);
610 if (Elephant(k)==N)
611 {
612 print("MyFile");
613 }
614 }
615 }
616 else
617 {
618 N=2*M-2;
619 for (int i=0; i<=pow(2,(M*M)); i++)
620 {
621 sum=0;
622 int k=i;
623 ChessBoards(k);
624 if (Elephant(k)==N)
625 {
626 print("MyFile");
627 }
628 }
629 }
630 break;
631 }
632 default : ///а это еси пользоватеь ввел цифру, которая не соответстует ни одной фигуре
633 {
634 cout<<"NOOOOO";
635 break;
636 }
637 };
638
639
640 return 0;
641 }
Краткое описание алгоритма: Для каждой фигуры написана отдельная функция, выполняющая поиск расстановок. После выбора типа фигуры, соответствующая функция выполняет поиск возможных расстановок. Она проходя по строкам двумерного массива пытается поставить фигуру в каждую клетку. Проходя по массиву она маркирует клетки, ставит 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 }
Краткое описание алгоритма: доска представлена в виде динамического массива, при выводе на экран пустые клетки обозначаются точками, а клетки, заполненные фигурами, обозначаются буквами (каждая буква соответствует первой букве названия фигуры на английском языке). Для каждой фигуры написаны функции проверки на возможность установки фигуры и функции расстановки. Кроме того, программа аналитически считает максимальное количество фигур для доски заданного пользователем размера и, при наличии команды пользователя, выводит все возможные расстановки рассчитанного максимального количества фигур на экран.
Инструкция: при запуске программа предлагает пользователю ввести размер доски, при этом число должно быть четным (если же пользователь вводит нечетное число, программа предлагает ввести размер еще раз, и так до тех пор, пока не будет введено четное число). Далее пользователь выбирает режим работы программы - либо расстановка фигур, либо расчет максимального количества фигур. В режиме расстановки фигур программа предлагает выбрать тип фигуры, выводит максимальное число фигур для доски заданного размера и предлагает ввести желаемое число фигур для расстановки (если оно больше максимального, предлагается повторная попытка ввода). В режиме расчета максимального числа программа предлагает выбрать тип фигуры, выводит рассчитанное число и задает вопрос о необходимости вывода всех возможных расстановок максимального количества для данной фигуры. Оба режима работают (т.е. все запросы повторяются) до тех пор, пока пользователь не даст команду на завершение цикла. Кроме того, в программе есть возможность изменения размера доски после выхода из всех циклов. При положительном ответе пользователя и изменении размера доступны оба режима работы.
Скачать можно здесь.
1 #include <iostream> ///расстановка одинаковых шахматных фигур одного цвета на доске произвольного размера так, чтобы они друг друга не били
2 #include <cstring>
3 #include <cstdlib>
4 #include <ctime>
5
6 using namespace std;
7 int result_count = 0; ///переменная, в которую закладывается номер варианта расстановки фигур
8 int N; ///то количество фигур для расстановки, которое задает пользователь
9 int **Board; ///двумерный массив для отображения шахматной доски
10 int M; /// размер шахматной доски
11
12 ///Функция вывода доски
13 void showBoard(string F) ///данная функция отображает доску
14 {
15 for(int i = 0; i < M; ++i) /// цикл, прогоняющий значения по строкам
16 {
17 for(int j = 0; j < M; ++j) /// цикл, прогоняющий значения по столбцам
18 cout << ((Board[i][j]) ? F : "."); ///заполнение как строки, так и столбца символом, который обозначает позицию на шахматной доске
19 cout << endl; ///точка - если данная клетка пустая, буква - если в клетке стоит соответствующая фигура
20 }
21 cout << "Result # " << ++result_count << "\n\n"; ///вывод номера варианта расположения с последующим переходом на новую строку
22 return;
23 }
24
25 ///Функции проверки и установки для ферзя
26
27 bool tryQueen(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец
28 {
29 for (int i = 0; i < M; ++i) ///проверка единственности ферзя в строке
30 {
31 if(Board[a][i])
32 return false;
33 }
34
35 for(int i = 0; i < M; ++i) ///проверка единственности ферзя в столбце
36 {
37 if(Board[i][b])
38 return false;
39 }
40
41 for(int i = 1; a-i >= 0 && b-i >= 0; ++i)///проверка единственности ферзя по диагонали влево-вверх
42 {
43 if(Board[a-i][b-i])
44 return false;
45 }
46
47 for(int i = 1; a+i < M && b+i < M; ++i)///проверка единственности ферзя по диагонали вправо-вниз
48 {
49 if(Board[a+i][b+i])
50 return false;
51 }
52
53 for(int i = 1; a+i < M && b-i >= 0; ++i)///проверка единственности ферзя по диагонали влево-вниз
54 {
55 if(Board[a+i][b-i])
56 return false;
57 }
58
59 for(int i = 1; a-i >= 0 && b+i < M; ++i)///проверка единственности ферзя по диагонали вправо-вверх
60 {
61 if(Board[a-i][b+i])
62 return false;
63 }
64
65 return true; ///если в ходе проверки ферзей и угроз не обнаружилось, в данную клетку можно поставить фигуру
66 }
67
68 void setQueen(int a, int count) ///функция расстановки ферзей; a - очередная строка, count - счетчик количества фигур, которое необходимо расставить
69 {
70 for(int b = 0; b < M; ++b) ///b - очередной столбец, расстановка идет по строкам
71 {
72 if(tryQueen(a, b)) ///проверка данной клетки на возможность установки фигуры
73 {
74 Board[a][b] = 1; ///установка ферзя в первую клетку поля, присваивание ей значения 1 (true)
75
76 for(int i = a + 1; i < M; ++i) ///расстановка указанного пользователем количества фигур
77 setQueen(i,count+1);
78
79 if(count+1 == N) /// если нужное количество фигур поставлено, то
80 showBoard("Q"); /// вызов функции вывода шахматной доски на экран
81
82 Board[a][b]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
83 }
84 }
85 }
86
87 ///Функции проверки и установки для ладьи
88
89 bool tryRook(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец
90 {
91 for (int i = 0; i < M; ++i) ///проверка единственности ладьи в строке
92 {
93 if(Board[a][i])
94 return false;
95 }
96
97 for(int i = 0; i < M; ++i) ///проверка единственности ладьи в столбце
98 {
99 if(Board[i][b])
100 return false;
101 }
102
103 return true; ///если в ходе проверки ладей и угроз не обнаружилось, в данную клетку можно поставить фигуру
104 }
105
106 void setRook(int a, int count) ///функция расстановки ладей; a - очередная строка, count - счетчик количества фигур, которое необходимо расставить
107 {
108 for(int b = 0; b < M; ++b) ///b - очередной столбец, расстановка идет по строкам
109 {
110 if(tryRook(a, b)) ///проверка данной клетки на возможность установки фигуры
111 {
112 Board[a][b] = 1; ///установка ладьи в первую клетку, присваивание ей значения 1 (true)
113
114 for(int i = a + 1; i < M; ++i) ///расстановка указанного пользователем количества фигур
115 setRook(i,count+1);
116
117 if(count+1 == N) /// если нужное количество фигур поставлено, то
118 showBoard("R"); /// вызов функции вывода шахматной доски на экран
119
120 Board[a][b]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
121 }
122 }
123 }
124
125 ///Функции проверки и установки для слона
126
127 bool tryEl(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец
128 {
129 for(int i = 1; a-i >= 0 && b-i >= 0; ++i)///проверка единственности слона по диагонали влево-вверх
130 {
131 if(Board[a-i][b-i])
132 return false;
133 }
134
135 for(int i = 1; a+i < M && b+i < M; ++i)///проверка единственности слона по диагонали вправо-вниз
136 {
137 if(Board[a+i][b+i])
138 return false;
139 }
140
141 for(int i = 1; a+i < M && b-i >= 0; ++i)///проверка единственности слона по диагонали влево-вниз
142 {
143 if(Board[a+i][b-i])
144 return false;
145 }
146
147 for(int i = 1; a-i >= 0 && b+i < M; ++i)///проверка единственности слона по диагонали вправо-вверх
148 {
149 if(Board[a-i][b+i])
150 return false;
151 }
152
153 return true; ///если в ходе проверки слонов и угроз не обнаружилось, в данную клетку можно поставить фигуру
154 }
155 void setEl(int dia, int count) ///функция расстановки слонов; line - очередная строка, count - счетчик количества фигур, которое необходимо расставить
156 {
157 ///dia - очередная диагональ, которую нужно исследовать на наличие фигуры и угрозы
158 int a, b; ///клетка, с которой начинается расстановка, a- очередная строка, b- очередной столбец
159
160 if (dia < M) ///условие, что клеткa данной диагонали лежат на доске
161 {
162 a = dia; ///начало отсчёта диагоналей, цикл движется по строке
163 b = 0; ///обнуление переменной для столбца, цикл движется по столбцу
164 }
165 else ///если клеткa данной диагонали выходит за размер доски (когда цикл по строке доберется до конца
166 {
167 a = M-1; ///самая последняя диагональ
168 b =(dia % M)+1; ///соответственно расчёт переменной для столбца этой диагонали
169 }
170
171 for(int i=0; a-i>=0 && b+i < M; ++i)/// цикл движется по строкам и столбцам снизу слева вправо вверх
172 {
173 int line = a-i; ///строковая координата данной клетки диагонали
174 int column = b+i; ///столбцовая координата данной клетки диагонали
175
176 if(tryEl(line, column))/// проверка на единственность слона по диагоналям
177 {
178 Board[line][column]=1; ///установка слона в первую клетку, присваивание ей значения 1 (true)
179
180 for(int i = dia + 1; i<2*M-1; ++i) ///расстановка указанного пользователем количества фигур
181 setEl(i,count+1);
182
183 if(count+1 == N) /// если нужное количество фигур поставлено, то
184 showBoard("E"); /// вызов функции вывода шахматной доски на экран
185
186 Board[line][column]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
187 }
188 }
189 }
190
191 ///Функции проверки и установки для коня
192
193 bool tryHorse(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец
194 {
195 ///проверка на наличие фигур и угроз во всех 8 точках, которые могут быть под ударом в квадрате 5х5 вокруг установленной фигуры
196
197 if ((a-1) >=0 && (b-2)>=0 && Board[a-1][b-2])
198 return false;
199
200 if ((a-1)>=0 && (b+2) < M && Board[a-1][b+2])
201 return false;
202
203 if ((a+1) < M && (b-2) >=0 && Board[a+1][b-2])
204 return false;
205
206 if ((a+1) < M && (b+2) < M && Board[a+1][b+2])
207 return false;
208
209 if ((a-2) >=0 && (b-1) >=0 && Board[a-2][b-1])
210 return false;
211
212 if ((a-2) >=0 && (b+1) < M && Board[a-2][b+1])
213 return false;
214
215 if ((a+2) < M && (b-1) >= 0 && Board[a+2][b-1])
216 return false;
217
218 if ((a+2) < M && (b+1) < M && Board[a+2][b+1])
219 return false;
220
221 return true; ///если в ходе проверки коней и угроз не обнаружилось, в данную клетку можно поставить фигуру
222 }
223
224 void setHorse(int count, int a, int b) ///функция расстановки коней; a - очередная строка, b - очередной столбец, count - счетчик количества фигур, которое необходимо расставить
225 {
226 if(count==N) /// если нужное количество фигур поставлено, то
227 {
228 showBoard("H"); /// вызов функции вывода шахматной доски на экран
229 }
230
231 if (a == M) ///условие необходимо; прогоняет алгоритм по всем строкам
232 return;
233
234 for (int j=b; j<M; ++j) ///установка коней в первой строке
235 {
236 if(tryHorse(a, j)) ///проверка данной клетки на возможность установки фигуры
237 {
238 Board[a][j]=1; ///установка коня в первую клетку, присваивание ей значения 1 (true)
239 int line = a, b = j+1; ///смещение в строке на одну позицию вправо, переобозначение строки на line
240
241 if (b == M) ///если данный столбец - самый крайний
242 {
243 b = 0; ///обнуление переменной, чтобы использовать ее при заполнении следующей строки
244 line++; ///то переход на следующую строку и дальнейшее ее заполнение
245 }
246 setHorse(count+1,line,b); ///установка фигуры, увеличение счетчика
247 Board[a][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
248 }
249 }
250
251 for(int i=a+1; i<M; ++i) ///дальнейшее заполнение оставшихся строк
252 {
253 for (int j=0; j<M; ++j)
254 {
255 if(tryHorse(i, j)) ///проверка данной клетки на возможность установки фигуры
256 {
257 Board[i][j]=1; ///установка коня в первую клетку, присваивание ей значения 1 (true)
258 int line = i, b = j+1; ///смещение в строке на одну позицию вправо
259
260 if (b == M) ///если данный столбец - самый крайний
261 {
262 b = 0;
263 line++; ///то переход на следующую строку и дальнейшее ее заполнение
264 }
265 setHorse(count+1,line,b); ///установка фигуры, увеличение счетчика
266 Board[i][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
267 }
268 }
269 }
270 }
271
272 ///для короля
273
274 bool tryKing(int a, int b) /// проверка на возможность поставить фигуру в квадрате 3х3, a- очередная строка, b- очередной столбец
275 {
276 ///проверка на наличие фигур и угроз во всех 8 точках, которые могут быть под ударом в квадрате 3х3 вокруг установленной фигуры
277
278 for(int i = a-1; i <= a+1; ++i) ///проверка по строкам
279 {
280 for(int j = b-1; j <= b+1; ++j) ///проверка по столбцам
281 {
282 if (a>=0 && a < M && b>=0 && b < M && Board[a][b]) ///условие наличия клетки в пределах доски
283 return false;
284
285 if ((a+1) < M && (b-1) >=0 && Board[a+1][b-1])
286 return false;
287
288 if ((a+1) < M && Board[a+1][b])
289 return false;
290
291 if ((a+1) < M && (b+1) < M && Board[a+1][b+1])
292 return false;
293
294 if ((b+1) < M && Board[a][b+1])
295 return false;
296
297 if ((a-1)>=0 && (b+1) < M && Board[a-1][b+1])
298 return false;
299
300 if ((a-1) >=0 && Board[a-1][b])
301 return false;
302
303 if ((a-1) >=0 && (b-1)>=0 && Board[a-1][b-1])
304 return false;
305
306 if ((b-1) >= 0 && Board[a][b-1])
307 return false;
308 }
309 }
310
311 return true; ///если в ходе проверки королей и угроз не обнаружилось, в данную клетку можно поставить фигуру
312 }
313
314 void setKing (int count, int a, int b) ///функция расстановки коней; a - очередная строка, b - очередной столбец, count - счетчик количества фигур, которое необходимо расставить
315 {
316 for (int j=b; j<M; ++j) ///установка королей в первой строке
317 {
318 if(tryKing(a, j)) ///проверка данной клетки на возможность установки фигуры
319 {
320 Board[a][j]=1; ///проверка данной клетки на возможность установки фигуры
321 setKing(count+1,a,j); ///расстановка фигур в первой строке
322 Board[a][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
323 }
324 }
325
326 for(int i=a+1; i<M; ++i) ///установка фигур в оставшуюся часть шахматной доски по строкам
327 {
328 for (int j=0; j<M; ++j)
329 {
330 if(tryKing(i, j)) ///проверка данной клетки на возможность установки фигуры
331 {
332 Board[i][j]=1; ///проверка данной клетки на возможность установки фигуры
333 setKing(count+1,i,j); ///расстановка фигур
334 Board[i][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
335 }
336 }
337 }
338
339 if(count==N) /// если нужное количество фигур поставлено, то
340 {
341 showBoard("K");/// вызов функции вывода шахматной доски на экран
342 return;
343 }
344 }
345
346 int main()
347 {
348 char s; ///переменная, будет использована в цикле
349 do /// цикл, выводящий на экран данные в зависимости от введенных пользователем значений переменных
350 {
351 do ///цикл для считывания введенного пользователем размера доски
352 {
353 cout << "Input the size of the board: " << endl; ///ввод размера доски
354 cin >> M;
355
356 if ( (M%2) == 1) ///цикл, работающий только в том случае, если пользователь введет нечетное число
357 {
358 cout << '\n' << "The number must be even, so try to input the size again" << '\n' << endl;
359 }
360
361 }
362 while (M%2 !=0); ///пока пользователь не введет допуcтимое число, цикл не прерывается
363
364 Board = new int*[M]; ///создание двумерного массива для отображения шахматной доски
365 for (int i = 0; i<M; i++)
366 Board[i] = new int[M]; ///создание первую строку доски
367 for (int i = 0; i<M; i++)
368 for (int j = 0; j<M; j++)
369 Board[i][j] = 0; ///зануление массива
370
371 int V; ///пользователь выбирает один из двух вариантов работы программы
372 cout << '\n' << "Input your choice: 1=placing of figures, 2=for max amount of figures" << endl;
373 cin >> V;
374
375 if (V==1) ///цикл, расставляющий фигуры по введенным пользователем данным
376 {
377 char k; ///переменная, будет использована в цикле
378 do /// цикл, выводящий на экран данные в зависимости от введенных пользователем значений переменных
379 {
380 int T; ///пользователь выбирает фигуру
381 cout << '\n' << "Input type of figure: 1-queen, 2-king, 3-horse, 4-rook, 5-elephant"<< endl;
382 cin >> T;
383
384 int maximum; ///переменная, хранящая максимальное количество фигур, которое можно расставить на заданной доске
385 if (T==1) ///максимальное количество фигур на заданной доске для ферзя
386 {
387 maximum=M;
388 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
389 }
390 if (T==2) ///максимальное количество фигур на заданной доске для короля
391 {
392 maximum=0.25*M*M;
393 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
394 }
395 if (T==3) ///максимальное количество фигур на заданной доске для коня
396 {
397 maximum=0.5*M*M;
398 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
399 }
400 if (T==4) ///максимальное количество фигур на заданной доске для ладьи
401 {
402 maximum=M;
403 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
404 }
405 if (T==5) ///максимальное количество фигур на заданной доске для слона
406 {
407 maximum=2*M-2;
408 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
409 }
410
411 do ///цикл, считывающий количество фигур, заданное пользователем
412 {
413 cout << "Input the amount of figures, it must be less than max amount or equals that" << endl;
414 cin >> N;
415 }
416 while (N>maximum); ///пока пользователь не введет допуcтимое число, цикл не прерывается
417
418 cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl;
419
420 if (T==1) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для ферзя
421 {
422 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
423 for (int i=0; i <M; ++i)
424 setQueen(i,0);
425 }
426 if (T==2) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для короля
427 {
428 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
429 setKing(0,0,0);
430 }
431 if (T==3) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для коня
432 {
433 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
434 setHorse(0,0,0);
435 }
436 if (T==4) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для ладьи
437 {
438 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
439 for (int i=0; i <M; ++i)
440 setRook(i,0);
441 }
442 if (T==5) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для слона
443 {
444 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
445 for(int i = 0; i<2*M-1; ++i)
446 setEl(i,0);
447 }
448
449 cout << '\n' << "If you want continue placing figures, input +, if not, input -" << endl;
450 cin >> k;
451 }
452 while (k != '-'); ///цикл работает до тех пор, пока пользователь не даст команду на его завершение
453 }
454
455 else if (V==2) ///цикл, вычисляющий максимальное количество фигур по введенным пользователем данным
456 {
457 char z; ///переменная, будет использована в цикле
458 do /// цикл, выводящий на экран данные в зависимости от введенных пользователем значений переменных
459 {
460 int T; ///переменная для выбора фигуры пользователем
461 cout << '\n' << "Input type of figure: 1-queen, 2-king, 3-horse, 4-rook, 5-elephant"<< endl;
462 cin >> T;
463 char d; ///переменная, будет использована в циклах
464 int maximum; ///переменная, хранящая максимальное количество фигур, которое можно расставить на заданной доске
465 if (T==1) ///максимальное количество фигур на заданной доске для ферзя
466 {
467 maximum=M; ///формула расчёта максимального количества фигур для заданной доски
468 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
469 cout << "If you want to see all locations of max amount, input +, if not, input -" << endl;
470 cin >> d;
471 cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl;
472 if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры
473 {
474 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
475 N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
476 for (int i=0; i < M; ++i)
477 setQueen(i,0);
478 }
479
480 }
481 if (T==2) ///максимальное количество фигур на заданной доске для короля
482 {
483 maximum=0.25*M*M; ///формула расчёта максимального количества фигур для заданной доски
484 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
485 cout << "If you want to see all locations of max amount, input +, if not, input -" << endl;
486 cin >> d;
487 cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl;
488 if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры
489 {
490 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
491 N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
492 setKing(0,0,0);
493 }
494 }
495 if (T==3) ///максимальное количество фигур на заданной доске для коня
496 {
497 maximum=0.5*M*M; ///формула расчёта максимального количества фигур для заданной доски
498 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
499 cout << "If you want to see all locations of max amount, input +, if not, input -" << endl;
500 cin >> d;
501 cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl;
502 if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры
503 {
504 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
505 N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
506 setHorse(0,0,0);
507 }
508 }
509 if (T==4) ///максимальное количество фигур на заданной доске для ладьи
510 {
511 maximum=M; ///формула расчёта максимального количества фигур для заданной доски
512 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
513 cout << "If you want to see all locations of max amount, input +, if not, input -" << endl;
514 cin >> d;
515 cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl;
516 if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры
517 {
518 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
519 N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
520 for (int i=0; i <M; ++i)
521 setRook(i,0);
522 }
523 }
524 if (T==5) ///максимальное количество фигур на заданной доске для слона
525 {
526 maximum=2*M-2; ///формула расчёта максимального количества фигур для заданной доски
527 cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl;
528 cout << "If you want to see all locations of max amount, input +, if not, input -" << endl;
529 cin >> d;
530 cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl;
531 if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры
532 {
533 result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла
534 N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
535 for(int i = 0; i<2*M-1; ++i)
536 setEl(i,0);
537 }
538 }
539
540 cout << '\n' << "If you want continue counting, input +, if not, input -" << '\n' << endl;
541 cin >> z;
542 }
543 while (z != '-'); ///цикл работает до тех пор, пока пользователь не даст команду на его завершение
544 }
545 cout << '\n' << "If you want to change the size of board, input +, if not, input -" << endl;
546 cin >> s;
547 if (s=='-')
548 {
549 cout << '\n' << "The program is finished." << '\n' << endl; ///вывод на экран сообщения о завершении работы программы
550 }
551 }
552 while (s != '-'); ///цикл работает до тех пор, пока пользователь не даст команду на его завершение, а также на завершение всей программы
553 }
Программа работает в двух режимах: поиск максимального числа фигур для заданного поля и количество возможных расстановок заданного числа фигур для заданного поля.
Алгоритм:
- Для поиска количества возможных расстановок заданного числа фигур для заданного поля – Проверяется, возможно ли поставить фигуру в данную клетку, рекурсивно перебирает для каждой клетки поля, как начальной клетки, все варианты расстановки заданного количества фигур относительно нее и выводит на экран все расстановки, которые подходят условиям.
- Для поиска максимального числа фигур для заданного поля – Проверяется, можно ли поставить одну фигуру, две, три и так далее, пока фигур больше поставить будет нельзя.
Скачать можно тут.
1 #include <vector>
2 #include <iostream>
3 #include <algorithm>
4
5
6 using namespace std;
7
8 int n,k, o, m, l, g, maxi, a, sum=0,y, mozno=1;//mozno=1 если можно поставить n фигур
9 vector<vector<int> > matrix;// двухмерный вектор
10
11 bool ladia(int x, int y) { //проверка, можно ли в эту клетку поставить ладью
12 for(int i = 0; i<n; i++)
13 if(matrix[x][i] == 1)
14 return false;
15 for(int j=0; j<n; j++)
16 if(matrix[j][y]==1)
17 return false;
18 return true;
19 }
20
21 bool slon(int x, int y) { // --//-- слона
22
23 for (int i=x, j=y;i<n && j>=0; i++, j--)
24 if(matrix[i][j] == 1)
25 return false;
26 for (int i=x, j=y;i>=0 && j>=0; i--, j--)
27 if(matrix[i][j] == 1)
28 return false;
29 for (int i=x, j=y;i>=0 && j<n; i--, j++)
30 if(matrix[i][j] == 1)
31 return false;
32 for (int i=x, j=y;i<n && j<n; i++, j++)
33 if(matrix[i][j] == 1)
34 return false;
35
36 return true;
37
38 }
39
40 bool fruz(int x, int y){ // --//-- ферзя
41 if(slon(x,y) && ladia(x,y))
42 return true;
43
44 return false;
45
46
47 }
48
49 bool kon(int x, int y) { // --//-- коня
50
51 if (x-1>=0 && y-2>=0 && matrix[x-1][y-2]==1)
52 return false;
53 if (y-2>=0 && x+1<n && matrix[x+1][y-2]==1)
54 return false;
55 if (x-2>=0 && y-1>=0 && matrix[x-2][y-1]==1)
56 return false;
57 if (x+2<n && y-1>=0 && matrix[x+2][y-1]==1)
58 return false;
59 if (x-2>=0 && y+1<n && matrix[x-2][y+1]==1)
60 return false;
61 if (x+2<n && y+1<n && matrix[x+2][y+1]==1)
62 return false;
63 if (x-1>=0 && y+2<n && matrix[x-1][y+2]==1)
64 return false;
65 if (x+1<n && y+2<n && matrix[x+1][y+2]==1)
66 return false;
67 return true;
68 }
69
70 bool king(int x, int y) { // --//-- короля
71
72 if (x-1>=0 && y-1>=0 && matrix[x-1][y-1]==1)
73 return false;
74 if (x-1>=0 && matrix[x-1][y]==1)
75 return false;
76 if (y+1<n && x-1>=0 && matrix[x-1][y+1]==1)
77 return false;
78 if (y+1<n && matrix[x][y+1]==1)
79 return false;
80 if (y+1<n && x+1>n && matrix[x+1][y+1]==1)
81 return false;
82 if (x+1<n && matrix[x+1][y]==1)
83 return false;
84 if (x+1<n && y-1>=0 && matrix[x+1][y-1]==1)
85 return false;
86 if (y-1>=0 && matrix[x][y-1]==1)
87 return false;
88 return true;
89
90 }
91
92 int mass() { // вывод доски на экран
93
94 for(int i = 0; i<n; i++)
95 {
96
97 for(int j = 0; j<n; j++)
98 cout<<matrix[i][j]<<" ";
99
100 cout<<endl;
101 }
102
103 }
104
105 int del() { // очистка доски(все нули)
106
107 for (int i=0; i<n; i++) {
108
109 for (int j=0; j<n; j++)
110 matrix[i][j]=0;
111 }
112
113 }
114
115
116
117 void vsevarintyrasstavitnfigur(int x,int y){ // рекурсивный поиск всех вараинтов расстановок заданнного количества фигур (x - номер фигуры в доске, если ее растянуть в линию, y - кол-во фигур)
118 if(y==0) {
119 if (a==1){
120 mass();
121 cout<<'\n';
122 }
123 if(a==2) {
124 mozno = 1; //mozno=1 если можно поставить n фигур
125
126 }
127
128 return;
129 }
130
131 for(int i=x;i<n*n;i++){
132
133 if (o==1)
134 if(fruz(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
135
136 if (o==2)
137 if(ladia(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
138
139 if (o==3)
140 if(slon(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
141
142 if (o==4)
143 if(kon(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
144
145 if (o==5)
146 if(king(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
147
148
149 vsevarintyrasstavitnfigur(i+1, y);
150 matrix[i/n][i%n]=0;//удаление фигуры из прошлой клетки для проверки других вариантов
151 y++;
152
153 }
154
155 }
156
157 void maxfig(){ //поиск максимального количества фигур
158 int i=0;
159 while(mozno==1){ //проверяет для данной доски возможность расставить 1,2... фигуры, пока не доходит до количества, которое расставить невозхможно. Тогда это количество фигур -1 - искомая величина
160 i++;
161 mozno=0;
162 vsevarintyrasstavitnfigur(0,i);
163 }
164 setlocale(LC_ALL, "Russian");
165 cout<<"Максимальное количество фигур = "<<i-1<<endl;
166 }
167
168
169 int main() {
170 setlocale(LC_ALL, "Russian");
171 g=0;
172 cout<<"Введите размер доски:"<<endl;
173 cin >>n;
174 for(int i=0; i<n; i++) {
175 vector<int> z;
176 for(int j=0; j<n; j++){
177 z.push_back(0); //создание вектора z из n нулей и добавление его к двухмерному вектору
178 }
179 matrix.push_back(z);
180 }
181
182 cout<<"1 - расстановки фигур на доске n*n"<<endl<<"2 - максимум фигур на доске n*n"<<endl;
183 cin>>a;
184
185 while(2>1){
186 cout<<" 1 - ферзь"<<endl;
187 cout<<" 2 - ладья"<<endl;
188 cout<<" 3 - слон"<<endl;
189 cout<<" 4 - конь"<<endl;
190 cout<<" 5 - король"<<endl;
191 cout<<" 6 - выход"<<endl;
192
193 cout<<"Введите число от 1 до 6:"<<endl;
194 cin>>o;
195 mozno=1;
196 if(o==6) break;
197
198
199
200
201
202
203 if (o==1) {
204 cout<<"Ферзь"<<endl;
205
206 if(a==1)
207 {
208 cin>>y;
209 vsevarintyrasstavitnfigur(0,y);
210 }
211
212
213 if (a==2)
214 maxfig();
215
216 }
217
218
219
220
221
222
223 if (o==2) {
224 cout<<endl<<"Ладья"<<endl;
225
226 if(a==1)
227 {
228
229 cin>>y;
230 vsevarintyrasstavitnfigur(0,y);
231 }
232
233 if (a==2)
234 maxfig();
235
236 }
237
238
239 if (o==3) {
240 cout<<endl<<"Слон"<<endl;
241
242 if(a==1)
243 {
244 cin>>y;
245 vsevarintyrasstavitnfigur(0,y);
246 }
247
248 if (a==2)
249 maxfig();
250
251 }
252
253
254 if (o==4) {
255 cout<<endl<<"Конь"<<endl;
256
257 if(a==1)
258 {
259 cin>>y;
260 vsevarintyrasstavitnfigur(0,y);
261 }
262 if (a==2)
263 maxfig();
264
265 }
266
267 if (o==5) {
268 cout<<"Король"<<endl;
269
270 if(a==1)
271 {
272 cin>>y;
273 vsevarintyrasstavitnfigur(0,y);
274
275 }
276 if (a==2)
277
278 maxfig();
279
280 }
281
282 }
283
284
285
286 }
Краткое описание алгоритма : Доска представлена в виде динамического массива;Для каждой фигуры написана отдельная функция проверки на возможность установки фигуры,проверяющая, находится ли эта фигура под ударом других. После выбора типа фигуры,используется рекурсивная функция,которая проверяет возможные расстановки через данную функцию проверки ,для данного типа фигуры. Для поиска максимального значения мы проверяем расстановку начиная с 0 количество фигур ,каждый раз увеличивая на 1,если количество расстановок станет равно нулю,то предыдущее количество фигур было максимальным.
Инструкция : Пользователя попросят ввести размер доски,затем выбрать один из вариантов работы программы:1.поиск возможных расстановок для M фигур или 2.поиск максимального количества расстановок для данного поля,затем попросят выбрать тип фигуры и в первом случае количество фигур.При выводе на экран выводится номер расстановки и доска,на доске F- обозначены занятые клетки,0-пуская клетка. Для 2 пункта выводится лишь число: максимальное количество фигур,которое можно расставить.
Скачать можно : тут
1 #include<iostream>
2 using namespace std;
3 int N;//размер доски NxN
4 int **a;
5 int *ax;
6 int *by;
7 int l = 0;//L-номер пункта в меню
8 int M;//количество фигур
9 bool isPrint = false;//переменная для вывода на экран,когда требуется,для удобства обозначим в начале false
10
11
12 void print()//функция вывода на экран
13 {
14 for (int i = N - 1; i >= 0; --i)
15 {
16 for (int j = 0; j < N; ++j)
17 {
18 cout << ((a[j][i]) ? "F " : "0 ");//если (a[j][i]) истина,то есть клетка занята,ставим F,в другом случае,т.е.свободна,ставим 0
19 }
20 cout << '\n';
21 }
22 cout << '\n';
23
24 }
25 bool Lad(int x, int y)//Ладья
26 {
27 for (int i = 0; i < N; ++i)
28 {
29 if (a[i][y] == 1 )//проверяем горизонталь:если клетка занята
30 {
31 return false;//возвращаем false
32 }
33 if (a[x][i] == 1)//проверяем вертикаль : если хотя бы одна клетка занята,то
34 {
35 return false;//возврашаем false
36 }
37 }
38 return true;//ничего выше не выполняется,значит возвращаем правду:вертикаль и горизонталь свободна
39
40 }
41
42 bool Kon(int x, int y)//Коняша
43 {
44 int i[8] = {-2, -2, -1, -1, 1, 1, 2, 2};//координаты клеток,на которые может ходить конь,относительно текущей (8 вариантов)
45 int j[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
46
47 for (int k = 0; k < 8; k++)//8 вариантов хода
48
49 {
50 if (x + i[k] >= 0 && x + i[k] < N && y + j[k] >= 0 && y + j[k] < N)//проверка выхода за границы массива
51 {
52 if (a[x + i[k]][y + j[k]] != 0)//клетка занята
53 {
54 return false;//возвращем false
55 }
56 }
57 }
58 return true;////ничего выше не выполняется,значит возвращаем правду:все варианты ходов свободны и конь никого не перебивает,тогда можно занять клетку
59
60 }
61
62
63
64
65 bool Korol(int x, int y)//Король
66 {
67
68 int i[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };//координаты клеток,на которые может ходить король,относительно текущей
69 int j[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
70
71 for(int k = 0; k < 8; k++)//8 вариантов хода
72 {
73 if (x + i[k] >= 0 && x + i[k] < N && y + j[k] >= 0 && y + j[k] < N)//прроверяем не выходит ли фигура за границы массива
74 {
75 if (a[x + i[k]][y + j[k]] != 0)//если какой нибудь из вариантов хода занят
76 {
77 return false;//то false
78 }
79 }
80 }
81 return true;//свободно,можно занимать
82 }
83
84 bool Slon(int x, int y)
85 {
86 int p1 = y - x;//номер диагонали слева направо
87 int p2 = y + x;//номер диагонали с права налево
88 for (int i = 0; i < N; i++)//проверяем левую диагональ
89 {
90 if (i + p1 >= 0 && i + p1 < N)//проверка на выход за границы массива
91 {
92 if (a[i][i + p1] == 1) //проверяем диагональ
93 {
94 return false;//диагональ занята
95 }
96 }
97 if (-i + p2 >= 0 && -i + p2 < N)//вторая диагональ
98 {
99 if (a[i][-i + p2] == 1)
100 {
101 return false;//вторая диагональ занята
102 }
103 }
104 }
105 return true;//обе диагонали свободны,ура!
106 }
107
108 bool Check(int x, int y)//Ферзь=Ладья+Слон
109 {
110 int p1 = y - x;//диагональ 1
111 int p2 = y + x;//диагональ 2
112 for (int i = 0; i < N; ++i)
113 {
114 if (a[i][y] == 1 )//проверяем горизонталь
115 {
116 return false;//занято
117 }
118 if (a[x][i] == 1)//проверяем вертикаль
119 {
120 return false;//занято
121 }
122
123 if (i + p1 >= 0 && i + p1 < N)//выход за границы массива
124 {
125 if (a[i][i + p1] == 1) //проверяем 1 диагональ
126 {
127 return false;//занято
128 }
129 }
130 if (-i + p2 >= 0 && -i + p2 < N)//выход за границы массива
131 {
132 if (a[i][-i + p2] == 1)//проверяем 2ую диагональ
133 {
134 return false;//занято
135 }
136 }
137 }
138 return true;//свободно!
139 }
140
141 int menu1()
142 {
143 cout << "Type of figure:" << endl << "1 - Ferz" << endl << "2 - Ladya" << endl << "3 - Slon" << endl << "4 - Kon" << endl << "5 - Korol" << endl;
144 cin >> l;
145 return l;
146 }
147
148 int num = 0;//номер расстановки
149 //пробует найти результаты решений.
150
151 void Func(int d,int K) //d-глубина рекурсии;K-сколько фигур нужно расставить
152 {
153 if (d == K)//когда расставили нужное количество
154 {
155 if (isPrint)//если true,то печатаем(в случае с MAX количеством доску печатать не нужно)
156 {
157 cout << "Result: " << num + 1 << '\n';//выводим нормер расстановки
158 print();//печатаем доску
159 }
160 num++;//номер расстановки увеличивается
161 return;
162 }
163
164 int minX = d != 0 ? ax[d - 1] : 0;//исходя из того куда быда поставлена предыдущая фигура
165 //,накладываются ограничения для выбора места новой,чтобы избежать поторений
166 int minY = d != 0 ? by[d - 1] + 1 : 0;
167
168
169 bool isPossible = false;//Проверяет,возможно ли занять клетку
170 for (int i = minX; i < N; ++i)
171 {
172
173 for (int j = (i != minX) ? 0 : minY; j < N; ++j)
174 {
175 switch (l)//l- номер пункта в меню с фигурами
176 {
177 case 1://ферзь
178 isPossible = Check(i, j);
179 break;
180 case 2://Ладья
181 isPossible = Lad(i, j);
182 break;
183 case 3://Слон
184
185 isPossible = Slon(i, j);
186 break;
187 case 4://Конь
188 isPossible = Kon(i, j);
189 break;
190 case 5://Король
191 isPossible = Korol(i, j);
192 break;
193 }
194 if (isPossible)//если клетку занять возмоно(функция вернула true)
195 {
196 a[i][j] = 1;//занимаем клетку
197 ax[d] = i;//запоминаем куда была поставлена фигура
198 by[d] = j;//запоминаем куда была поставлена фигура
199 Func(d + 1, K);//вызываем рекурсивно
200 a[i][j] = 0;
201 }
202 }
203 }
204
205 return;
206 }
207
208 int main()
209 {
210
211 cout << "Enter size: ";//нужно ввести размер доски
212 cin >> N;//считываем размер доски
213
214 a = new int*[N];//создаём двумерный массив,т.е.нашу доску
215 for (int i = 0; i < N; i++)
216 {
217 a[i] = new int[N];
218 for (int j = 0; j < N; j++)
219 a[i][j] = 0;//заполняем нулями
220 }
221
222 ax = new int[N];//массивы для сохранения координаты каждой фигуры,чтобы избежать повторений
223 by = new int[N];
224
225 int d;//пункт в меню
226 cout<<"1 - Rasstanovka figur"<<endl<<"2 - MAX znachenie"<<endl;//два варианта работы программы
227 cin>>d;//считываем выбор пользователя
228 if(d==1)//если выбирает расстановку
229 {
230 menu1();//то спрашиваем для какой фигуры
231 cout<<"How many figures?"<<endl;//и как много будет фигур
232 cin>>M;//считываем количество фигур
233 isPrint = true;//в этом случае будем выводить на экран
234 Func(0,M);//запуск рекурсивной функции
235 }
236
237 if (d == 2)//случай подсчёта максимального значения
238 {
239 int n = 0;//изачально max=0
240 menu1();//выбираем фигуру
241
242 do//начало цикла
243 {
244 num = 0;
245 Func(0, ++n);//запускаем каждый раз увеличивая значение фигур и считаем количество расстановок
246 } while (num != 0);//количество вариантов не должно быть равно нулю
247 cout <<"MAX ="<< n - 1 << endl;//если количество вариантов = 0,то выходим из цикла и предыдущее значение максимальное
248 }
249
250
251 int z;
252 cin >> z;
253
254 return 0;
255 }
Программа: 1)Программа получает все возможные варианты расстановок одинаковых фигур на поле боя(шахматной доске) так, чтобы они не смогли бить друг друга.2)Программа выводит максимальное число фигур, которые можно поставить на шахматную доску nxn так, чтобы они не смогли бить друг друга.
Идея алгоритма: Функция вызывает саму себя(рекурсия) в рекурсии фигура ставится на небьющуюся клетку и помечаются клетки, которые бьются этой фигурой.Если дальше ставить нельзя, то начинается обратный ход:фигура убирается, и запоминается место, где она стояла, и вновь вызывается функция.
Скачать можно тут.
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6
7
8 //задаю массивы в которых изображены все ходы определенных фигур
9 int d = 0;
10 int d_knight[2][8] = {{1, 1, -1, -1, 2, 2, -2, -2},
11 {2, -2, 2, -2, 1, -1, 1, -1}};
12 int d_bish[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
13 int d_king[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
14 //Проверяем, не выходим ли мы за поле
15 bool ok(int x, int y, int n) {
16 if (x < 0 || y < 0 || x >= n || y >= n)
17 return false;
18 return true;
19 }
20
21 void print(int n, vector<vector<pair<bool, int> > > board) {
22 for (int i = 0; i < n; i++) {
23 for (int j = 0; j < n; j++) {
24 cout << ((board[i][j].first) ? " X " : " 0 ");
25 }
26 cout << '\n';
27 }
28 cout << "-------------------------------------\n";
29 }
30 //Рекурсивная функция
31 int func(int n, int k, int count, vector<vector<pair<bool, int> > > board, int ii, int jj, int fig, int task) {
32 int ans = 0;
33 if (count == k && !task) {
34 print(n, board);
35 return 1;
36 }
37 else if(task) {
38 ans = max(ans, count);
39 }
40 for (int i = ii + jj / n; i < n; i++) {
41 for (int j = jj % n; j < n; j++) {
42 if (!board[i][j].first && !board[i][j].second) {
43 switch (fig) {
44 case 1://конь
45 for (int k = 0; k < 8; k++) {
46 if (ok(i + d_knight[0][k], j + d_knight[1][k], n))
47 board[i + d_knight[0][k]][j + d_knight[1][k]].second++;
48 }
49 break;
50 case 2://слон
51 for (int k = 0; k < n; k++) {
52 for (int l = 0; l < 4; l++) {
53 if (ok(i + k * d_bish[l][0], j + k * d_bish[l][1], n))
54 board[i + k * d_bish[l][0]][j + k * d_bish[l][1]].second++;
55 }
56 }
57 break;
58 case 3: // ладья
59 for (int k = 0; k < n; k++)
60 board[i][k].second++, board[k][j].second++;
61 break;
62 case 4: // король
63 for (int k = 0; k < 8; k++)
64 if (ok(i + d_king[k][0], j + d_king[k][1], n))
65 board[i + d_king[k][0]][j + d_king[k][1]].second++;
66 break;
67 case 5: // ферзь
68 for (int k = 0; k < 8; k++)
69 for (int l = 0; l < n; l++)
70 if (ok(i + l * d_king[k][0], j + l * d_king[k][1], n))
71 board[i + l * d_king[k][0]][j + l * d_king[k][1]].second++;
72 break;
73
74 }
75 //Рекурсия
76 board[i][j].first = true;
77 if (!task)
78 ans += func(n, k, count + 1, board, i, j + 1, fig, task);
79 //обратный ход
80 else
81 ans = max(ans, func(n, k, count + 1, board, i, j + 1, fig, task));
82 board[i][j].first = false;
83 switch (fig) {
84 case 1:
85 for (int k = 0; k < 8; k++) {
86 if (ok(i + d_knight[0][k], j + d_knight[1][k], n))
87 board[i + d_knight[0][k]][j + d_knight[1][k]].second--;
88 }
89 break;
90 case 2:
91 for (int k = 0; k < n; k++) {
92 for (int l = 0; l < 4; l++) {
93 if (ok(i + k * d_bish[l][0], j + k * d_bish[l][1], n))
94 board[i + k * d_bish[l][0]][j + k * d_bish[l][1]].second--;
95 }
96 }
97 break;
98 case 3:
99 for (int k = 0; k < n; k++)
100 board[i][k].second--, board[k][j].second--;
101 break;
102 case 4:
103 for (int k = 0; k < 8; k++)
104 if (ok(i + d_king[k][0], j + d_king[k][1], n))
105 board[i + d_king[k][0]][j + d_king[k][1]].second--;
106 break;
107 case 5:
108 for (int k = 0; k < 8; k++)
109 for (int l = 0; l < n; l++)
110 if (ok(i + l * d_king[k][0], j + l * d_king[k][1], n))
111 board[i + l * d_king[k][0]][j + l * d_king[k][1]].second--;
112 break;
113 }
114 }
115 }
116 jj = 0;
117 }
118 return ans;
119 }
120 //меню
121 int main() {
122 int fig, task;
123 int n, k;
124 cout << "Please, input the task number: 1 - amount of solutions, 2 - maximum of figures\n";
125 cin >> task;
126 task--;
127 cout << "Please, input figure type: 1 - knight, 2 - bishop, 3 - castle, 4 - king, 5 - queen\n";
128 cin >> fig;
129 cout << "Please, input the size of the board\n";
130 cin >> n;
131 if (!task) {
132 cout << "Please, input number of figures\n";
133 cin >> k;
134 }
135 vector<vector<pair<bool, int> > > v = vector<vector<pair<bool, int> > >(n, vector <pair<bool, int> >(n, {false, 0}));
136 cout << func(n, k, 0, v, 0, 0, fig, task);
137 }
Описание алгоритма:
Программа проверяет возможность расстановки фигур на доске M*M . При выводе на экран на экран клетки,занятые фигурами ,помечаются буквами,соответствующими первой букве типа фигуры. Также программа считает максимальное число фигур определенного типа,которые можно расставить на доске.
Инструкция В окне консоли пользователю предлагается выбрать 2 типа работы программы, затем пользователь вводит размер доски(четный),тип и количество фигур,которые необходимо разместить на доске.В зависимости от режима работы программы ,будет выведено либо максимально возможное число расстановок фигур,либо максимальное число фигур. Скачать можно тут [[1]]
