Информатика: Расстановка шахматных фигур
Материал из Department of Theoretical and Applied Mechanics
Алгоритм: в зависимости от выбранного режима работы, после ввода пользователем необходимой информации о размере поля а также типе расставляемых фигур, запускается основная рекурсивная функция, которая либо подсчитывает все возможные расстановки для заданного числа фигур и выводит их в файл, либо рассчитывает максимально возможное расставляемое число фигур. В первом режиме это происходит путём установки фигуры в свободную клетку и отметки клеток, которые бьются данной фигурой, затем запускается эта же функция для оставшихся клеток и т.д., пока число поставленных фигур не дойдёт до числа, заданного пользователем. Тогда эта расстановка выводится в файл и счётчик числа расстановок увеличивается на единицу. Во втором режиме как только находится расстановка для данного количества фигур, функция завершает свою работу, увеличивается счётчик количества фигур и функция вызывается уже для большего количества фигур, пока не будет найдено максимально возможное расставляемое на данной доске число фигур.
Инструкция: В меню пользователю предлагается указать размеры доски, тип расставляемых фигур и режим работы программы. После этого, если был выбран режим вывода всех расстановок, необходимо ввести количество расставляемых фигур, после чего программа выведет на экран количество расстановок, а в файле "output.txt" появятся изображения всех расстановок. При выборе второго режима, на экран будет выведено максимальное число фигур заданного типа, которые можно расставить на данной доске.
Ссылка для скачивания:[1]
Краткое описание алгоритма:если шахматную доску представить в виде одной строчки(вторую поставить следом за первой, третью за второй и тд), то получится двоичное число. Максимальное число которое может получиться если 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 режима работы программы: первый выводит число возможных расстановок на экран, а список возможных расстановок в отдельный файл (при этом пользователь дополнительно выбирает число фигур); второй выводит на экран максимальное число фигур выбранного типа, которые можно расставить на заданной доске.
Посмотреть программу можно тут
Краткое описание алгоритма: доска представлена в виде динамического массива, заполненного 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 }
Краткое описание алгоритма: Доска представлена в виде динамического массива, по ходу программы, в зависимости от алгоритмов для разных фигур, функции заполняют доску числами 0-место свободно, 1-находится под ударом и 2-занято фигурой, потом массив преобразовывается к нормальному виду 0 и 1-фигура. Так программа прогоняет все возможные варианты расстановок. Также программа аналитически просчитывает максимальное количество фигур для каждого размера доски.
Инструкция: Сначала программа просит выбрать фигуру, с которой будем работать. Затем 2 варианта развития событий: 1 - вывод в файл всех расстановок, 2 - максимальное количество фигур. В зависимости от выбора, в первом случае еще нужно ввести количество фигур, и программа запишет в файл все возможные варианты и выведет на экран число расстановок, а во втором - на экране появится максимальное кол-во фигур. Скачать можно тут.
Основная идея программы: пользователь вводит размер доски MxM , тип фигур, их количество. Программа рассчитывает максимально возможное количество фигур , которые можно расположить на доске, чтобы они не били друг друга.
Инструкция к программе: Пользователь вводит размер доски M(size*size).А затем предоставляется выбор между нахождением максимально возможного числа фигур , и их расстановкой.Также пользователь выбирает тип фигуры , и количество(если интересует расстановка).
Скачать можно здесь
Основная идея программы: Программа подсчитывает и выводит расстановку указанного кол-ва фигур на указанном поле и второй опицей выводит максимальную расстановку на поле размером size*size.
Инструкция: Запустите программу и следуйте инструкциям. Сначала идет выбор алгоритма, после чего идет выбор фигуры и размер доски для подсчета максимальной расстановки на поле size*size. Результат будет выведен на экран.
Скачать можно тут.
Краткое описание алгоритма: Функция, которая выполняет поиск расстановок, пытается поставить фигуру в каждую клетку. В случае неудачи программа отмечает клетки, в которых фигура уже побывала, но постановка не удалась, отрицательной величиной, равной по модулю шагу, на котором эта постановка была испробована. В случае пустой клетки она отмечается нулем, в случае успеха клетка отмечается положительным числом, равным шагу, соответствующему попытке постановки. Также программа аналитически просчитывает максимальное количество фигур для каждого размера доски.
Инструкция: В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей. Он вводит размер доски и тип фигуры. Если он выбирает максимальное число расстановок, то программа выводит их количество, а также предлагает вывести все расстановки на экран. Другой вариант работы программы - вывод расстановок 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 }
Краткое описание алгоритма: Доска представлена в виде динамического массива. Если в клетке присутствует фигура, то тогада она обозначается '+', если же клетка осталась путсая, то тогда '0'.
Инструкция: Инструкция: при запуске программа предлагает пользователю ввести размер доски, при этом число должно быть четным (если же пользователь вводит нечетное число, программа предлагает ввести размер еще раз, и так до тех пор, пока не будет введено четное число). Далее пользователь выбирает режим работы программы - либо расстановка фигур, либо расчет максимального количества фигур. В режиме расстановки фигур программа предлагает выбрать тип фигуры, выводит максимальное число фигур для доски заданного размера и предлагает ввести желаемое число фигур для расстановки (если оно больше максимального, предлагается повторная попытка ввода). В режиме расчета максимального числа программа предлагает выбрать тип фигуры, выводит рассчитанное число и задает вопрос о необходимости вывода всех возможных расстановок максимального количества для данной фигуры. Оба режима работают (т.е. все запросы повторяются) до тех пор, пока пользователь не даст команду на завершение цикла. Кроме того, в программе есть возможность изменения размера доски после выхода из всех циклов. При положительном ответе пользователя и изменении размера доступны оба режима работы.
Скачать можно тут.
Основная идея программы: реализация задачи о расстановке фигур одинакового типа на произвольной доске MxM Скачать можно здесь
Краткое описание алгоритма: Доска представлена в виде динамического массива[m;m], при выводе на экран пустые клетки обозначаются звездочками,а клетки, заполненные фигурами-буквами(каждая буква соответствует первой букве названия фигуры на английском языке). Для всех фигур написаны алгоритмы проверки на возможность расстановки фигуры. После выбора типа фигуры,используется рекурсивная функция,которая проверяет возможные расстановки через данную функцию проверки ,для данного типа фигуры. Во втором варианте работы программы,она аналитически высчитывает максимально возможное количество заданных фигур на доске.В программу встроена функция,проверяющая доску на повторные и симметричные относительно всех осей симметрии способы расстановки фигур.
Инструкция: В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей. Он вводит размер доски и тип фигуры и кол-во фигур(для первого типа работы программы).Если он выбирает первый вариант работы программы - вывод всех различных расстановок N фигур.Другой вариант работы программы максимальное число расстановок- программа выводит их количество.
Скачать можно тут.
Функционал программы: получение всевозможных расстановок 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 }
Описание алгоритма:
Программа проверяет возможность расстановки фигур на доске M*M . При выводе на экран на экран клетки,занятые фигурами ,помечаются буквами,соответствующими первой букве типа фигуры. Также программа считает максимальное число фигур определенного типа,которые можно расставить на доске.
Инструкция:
В окне консоли пользователю предлагается выбрать 2 типа работы программы, затем пользователь вводит размер доски(четный),тип и количество фигур,которые необходимо разместить на доске.В зависимости от режима работы программы ,будет выведено либо максимально возможное число расстановок фигур,либо максимальное число фигур. Скачать можно [тут]
1 #include <iostream>
2 #include <windows.h>
3 using namespace std;
4
5 enum type{peshka, king, kon, ladya, slon, queen}; // все возможные типы фигур
6 const char symbols[] = "pKklsQ"; // буквенное обозначение каждой фигуры:p - пешка, K - король, k - конь, l- ладья, s - слон, Q - ферзь
7 const int NONE = INT_MAX;//константа для обозначения пустой клетки
8 int M, **desk, *colons, *rows, *diag_1, *diag_2;
9
10 // структура для описания клектки доски
11 struct point
12 {
13 int x, y;
14 point(int x = 0, int y = 0): x(x), y(y) {}
15 point &operator++()
16 {
17 if (y == M - 1)
18 {
19 ++x;
20 y = 0;
21 }
22 else
23 ++y;
24 return *this;
25 }
26 point operator+(const point &p) const
27 {
28 return point(x + p.x, y + p.y);
29 }
30 point next() const
31 {
32 point r = *this;
33 return ++r;
34 }
35 };
36
37
38 int *new_array(int n)
39 {
40 int *a = new int[n];
41 fill(a, a + n, NONE);
42 return a;
43 }
44
45 // Количество свободных клеток от клетки p до конца доски
46 int rest(const point &p, type t)
47 {
48 int r0 = (M - p.x) * M - p.y, r,
49 m = M - p.x,
50 s_2 = (m + 1) / 2 * M;
51 switch (t)
52 {
53 case peshka:
54 case kon:
55 r = s_2; break;
56 case king:
57 r = s_2 / 2; break;
58 case ladya:
59 case queen:
60 return m;
61 case slon:
62 r = m + M - 1;
63 }
64 return min(r0, r);
65 }
66
67 // Помечает клетку доски номером i
68 void set(const point &p, type t, int i)
69 {
70 if (t == peshka || t == king || t == kon)
71 desk[p.x][p.y] = i;
72 else
73 {
74 if (t == ladya || t == queen)
75 colons[p.y] = rows[p.x] = i;
76 if (t == slon || t == queen)
77 diag_1[p.x+p.y] = diag_2[p.x-p.y+M-1] = i;
78 }
79 }
80
81 // Можно ли поставить фигуру номер i на клетку p
82 bool empty(const point &p, type t, int i)
83 {
84 const int n_attack[3] = {4, 8, 8};
85 const point attack[3][8] = {{point(1, 1), point(1, -1), point(-1, 1), point(-1, -1)}, //кол-во вариантов атаки для пешки
86 {point(1, 1), point(1, -1), point(-1, 1), point(-1, -1), point(1, 0), point(-1, 0), point(0, 1), point(0, -1)}, // кол-во вариантов атаки для короля
87 {point(1, 2),point(-1, 2),point(1, -2), point (-1,-2), point (2, 1), point (2,-1), point (-2, 1),point (-2,-1)}}; //количество вариантов атаки для коня
88 switch(t)
89 {
90 case peshka:
91 case king:
92 case kon:
93 for (int k = 0; k < n_attack[t]; k++)
94 {
95 point q = p + attack[t][k];
96 if (q.x >= 0 && q.x < M && q.y >= 0 && q.y < M && desk[q.x][q.y] < i)
97 return false;
98 }
99 return true;
100 case ladya:
101 return colons[p.y] > i && rows[p.x] > i;
102 case slon:
103 return diag_1[p.x+p.y] > i && diag_2[p.x-p.y+M-1] > i;
104 case queen:
105 return colons[p.y] > i && rows[p.x] > i && diag_1[p.x+p.y] > i && diag_2[p.x-p.y+M-1] > i;
106 }
107 }
108
109 //печатает заданное количество досок на экране
110 void print(point **figures, int n_desks, int N, type t, ostream &out = cout)
111 {
112 HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
113 for (int n = 0; n < n_desks; n++)
114 {
115 out << " \xdb";
116 for (int i = 0; i < M * 2 + 2; i++)
117 out << "\xdf";
118 out << "\xdb";
119 }
120 out << endl;
121
122 int *K = new int[n_desks];
123 fill(K, K + n_desks, 0);
124 for (int i = 0; i < M; i++)
125 {
126 for (int n = 0; n < n_desks; n++)
127 {
128 int &k = K[n];
129 out << " \xdb ";
130 for (int j = 0; j < M; j++)
131 {
132 SetConsoleTextAttribute(hConsole, (i + j) % 2 == 0 ? 0xf0 : 0xf);
133 if (k < N && i == figures[n][k].x && j == figures[n][k].y)
134 {
135 out << ' ' << symbols[t];
136 k++;
137 }
138 else
139 out << " ";
140 }
141 SetConsoleTextAttribute(hConsole, 0x70);
142 out << " \xdb";
143 }
144 out << endl;
145 }
146 delete[] K;
147
148 for (int n = 0; n < n_desks; n++)
149 {
150 out << " \xdb";
151 for (int i = 0; i < M * 2 + 2; i++)
152 out << "\xdc";
153 out << "\xdb";
154 }
155 out << endl << endl;
156 }
157
158 // Вывести все возможные расположения на доске N фигур
159 void all_placements(int N, type t)
160 {
161 desk = NULL;
162 colons = rows = diag_1 = diag_2 = NULL;
163 // создание необходимых массивов, отмечающих занятость клеток, в зависимости от вида фигуры
164 if (t == peshka || t == king || t == kon)
165 {
166 desk = new int*[M];
167 for (int j = 0; j < M; j++)
168 desk[j] = new_array(M);
169 }
170 else
171 {
172 if (t == ladya || t == queen)
173 {
174 colons = new_array(M);
175 rows = new_array(M);
176 }
177 if (t == slon || t == queen)
178 {
179 diag_1 = new_array(2*M-1);
180 diag_2 = new_array(2*M-1);
181 }
182 }
183
184 const int W = 80 / (2 * M + 5);//количество досок,помещающихся на экране
185 point **figures = new point*[W];//массив фигур
186 for (int j = 0; j < W; j++)
187 figures[j] = new point[N];
188
189 int i = 0, // номер фигуры
190 k = 0; //номер комбинации
191 while (true)
192 {
193 if (rest(figures[k%W][i], t) < N - i) // если оставшиеся фигуры не помещаются на доске
194 {
195 if (i == 0) // если все комбинации закончились
196 {
197 // вывод оставшихся досок
198 if (k % W)
199 print(figures, k % W, N, t);
200 cout << "Amount of combinations: " << k << endl;
201 break;
202 }
203 // переходим к предыдущей фигуре и помечаем клетку пустой
204 set(figures[k%W][--i], t, NONE);
205 // сдвигаем фигуру на шаг вперёд
206 ++figures[k%W][i];
207 }
208 else if (!empty(figures[k%W][i], t, i)) // если фигуры помещаются, но текущая клетка под ударом
209 // сдвигаем текущую фигуру на шаг вперёд
210 ++figures[k%W][i];
211 else if (i == N - 1) // если ставим последнюю фигуру
212 {
213 // если текущая доска - последняя на строке экрана, выводим W досок
214 if ((k + 1) % W == 0)
215 print(figures, W, N, t);
216 // копирование комбинаций фигур на следующую доску
217 for (int j = 0; j < N; j++)
218 figures[(k+1)%W][j] = figures[k%W][j];
219 // переход к следующей доске
220 k++;
221 //сдвигаем текущую фигуру на шаг вперёд
222 ++figures[k%W][i];
223 }
224 else // если ставим не последнюю фигуру
225 {
226 // помечаем текущую клетку номером i
227 set(figures[k%W][i], t, i);
228 //ставим следующую фигуру на клетку после текущей
229 figures[k%W][i+1] = figures[k%W][i].next();
230 // переходим к следующей фигуре
231 i++;
232 }
233 }
234
235 //освобождение памяти
236 for (int j = 0; j < W; j++)
237 delete[] figures[j];
238 delete[] figures;
239 if (desk)
240 {
241 for (int j = 0; j < M; j++)
242 delete[] desk[j];
243 delete[] desk;
244 }
245 if (colons)
246 {
247 delete[] colons;
248 delete[] rows;
249 }
250 if (diag_1)
251 {
252 delete[] diag_1;
253 delete[] diag_2;
254 }
255 }
256
257
258 int main()
259 {
260 system("color 70"); // Установка серого фона и чёрного текста
261 while (true)
262 {
263 cout << "Choose the mode:\n1 - all possible variants of figures' placement\n2 - maximum number of figures which can be placed on the desk\nq - quit\n\n";
264 char c;
265 cin >> c;
266 cin.ignore(100, '\n');
267 switch (c)
268 {
269 case '1':
270 case '2':
271 cout << "Enter the desk size please. (The number must be even and not more than 37.)\n";
272 cin >> M;
273 while (!cin || M % 2 != 0 || M > 37 || M <= 0)
274 {
275 cout << "Error: wrong desk size. Try again please.\n";
276 cin.clear();
277 cin.ignore(100, '\n');
278 cin >> M;
279 }
280 cin.ignore(100, '\n');
281 cout << "Choose a figure, please.\n p - peshka, k - kon, l - ladya, s - slon, Q - Queen, K - King\n";
282 char f;
283 cin >> f;
284 cin.ignore(100, '\n');
285 type t;
286 int i;
287 do
288 {
289 for (i = 0; i < 6; i++)
290 {
291 if (symbols[i] == f)
292 {
293 t = type(i);
294 break;
295 }
296 }
297 if (i == 6)
298 {
299 cout << "Enter the right letter, you've chosen the wrong one.\n";
300 cin >> f;
301 cin.ignore(100, '\n');
302 }
303 } while (i == 6);
304 if (c == '1')
305 {
306 cout << "Enter the number of figures please.\n";
307 int N;
308 cin >> N;
309 while (!cin || N <= 0)
310 {
311 cout << "Error: wrong argument. Try again please.\n";
312 cin.clear();
313 cin.ignore(100, '\n');
314 cin >> N;
315 }
316 cin.ignore(100, '\n');
317 all_placements(N, t);
318 }
319 else
320 {
321 cout << "The maximal number of figures is ";
322 switch (t)
323 {
324 case peshka:
325 cout << M*M/2; break;
326 case king:
327 cout << M*M/4; break;
328 case kon:
329 cout << (M == 2 ? 4 : M*M/2); break;
330 case ladya:
331 cout << M; break;
332 case slon:
333 cout << 2*M - 2; break;
334 case queen:
335 cout << (M == 2 ? 1 : M);
336 }
337 cout << ".\n";
338 }
339 break;
340 case 'q':
341 cout << endl;
342 return 0;
343 default:
344 cout << "You've chosen the wrong command, try again please.\n";
345 }
346 cout << endl << endl;
347 }
348 }
Краткое описание алгоритма : Доска представлена в виде динамического массива;Для каждой фигуры написана отдельная функция проверки на возможность установки фигуры,проверяющая, находится ли эта фигура под ударом других. После выбора типа фигуры,используется рекурсивная функция,которая проверяет возможные расстановки через данную функцию проверки ,для данного типа фигуры. Для поиска максимального значения мы проверяем расстановку начиная с 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)Устанавливает каждую следующую фигуру на n-е свободное место которое он нашел после последней установленной фигуры, где n изменяется от 1 до бесконечности(установка заканчивается тогда, когда программа не может установить очередную фигуру). 3)Счетчик количества фигур, которые необходимо установить, уменьшается на 1 после каждой установки. 4)После того, как фигура установлена, программа рекурсивно вызывает функцию установки очередной фигуры(возвращается в пункт 2) 5)В рекурсивную функцию отправляется только копия доски. Таким образом, возвращаясь из рекурсии, мы получаем доску без последующих установленных фигур. Когда счетчик фигур, которые необходимо установить, уменьшается до нуля, данное поле сохраняется в списке. 6)Вывод списка. Скачать можно тут
Нарядчиков Александр
Инструкция: Запустить программу, следовать указаниям, полученным в меню программы.
Описание программы: Шахматное поле представлено в виде двумерного массив N на M, значения N и M пользователь вводит самостоятельно, память выделяется динамически. Также пользователь выбирает тип и количество фигур на поле. В меню можно выбрать между поиском максимально возможного числа фигур на столе и поиском всех расстановок с дальнейшей записью полей в файл.
Описание алгоритма: При поиске всех расстановок происходит установка выбранной фигуры в свободную клетку, далее происходит маркирование тех клеток, в которые уже невозможно поставить фигуру данного типа, затем процесс происходит снова(рекурсия) пока на поле не окажется выбранное пользователем число фигур. Под конец данное поле записывается в файл и происходит поиск других возможных расстановок данного типа. В конце получаем файл со всеми вариантами расстановок и их количеством. При поиске наибольшего числа фигур на доске программа ищет расстановку для одной фигуры, затем для двух, если это возможно и т.д. С каждым разом происходит увеличение счетчика количества фигур на поле, тем самым в конце данного алгоритма мы получаем максимально возможное число данного типа фигур на доске данного размера.
"T04CHESS.CPP"
1 /* FILENAME: T04CHESS.CPP
2 * LAST UPDATE: 17.01.2016
3 */
4
5 #include "CHESS.h"
6
7 /* Main function */
8 int main( void )
9 {
10 // Переменная, отвечающая за выход из меню
11 int IsReady = 1;
12 // Количество строк поля; количество столбцов поля
13 int N, M;
14 // Если идет поиск всех расстановок - 0; если идет поиск максимального числа фигур на доске - 1
15 int IsCount;
16 // Количество фигур на поле
17 int Number;
18 // Тип фигуры; количество разных расстановок; максимальное число фигур на доске
19 int tmp, count, max_value = 1;
20 // Создание указателя на тип FILE
21 FILE *F;
22
23 // Консольное меню
24 while (IsReady == 1)
25 {
26 cout << "Input figure type:\n1 - castle\n2 - bishop\n3 - knight\n4 - queen\n5 - king\n";
27 cin >> tmp;
28
29 cout << "Input number of rows on the field:\n";
30 cin >> N;
31
32 cout << "Input number of columns on the field:\n";
33 cin >> M;
34
35 // Поле шахмат
36 chess desk(N, M);
37
38 // Обнуление поля
39 desk.Clear();
40
41 cout << "Input in what mode do you want to work:\n0 - Searching for all fields variants\n1 - Searching for the maximum number of chessmen\n";
42 cin >> IsCount;
43
44 // Если идет поиск всех расстановок
45 if (IsCount == 0)
46 {
47 cout << "Input number of chessmen on the field:\n";
48 cin >> Number;
49
50 // Создание файла и его открытие
51 fopen_s(&F, "chess.txt", "wt");
52 if ((type)(tmp + 1) == 2)
53 fputs("Castles' fields:\n", F);
54 else if ((type)(tmp + 1) == 3)
55 fputs("Bishops' fields:\n", F);
56 else if ((type)(tmp + 1) == 4)
57 fputs("Knights' fields:\n", F);
58 else if ((type)(tmp + 1) == 5)
59 fputs("Quenns' fields:\n", F);
60 else if ((type)(tmp + 1) == 6)
61 fputs("Kings' fields:\n", F);
62 else
63 {
64 fputs("Error\n", F);
65 return 0;
66 }
67 // Закрытие файла
68 fclose(F);
69
70 // Количество разных расстановок
71 count = desk.FillField(IsCount, (type)(tmp + 1), 0, 0, Number, 0);
72
73 // Открытие файла в режиме повторной записи
74 fopen_s(&F, "chess.txt", "at");
75 fprintf(F, "\nNumber of fields: %i", count);
76 // Закрытие файла
77 fclose(F);
78
79 cout << "Done!\nCheck 'chess.txt' to see results\n";
80 }
81
82 // Если идет поиск максимального числа фигур на доске
83 else if (IsCount == 1)
84 {
85 while (desk.FillField(IsCount, (type)(tmp + 1), 0, 0, max_value, 0))
86 max_value++;
87 cout << "The maximum number of chessmen on the board is " << (max_value - 1) << endl;
88 max_value = 1;
89 }
90
91 // Если было введено некорректное значение для IsCount
92 else
93 cout << "Error\n";
94
95 // Продолжение работы с программой
96 cout << "Press '1' if you want to continue\nPress another number if you want to exit\n";
97 cin >> IsReady;
98
99 if (IsReady == 1)
100 continue;
101 else
102 exit(0);
103 }
104
105 return 0;
106 } // End of 'main' function
107
108 // END OF 'T04CHESS.CPP' FILE
"CHESS.CPP"
1 /* FILENAME: CHESS.CPP
2 * LAST UPDATE: 17.01.2016
3 */
4
5 #include "CHESS.H"
6
7 // Количество расстановок
8 int Result_count = 0;
9
10 /* Clear field function */
11 // Обнуление поля
12 void chess::Clear( void )
13 {
14 // Все клетки свободны
15 for (int i = 0; i < N; i++)
16 for (int j = 0; j < M; j++)
17 Field[i][j] = Free;
18 } // End of 'Clear' function
19
20 /* Check if the cell is available that function */
21 // Проверка, свободна и существует ли данная клетка
22 int chess::IsAvailable( int x, int y )
23 {
24 if (x >= 0 && y >= 0 && x < M && y < N)
25 if (Field[y][x] == Free)
26 return 1;
27
28 return 0;
29 } // End of 'IsAvailable' function
30
31 /* Output field in file function */
32 // Запись одного поля в файл
33 void chess::OutputInFile( void )
34 {
35 // Создание указателя на тип FILE
36 FILE *F;
37
38 // Открытие файла в режиме повторной записи
39 fopen_s(&F, "chess.txt", "at");
40
41 // Переход на следующую строку файла
42 fputc('\n', F);
43
44 // Заполнение файла текущем полем
45 for (int i = 0; i < N; ++i)
46 {
47 // '*' - свободная клетка; '#' - клетка, которая уже занята
48 for (int j = 0; j < M; ++j)
49 (Field[i][j] == Free || Field[i][j] == busy) ? fputc('*', F) : fputc('#', F);
50 // Переход на следующую строку файла
51 fputc('\n', F);
52 }
53
54 // Закрытие файла
55 fclose(F);
56 } /* End of 'OutputInFile' function */
57
58 /* Copy desks function */
59 // Копирование поля
60 void chess::Copy( chess &desk2 )
61 {
62 for (int i = 0; i < N; i++)
63 for (int j = 0; j < M; j++)
64 desk2.Field[i][j] = Field[i][j];
65 } // End of 'Copy' function
66
67 /* Fill field function */
68 // Заполнение полей и поиск максимального числа расстановок
69 // Chessmen_num - количество фигур, которое нужно поставить; Already_stood - количество, которое уже стоит
70 int chess::FillField( int IsCount, type set, int x, int y, int Chessmen_num, int Already_stood )
71 {
72 int i, j, k, l;
73 chess desk2(N, M);
74
75 // Обнуление поля
76 desk2.Clear();
77
78 // Пробег по всем оставшимся клеткам поля, начиная с той, на которой мы закончили предыдущую итерацию
79 for (i = y; i < N; i++)
80 for (j = ((i == y) ? x : 0); j < M; j++)
81 {
82 // Если клетка свободна
83 if (Field[i][j] == Free)
84 {
85 // Копируем доску
86 Copy(desk2);
87
88 // Множественный выбор типа фигуры
89 switch (set)
90 {
91 // Ладья
92 case castle:
93 for (k = 0; k < N; k++)
94 {
95 // Движение по столбцу
96 if (desk2.Field[k][j] == Free)
97 desk2.Field[k][j] = busy;
98 // Движение по строке
99 if (desk2.Field[i][k] == Free)
100 desk2.Field[i][k] = busy;
101 }
102 break;
103 // Слон
104 case bishop:
105 // Выбор и поиск наибольшей существующей на поле диагонали
106 for (k = 1 - (N < M ? N : M); k < (N < M ? N : M); k++)
107 {
108 // Проход из левого верхнего угла до правого нижнего
109 if (IsAvailable(j + k, i + k))
110 desk2.Field[i + k][j + k] = busy;
111 // Проход из левого нижнего до правого верхнего
112 if (IsAvailable(j + k, i - k))
113 desk2.Field[i - k][j + k] = busy;
114 }
115 break;
116 // Конь
117 case knight:
118 // Ходы коня, k - приращение по X, l - по Y
119 k = -2, l = 1;
120 // Проверка возможности хода в данную клетку
121 if (IsAvailable(j + k, i + l))
122 desk2.Field[i + l][j + k] = busy;
123
124 k = -2, l = -1;
125 // Проверка возможности хода в данную клетку
126 if (IsAvailable(j + k, i + l))
127 desk2.Field[i + l][j + k] = busy;
128
129 k = -1, l = 2;
130 // Проверка возможности хода в данную клетку
131 if (IsAvailable(j + k, i + l))
132 desk2.Field[i + l][j + k] = busy;
133
134 k = -1, l = -2;
135 // Проверка возможности хода в данную клетку
136 if (IsAvailable(j + k, i + l))
137 desk2.Field[i + l][j + k] = busy;
138
139 k = 1, l = 2;
140 // Проверка возможности хода в данную клетку
141 if (IsAvailable(j + k, i + l))
142 desk2.Field[i + l][j + k] = busy;
143
144 k = 1, l = -2;
145 // Проверка возможности хода в данную клетку
146 if (IsAvailable(j + k, i + l))
147 desk2.Field[i + l][j + k] = busy;
148
149 k = 2, l = 1;
150 // Проверка возможности хода в данную клетку
151 if (IsAvailable(j + k, i + l))
152 desk2.Field[i + l][j + k] = busy;
153
154 k = 2, l = -1;
155 // Проверка возможности хода в данную клетку
156 if (IsAvailable(j + k, i + l))
157 desk2.Field[i + l][j + k] = busy;
158 break;
159 // Ферзь
160 case queen:
161 for (k = 0; k < N; k++)
162 {
163 // Движение по столбцу
164 if (desk2.Field[k][j] == Free)
165 desk2.Field[k][j] = busy;
166 // Движение по строке
167 if (desk2.Field[i][k] == Free)
168 desk2.Field[i][k] = busy;
169 }
170
171 // Выбор и поиск наибольшей существующей на поле диагонали
172 for (k = 1 - (N < M ? N : M); k < (N < M ? N : M); k++)
173 {
174 // Проход из левого верхнего угла до правого нижнего
175 if (IsAvailable(j + k, i + k))
176 desk2.Field[i + k][j + k] = busy;
177 // Проход из левого нижнего до правого верхнего
178 if (IsAvailable(j + k, i - k))
179 desk2.Field[i - k][j + k] = busy;
180 }
181 break;
182 // Король
183 case king:
184 // Проход по квадрату 3 на 3, построенному центром на клетке, в которой стоит король
185 for (k = -1; k < 2; k++)
186 for (l = -1; l < 2; l++)
187 if (IsAvailable(j + k, i + l))
188 desk2.Field[i + l][j + k] = busy;
189 break;
190 }
191 // Установка фигуры в данную клетку
192 desk2.Field[i][j] = set;
193
194 // Проверяем, что количество поставленных фигур, которое равно номеру итерации, меньше чем необходимое число фигур
195 if ((Already_stood + 1) < Chessmen_num)
196 {
197 // Если идет поиск всех расстановок, то запускаем следующий шаг
198 if (IsCount == 0)
199 desk2.FillField(IsCount, set, j, i, Chessmen_num, Already_stood + 1);
200 // Если идет поиск максимального числа фигур на доске и была найдена хотя бы одна расстоновка, то возвращаем 1
201 else if ((IsCount == 1) && desk2.FillField(IsCount, set, j, i, Chessmen_num, Already_stood + 1))
202 return 1;
203 }
204
205 // Если количество поставленных фигур равно необходимому числу фигур
206 else if ((Already_stood + 1) == Chessmen_num)
207 {
208 // Если идет поиск всех расстановок, то увеличиваем количество расстоновок на одну и записываем поле в файл
209 if (IsCount == 0)
210 {
211 Result_count++;
212 desk2.OutputInFile();
213 }
214 // Если идет поиск максимального числа фигур на доске, значит расстановка существует, возвращаем 1
215 else if (IsCount == 1)
216 return 1;
217 }
218 }
219 }
220 // Если идет поиск всех расстановок, то возвращаем количество расстановок
221 if (IsCount == 0)
222 return Result_count;
223 // Если идет поиск максимального числа фигур на доске, то возвращаем 0
224 else if (IsCount == 1)
225 return 0;
226 } // End of 'FillField' function
227
228 // END OF 'CHESS.CPP' FILE
"CHESS.H"
1 /* FILENAME: CHESS.H
2 * LAST UPDATE: 17.01.2016
3 */
4
5 #ifndef __CHESS_H_
6 #define __CHESS_H_
7
8 #include <iostream>
9 #include <conio.h>
10
11 using namespace std;
12
13 // свободен, занят, ладья, слон, конь, ферзь, король
14 enum type { Free, busy, castle, bishop, knight, queen, king };
15
16 /* Chess class */
17 class chess
18 {
19 private:
20 // Поле данных фигур
21 type **Field;
22 // Количество строк поля; количество столбцов поля
23 int N, M;
24 public:
25 /* Default constructor */
26 chess( void )
27 {
28 N = 8, M = 8;
29
30 // Выделение памяти под массив поля
31 Field = new type*[N];
32 for (int i = 0; i < N; i++)
33 Field[i] = new type[M];
34 }
35
36 /* Class constructor */
37 chess( int _N, int _M ) : N(_N), M(_M)
38 {
39 // Выделение памяти под массив поля
40 Field = new type* [N];
41 for (int i = 0; i < N; i++)
42 Field[i] = new type [M];
43 }
44
45 /* Class destructor */
46 ~chess( void )
47 {
48 // Чистка памяти
49 for (int i = 0; i < N; i++)
50 delete[] Field[i];
51 delete[] Field;
52 }
53
54 /* Clear field function */
55 void Clear( void );
56
57 /* Check if the cell is available that function */
58 int IsAvailable( int x, int y );
59
60 /* Output field in file function */
61 void OutputInFile( void );
62
63 /* Copy desks function */
64 void Copy( chess& desk2 );
65
66 /* Fill field function */
67 int FillField ( int IsCount, type set, int x, int y, int Chessmen_num, int Already_stood);
68 }; // end of 'chess' class
69
70 #endif /*__CHESS_H_ */
71
72 // END OF 'CHESS.H' FILE
Основная идея программы: программа позволяет выводить на экран всевозможные расстановки n однотипных фигур на шахматной доске размером n*n так, чтобы ни одна из фигур не била другую.
Скачать можно тут.
1 #include <iostream>
2 #include <cstring>
3 #include <cstdlib>
4 #include <ctime>
5
6 using namespace std;
7 int R = 0; ///переменная, отвечающая за количество вариантов расстановок
8 int N; ///количество фигур для расстановки, которое задает пользователь
9 int **B; ///двумерный массив, отображающий шахматную доску
10 int M; /// размер шахматной доски
11
12
13 void showBoard() ///функция, выводящая доску на экран
14 {
15 for(int i=0; i<M; ++i) /// строки
16 {
17 for(int j=0; j<M; ++j) /// столбцы
18 {cout << B[i][j] << " ";} ///заполнение клетки с координатами i;j
19 cout << endl;
20 }
21 cout << "Variant " << ++R << "\n\n"; ///вывод номера варианта расположения с последующим переходом на новую строку
22 return;
23 }
24
25 bool checkQueen(int a, int b) /// функция, проверяющая, не бьется ли ферзь другим ферзем
26 {
27 for (int i = 0; i < M; ++i) ///проверка строки
28 {
29 if(B[a][i])
30 return false;
31 }
32
33 for(int i = 0; i < M; ++i) ///проверка столбца
34 {
35 if(B[i][b])
36 return false;
37 }
38
39 for(int i = 1; a-i >= 0 && b-i >= 0; ++i)///по диагонали влево-вверх
40 {
41 if(B[a-i][b-i])
42 return false;
43 }
44
45 for(int i = 1; a+i < M && b+i < M; ++i)///по диагонали вправо-вниз
46 {
47 if(B[a+i][b+i])
48 return false;
49 }
50
51 for(int i = 1; a+i < M && b-i >= 0; ++i)///по диагонали влево-вниз
52 {
53 if(B[a+i][b-i])
54 return false;
55 }
56
57 for(int i = 1; a-i >= 0 && b+i < M; ++i)///по диагонали вправо-вверх
58 {
59 if(B[a-i][b+i])
60 return false;
61 }
62
63 return true;
64 }
65
66 void Queen(int a, int count) ///функция, расстанавливающая ферзи
67 {
68 for(int b = 0; b < M; ++b) /// расстановка по изменению номера столбца
69 {
70 if(checkQueen(a, b)) ///проверка, бьется ли данная клетка ферзем
71 {
72 B[a][b] = 1; ///заполнение первой клетки
73 for(int i = a+1; i < M; ++i) ///расстановка указанного пользователем количества фигур
74 Queen(i,count+1);
75 if(count+1==N) /// проверка, расставили ли мы нужное количество фигур
76 showBoard();
77 B[a][b]=0; ///обнуление переменной
78 }
79 }
80 }
81
82 bool checkRook(int a, int b) /// функция, проверяющая ли данную клетку ладья
83 {
84 for (int i = 0; i < M; ++i) ///проверка строки
85 {
86 if(B[a][i])
87 return false;
88 }
89
90 for(int i = 0; i < M; ++i) ///проверка столбца
91 {
92 if(B[i][b])
93 return false;
94 }
95
96 return true;
97 }
98
99 void Rook(int a, int count) ///функция, расстанавливающая ладьи
100 {
101 for(int b = 0; b < M; ++b) /// расстановка по строкам с изменением номера столбца
102 {
103 if(checkRook(a, b)) ///проверка, бьется ли данная клетка ладьей
104 {
105 B[a][b] = 1; ///установка ладьи
106 for(int i =a+1; i<M; ++i)
107 Rook(i,count+1);
108 if(count+1 == N) /// проверка, расставили ли мы нужное количество элементов
109 showBoard();
110
111 B[a][b]=0; ///обнуление переменной
112 }
113 }
114 }
115
116 bool checkElephant(int a, int b) /// функция, проверяющая, бьется ли данная клетка слоном
117 {
118 for(int i = 1; a-i >= 0 && b-i >= 0; ++i)///проверка по диагонали влево-вверх
119 {
120 if(B[a-i][b-i])
121 return false;
122 }
123
124 for(int i = 1; a+i < M && b+i < M; ++i)///проверка по диагонали вправо-вниз
125 {
126 if(B[a+i][b+i])
127 return false;
128 }
129
130 for(int i = 1; a+i < M && b-i >= 0; ++i)///проверка по диагонали влево-вниз
131 {
132 if(B[a+i][b-i])
133 return false;
134 }
135
136 for(int i = 1; a-i >= 0 && b+i < M; ++i) ///проверка по диагонали вправо-вверх
137 {
138 if(B[a-i][b+i])
139 return false;
140 }
141
142 return true;
143 }
144 void Elephant(int dia, int count) ///функция, расстанавливающая слоны
145 {
146 int a, b; /// задача клетки, соответствующекй данной диагонали
147 if (dia < M) /// проверка диагонали
148 {
149 a = dia; /// номер строки - номер диагонали
150 b = 0; ///обнуление переменной для столбца, цикл движется по столбцу
151 }
152 else ///если все диагонали рассмотрены
153 {
154 a = M-1; /// рассматриваем самую последнюю диагональ
155 b =(dia % M)+1; ///рассчитываем координату столбца для данной диагонали
156 }
157
158 for(int i=0; a-i>=0 && b+i < M; ++i)/// цикл движется по строкам и столбцам из нижнего левого угла в правый верхний
159 {
160 int line=a-i; ///координата строки (мы уменьшаем координату строки)
161 int column=b+i; ///координата столбца (но увеличиваем координату столбца)
162
163 if(checkElephant(line, column))/// проверка, бьется ли слон по диагонали
164 {
165 B[line][column]=1; ///установка слона
166
167 for(int i=dia+1; i<2*M-1; ++i) ///расстановка фигур, основанная на изменении параметров (номера диагонали и количества рсставленных фигур)
168 Elephant(i,count+1);
169
170 if(count+1 == N) /// проверка количества расставленных фигур
171 showBoard();
172
173 B[line][column]=0; ///обнуление переменной
174 }
175 }
176 }
177
178 bool checkHorse(int a, int b) /// функция, проверяющая, бьется ли данная клетка конями
179 {
180 if ((a-1) >=0 && (b-2)>=0 && B[a-1][b-2])
181 return false;
182
183 if ((a-1)>=0 && (b+2) < M && B[a-1][b+2])
184 return false;
185
186 if ((a+1) < M && (b-2) >=0 && B[a+1][b-2])
187 return false;
188
189 if ((a+1) < M && (b+2) < M && B[a+1][b+2])
190 return false;
191
192 if ((a-2) >=0 && (b-1) >=0 && B[a-2][b-1])
193 return false;
194
195 if ((a-2) >=0 && (b+1) < M && B[a-2][b+1])
196 return false;
197
198 if ((a+2) < M && (b-1) >= 0 && B[a+2][b-1])
199 return false;
200
201 if ((a+2) < M && (b+1) < M && B[a+2][b+1])
202 return false;
203
204 return true;
205 }
206
207 void Horse(int count, int a, int b) ///функция расстановки коней; a - очередная строка, b - очередной столбец, count - счетчик количества фигур, которое необходимо расставить
208 {
209 if(count==N) /// проверка количества расставленных фигур
210 {
211 showBoard();
212 }
213 if (a == M) /// не выходит ли за предел доски
214 return;
215 for (int j=b; j<M; ++j) ///рассматриваем первую строку
216 {
217 if(checkHorse(a, j)) ///проверка
218 {
219 B[a][j]=1; ///установка коня
220 int l = a, b = j+1; ///смещение в другой столбец
221
222 if (b == M) ///проверка, не крайний ли это столбец, так как тогда мы не можем продолжать расстановку (мы ее завершили)
223 {
224 b=0; ///обнуление переменной
225 l++; ///переход на следующую
226 }
227 Horse(count+1,l,b); ///установка фигуры, увеличение счетчика
228 B[a][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку
229 }
230 }
231 for(int i=a+1; i<M; ++i) ///заполнение строк
232 {
233 for (int j=0; j<M; ++j)
234 {
235 if(checkHorse(i, j)) ///проверка клетки, не бьется ли она другими конями
236 {
237 B[i][j]=1; ///установка коня
238 int l = i, b = j+1; ///смещаемся на другой столбец
239 if (b == M)
240 {
241 b = 0;
242 l++;
243 }
244 Horse(count+1,l,b); ///установка фигуры с увеличением счетчика
245 B[i][j]=0; ///обнуление переменной
246 }
247 }
248 }
249 }
250
251 bool checkKing(int a, int b) /// функция, проверяющая, бьет ли данную клетку король
252 {
253 for(int i = a-1; i <= a+1; ++i)
254 {
255 for(int j = b-1; j <= b+1; ++j)
256 {
257 if (a>=0 && a < M && b>=0 && b < M && B[a][b])
258 return false;
259
260 if ((a+1) < M && (b-1) >=0 && B[a+1][b-1])
261 return false;
262
263 if ((a+1) < M && B[a+1][b])
264 return false;
265
266 if ((a+1) < M && (b+1) < M && B[a+1][b+1])
267 return false;
268
269 if ((b+1) < M && B[a][b+1])
270 return false;
271
272 if ((a-1)>=0 && (b+1) < M && B[a-1][b+1])
273 return false;
274
275 if ((a-1) >=0 && B[a-1][b])
276 return false;
277
278 if ((a-1) >=0 && (b-1)>=0 && B[a-1][b-1])
279 return false;
280
281 if ((b-1) >= 0 && B[a][b-1])
282 return false;
283 }
284 }
285
286 return true;
287 }
288
289 void King (int count, int a, int b) ///функция, расставляющая коней
290 {
291 for (int j=b; j<M; ++j) ///установка королей в первой строке
292 {
293 if(checkKing(a, j)) ///проверка данной клетки на возможность установки фигуры
294 {
295 B[a][j]=1; ///если по результатам проверки можно поставить фигуру, то мы ее ставим
296 King(count+1,a,j); ///расстановка фигур для первой доски
297 B[a][j]=0; ///обнуление переменной
298 }
299 }
300
301 for(int i=a+1; i<M; ++i) ///расстановка фигур
302 {
303 for (int j=0; j<M; ++j)
304 {
305 if(checkKing(i, j)) ///проверка данной клетки на возможность установки фигуры
306 {
307 B[i][j]=1; /// если короля можно поставить, то ставим его в данную клетку
308 King(count+1,i,j);
309 B[i][j]=0; ///обнуление переменной
310 }
311 }
312 }
313
314 if(count==N)
315 {
316 showBoard();/// вывод шахмат на экран
317 return;
318 }
319 }
320
321 int main()
322 {
323 cout << "Enter the size of the board: " << endl; ///ввод размера доски
324 cin >> M;
325 B = new int*[M];
326 for (int i=0; i<M; i++)
327 B[i] = new int[M];
328 for (int i = 0; i<M; i++)
329 for (int j = 0; j<M; j++)
330 B[i][j] = 0;
331 int Var;
332 cout << '\n' << "1=your number of figures, 2=max number of figures" << endl;
333 cin >> Var;
334 int F;
335 cout << '\n' << "Input type of figure: 1-queen, 2-king, 3-horse, 4-rook, 5-elephant"<< endl;
336 cin >> F;
337 if (Var==1) /// если пользователь выбрал свое количество фигур, то мы выполняем следующие действия:
338 {
339 int mn;
340 cout << "Input the number of figures" << endl;
341 cin >> N;
342 if (F==1)
343 {
344 for (int i=0; i <M; ++i)
345 Queen(i,0);
346 }
347 if (F==2)
348 {
349 King(0,0,0);
350 }
351 if (F==3)
352 {
353 Horse(0,0,0);
354 }
355 if (F==4)
356 {
357 for (int i=0; i <M; ++i)
358 Rook(i,0);
359 }
360 if (F==5)
361 {
362 for(int i = 0; i<2*M-1; ++i)
363 Elephant(i,0);
364 }
365 }
366 else if (Var==2) /// если пользователь выбрал максимальное количество фигур
367 {
368 int mn;
369 if (F==1)
370 {
371 mn=M;
372 cout << "Max number " << mn << endl; /// выводим максимальное количество фигур
373 N=mn; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
374 for (int i=0; i < M; ++i)
375 Queen(i,0);
376 }
377
378 if (F==2)
379 {
380 mn=0.25*M*M;
381 cout << '\n' << "Max number " << mn << endl;
382 N=mn; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
383 King(0,0,0);
384 }
385 if (F==3)
386 {
387 mn=0.5*M*M;
388 cout << "Max number " << mn << endl;
389 N=mn; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
390 Horse(0,0,0);
391 }
392 if (F==4)
393 {
394 mn=M;
395 cout << "Max number " << mn << endl;
396 N=mn; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
397 for (int i=0; i <M; ++i)
398 Rook(i,0);
399 }
400 if (F==5)
401 {
402 mn=2*M-2;
403 cout << "Max number " << mn << endl;
404 N=mn; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше
405 for(int i = 0; i<2*M-1; ++i)
406 Elephant(i,0);
407 }
408 }
409 }
Инструкция: В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей: либо максимальное число вариантов, либо посмотреть наглядно на варианты. Человек вводит размер доски и тип фигуры.
Скачать программу можно [2]
1 #define windows
2
3 #include <stdio.h>
4 #include <vector>
5
6 #ifdef windows
7 #include <windows.h>
8 #endif // windows
9
10 using namespace std;
11
12 #ifdef windows
13 HANDLE hCon;
14 #endif // windows
15
16 unsigned fact(int n) //factorial of a number
17 {
18 unsigned long long ret = 1;
19 for(int i = 2; i <= n; i++)
20 ret *= i;
21 return ret;
22 }
23
24 struct desk
25 {
26 char **deskFigures, **deskOccupy; //desk with figures, desk with occupation counter for each cell
27 int x, y, size, a, f; //pointer position(x, y), size of the desk, amount of prints, amount of figures
28 vector<pair<int, int> > *s; //stack of placed figures
29 bool stackIsUsed; //if stack is needed
30 desk(int size, bool stackIsUsed = true):x(0), y(0), size(size), a(0), f(0), stackIsUsed(stackIsUsed)
31 {
32 deskFigures = new char*[size];
33 for(int i = 0; i < size; i++)
34 deskFigures[i] = new char[size];
35 deskOccupy = new char*[size];
36 for(int i = 0; i < size; i++)
37 deskOccupy[i] = new char[size];
38 if(stackIsUsed)
39 s = new vector<pair<int, int> >;
40 clear();
41 }
42 ~desk()
43 {
44 for(int i = 0; i < size; i++)
45 delete deskFigures[i];
46 delete deskFigures;
47 for(int i = 0; i < size; i++)
48 delete deskOccupy[i];
49 delete deskOccupy;
50 if(stackIsUsed)
51 delete s;
52 }
53 void setKnight(int x, int y, int z) //increase all cells occupied by knight at (x, y) on z
54 {
55 if(x + 2 < size)
56 {
57 if(y - 1 >= 0)
58 deskOccupy[x + 2][y - 1] += z;
59 if(y + 1 < size)
60 deskOccupy[x + 2][y + 1] += z;
61 }
62 if(y + 2 < size)
63 {
64 if(x - 1 >= 0)
65 deskOccupy[x - 1][y + 2] += z;
66 if(x + 1 < size)
67 deskOccupy[x + 1][y + 2] += z;
68 }
69 if(x - 2 >= 0)
70 {
71 if(y - 1 >= 0)
72 deskOccupy[x - 2][y - 1] += z;
73 if(y + 1 < size)
74 deskOccupy[x - 2][y + 1] += z;
75 }
76 if(y - 2 >= 0)
77 {
78 if(x - 1 >= 0)
79 deskOccupy[x - 1][y - 2] += z;
80 if(x + 1 < size)
81 deskOccupy[x + 1][y - 2] += z;
82 }
83 }
84 void setBishop(int x, int y, int z) //increase all cells occupied by bishop at (x, y) on z
85 {
86 for(int ix = 0, iy1 = y - x, iy2 = y + x; ix < size; ix++, iy1++, iy2--)
87 if(ix != x)
88 {
89 if((iy1 >= 0)and(iy1 < size))
90 deskOccupy[ix][iy1] += z;
91 if((iy2 >= 0)and(iy2 < size))
92 deskOccupy[ix][iy2] += z;
93 }
94 }
95 void setRook(int x, int y, int z) //increase all cells occupied by rook at (x, y) on z
96 {
97 for(int i = 0; i < size; i++)
98 {
99 if(i != x)
100 deskOccupy[i][y] += z;
101 if(i != y)
102 deskOccupy[x][i] += z;
103 }
104 }
105 void setKing(int x, int y, int z) //increase all cells occupied by king at (x, y) on z
106 {
107 for(int ix = x - 1; ix <= x + 1; ix++)
108 for(int iy = y - 1; iy <= y + 1; iy++)
109 if((ix >= 0)and(ix < size)and(iy >= 0)and(iy < size)and((ix != 0)or(iy != 0)))
110 deskOccupy[ix][iy] += z;
111 }
112 void setFigure(int x, int y, int z, char figure) //increase all cells occupied by figure
113 //and (x, y) on z
114 {
115 deskOccupy[x][y] += z;
116 switch(figure)
117 {
118 case 'N':
119 setKnight(x, y, z);
120 break;
121 case 'B':
122 setBishop(x, y, z);
123 break;
124 case 'R':
125 setRook(x, y, z);
126 break;
127 case 'Q':
128 setBishop(x, y, z);
129 setRook(x, y, z);
130 break;
131 case 'K':
132 setKing(x, y, z);
133 break;
134 }
135 }
136 bool putFigure(int x, int y, char figure) //place figure on desk and update occupied cells
137 {
138 if(deskFigures[x][y] > 0)
139 return false;
140 deskFigures[x][y] = figure;
141 if(stackIsUsed)
142 s -> push_back(make_pair(x, y));
143 setFigure(x, y, 1, figure);
144 f++;
145 return true;
146 }
147 int cellsLeft() //amount of cells after pointer
148 {
149 return (size - y) * size - x;
150 }
151 bool putNextFree(char figure) //attempt to put figure on the next free(and not occupied) place
152 {
153 if(y >= size)
154 return false;
155 while(deskOccupy[x][y] > 0)
156 {
157 if(++x == size)
158 {
159 if(++y == size)
160 return false;
161 x = 0;
162 }
163 }
164 return putFigure(x, y, figure);
165 }
166 void removeFigure(int x, int y) //remove figure from (x, y)
167 {
168 if(deskFigures[x][y]!=0)
169 setFigure(x, y, -1, deskFigures[x][y]);
170 deskFigures[x][y] = 0;
171 f--;
172 }
173 void removeBishop(int diag, bool color, bool left) //remove bishop
174 {
175 if(color) //true - white, false - black
176 {
177 if(diag > 0) //diag - number of diagonal
178 {
179 int diff = left ? 0 : diag * 2;
180 removeFigure(diff, diag * 2 - diff);
181 removeFigure(size - diff - 1, size - diag * 2 + diff - 1);
182 }
183 else
184 if(left) //determine position of the bishop on the diagonal
185 removeFigure(0, 0);
186 else
187 removeFigure(size - 1, size - 1);
188 }
189 else
190 {
191 if(diag > 0)
192 {
193 int diff = left ? 0 : diag * 2;
194 removeFigure(size - diff - 1, diag * 2 - diff);
195 removeFigure(diff, size - diag * 2 + diff - 1);
196 }
197 else
198 if(left)
199 removeFigure(0, size - 1);
200 else
201 removeFigure(size - 1, 0);
202 }
203 }
204 void putBishop(int diag, bool color, bool left) //place bishop
205 {
206 if(color)
207 {
208 if(diag > 0)
209 {
210 int diff = left ? 0 : diag * 2;
211 putFigure(diff, diag * 2 - diff, 'B');
212 putFigure(size - diff - 1, size - diag * 2 + diff - 1, 'B');
213 }
214 else
215 if(left)
216 putFigure(0, 0, 'B');
217 else
218 putFigure(size - 1, size - 1, 'B');
219 }
220 else
221 {
222 if(diag > 0)
223 {
224 int diff = left ? 0 : diag * 2;
225 putFigure(size - diff - 1, diag * 2 - diff, 'B');
226 putFigure(diff, size - diag * 2 + diff - 1, 'B');
227 }
228 else
229 if(left)
230 putFigure(0, size - 1, 'B');
231 else
232 putFigure(size - 1, 0, 'B');
233 }
234 }
235 void swapBishops(int diag, bool color, bool left) //move pair bishops to another borders
236 {
237 removeBishop(diag, color, left);
238 putBishop(diag, color, not(left));
239 }
240 void figureBefore() //remove one figure from stack and change pointer to the next position after figure was placed
241 {
242 pair<int, int> c = s -> back();
243 s -> pop_back();
244 x = c.first;
245 y = c.second;
246 removeFigure(x, y);
247 if(++x == size)
248 {
249 x = 0;
250 y++;
251 }
252 }
253 void clear() //clear the desk
254 {
255 for(int ix = 0; ix < size; ix++)
256 for(int iy = 0; iy < size; iy++)
257 {
258 deskFigures[ix][iy] = 0;
259 deskOccupy[ix][iy] = 0;
260 }
261 x = 0;
262 y = 0;
263 if(stackIsUsed)
264 s -> empty();
265 f = 0;
266 }
267 void show() //show the desk
268 {
269 a++;
270 printf("%i:\n", a);
271 #ifdef windows
272 unsigned background = 4;
273 #else
274 printf("\x1b[31m");
275 char background = 47;
276 #endif //windows
277 for(int y = 0; y < size; y++)
278 for(int x = 0; x < size; x++)
279 {
280 #ifdef windows
281 SetConsoleTextAttribute(hCon, background);
282 #else
283 printf("\x1b[%dm", background);
284 #endif //windows
285 if(deskFigures[x][y] == 0)
286 putchar(' ');
287 else
288 putchar(deskFigures[x][y]);
289 #ifdef windows
290 if(x < size - 1)
291 background = background == 4 ? 116 : 4;
292 else
293 {
294 SetConsoleTextAttribute(hCon, 7);
295 putchar('\n');
296 }
297 #else
298 if(x < size - 1)
299 background = background == 47 ? 40 : 47;
300 else
301 {
302 printf("\x1b[0m\n");
303 if(y < size - 1)
304 printf("\x1b[31m");
305 }
306 #endif // windows
307 }
308 }
309 };
310
311 int m = -1; //0 for number of arrangements, 1 for all variants
312
313 unsigned lookForFigure(int size, int amount, char figure, bool show = true) //brute-force
314 {
315 desk *d = new desk(size);
316 unsigned ret = 0;
317 while((d -> f > 0)or(d -> cellsLeft() >= amount))
318 if(not(d -> putNextFree(figure)))
319 {
320 if(d -> f == amount)
321 {
322 if(show)
323 d -> show();
324 ret++;
325 }
326 d -> figureBefore();
327 }
328 delete d;
329 return ret;
330 }
331
332 void lookForKnight(int size, int amount) //arrangements of knights
333 {
334 if(m == 0)
335 {
336 printf("Amount of arrangements: ");
337 if(size == 2)
338 printf("1\n");
339 else
340 if(size == 4)
341 printf("6\n");
342 else
343 printf("2\n");
344 }
345 else
346 {
347 desk *d = new desk(size);
348 if(size == 2)
349 {
350 d -> putFigure(0, 0, 'N');
351 d -> putFigure(0, 1, 'N');
352 d -> putFigure(1, 0, 'N');
353 d -> putFigure(1, 1, 'N');
354 d -> show();
355 }
356 else
357 if(size==4)
358 lookForFigure(size, amount, 'N');
359 else
360 {
361 for(int x = 0; x < size; x++)
362 for(int y = 0;y < size; y++)
363 if(x + y % 2 == 0)
364 d -> putFigure(x, y, 'N');
365 d -> show();
366 d -> clear();
367 for(int x = 0; x < size; x++)
368 for(int y = 0;y < size; y++)
369 if(x + y % 2 == 1)
370 d -> putFigure(x, y, 'N');
371 d -> show();
372 }
373 }
374 }
375
376 void lookForBishop(int size, int amount) //arrangements of bishops
377 {
378 if(m == 0)
379 printf("Amount of arrangements: %u", (unsigned) 1 << size);
380 else
381 {
382 desk *d = new desk(size, false);
383 bool *b = new bool[size];
384 for(int dw = 0; dw < size/2; dw++)
385 {
386 d -> putBishop(dw, true, false);
387 d -> putBishop(dw, false, false);
388 }
389 int p = size - 1;
390 for(;;)
391 {
392 d -> show();
393 while(b[p])
394 {
395 d -> swapBishops(p % (size / 2), p < size / 2, true);
396 b[p--] = false;
397 if(p < 0)
398 return;
399 }
400 b[p] = true;
401 d -> swapBishops(p % (size / 2), p < size / 2, false);
402 p = size - 1;
403 }
404 }
405 }
406
407 void lookForRook(int size, int amount) //arrangements of rooks
408 {
409 if(m == 0)
410 printf("Amount of arrangements: %u", fact(size));
411 else
412 lookForFigure(size, amount, 'R');
413 }
414
415 void lookForQueen(int size, int amount) //arrangements of queens
416 {
417 if(m == 0)
418 printf("Amount of arrangements: %u", lookForFigure(size, amount, 'Q', false));
419 else
420 lookForFigure(size, amount, 'Q');
421 }
422
423 void lookForKing(int size, int amount) //arrangements of kings
424 {
425 if(m == 0)
426 printf("Amount of arrangements: %u", lookForFigure(size, amount, 'K', false));
427 else
428 lookForFigure(size, amount, 'K');
429 }
430
431 int main()
432 {
433 int s = -1, f = -1; //s - size, f - figure
434 #ifdef windows
435 hCon = GetStdHandle(STD_OUTPUT_HANDLE);
436 #endif // windows
437 sizeInput:
438 printf("Enter size of the desk:\n");
439 scanf("%i", &s);
440 if((s<=0)or(s%2!=0))
441 {
442 printf("Size must be above 0 and even\n");
443 goto sizeInput;
444 }
445 modeInput:
446 printf("Enter mode:\n\t0: Print amount of results\n\t1: Print all results\n");
447 scanf("%i", &m);
448 if((m<0)or(m>1))
449 {
450 printf("Mode can be 0 or 1\n");
451 goto modeInput;
452 }
453 figureInput:
454 printf("Enter figures to be placed\n\t0: Knight (N)\n\t1: Bishop (B)\n\t2: Rook (R)\n\t3: Queen (Q)\n\t4: King (K)\n");
455 scanf("%i", &f);
456 if((f<0)or(f>4))
457 {
458 printf("Figure number ranges from 0 to 4\n");
459 goto figureInput;
460 }
461 switch(f)
462 {
463 case 0:
464 if(s==2)
465 lookForKnight(s, 4);
466 else
467 lookForKnight(s, s *s / 2);
468 break;
469 case 1:
470 lookForBishop(s, 2 * s - 2);
471 break;
472 case 2:
473 lookForRook(s, s);
474 break;
475 case 3:
476 if(s==2)
477 lookForQueen(s, 1);
478 else
479 lookForQueen(s, s);
480 break;
481 case 4:
482 lookForKing(s, (s / 2) * (s / 2));
483 break;
484 }
485 return 0;
486 }
Суть программы: Программа позволяет на шахматной доске MxM расставить N фигур K типа всевозможными способами, причем при этом производится расчет максимального количества фигур K типа, которые можно расставить на данной доске MxM.
Идея: Шахматная доска представляет собой двумерный динамический массив. С помощью рекурсивного метода программа пробегает по массиву, проверяя клетки доски по всем направлениям на то, атакованы ли они другими фигурами этого типа. В зависимости от количества поставленных фигур изменяется количество итераций. В новую клетку ставиться новая фигура и так до тех пор, пока не выполнится написанное выше условие, после чего начнется обратный ход.
Инструкция: Программа написана в виде меню на английском языке: пользователю будет предоставлена возможность сначала обозначить размер доски, а после выбрать тип фигур и их количество для дальнейшей работы с ними. Комментарии к программе написаны также на английском языке.
Ссылка для скачиваний: здесь.
Программа: 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 }
Программа работает в двух режимах: поиск максимального числа фигур для заданного поля и количество возможных расстановок заданного числа фигур для заданного поля.
Алгоритм:
- Для поиска количества возможных расстановок заданного числа фигур для заданного поля – Проверяется, возможно ли поставить фигуру в данную клетку, рекурсивно перебирает для каждой клетки поля, как начальной клетки, все варианты расстановки заданного количества фигур относительно нее и выводит на экран все расстановки, которые подходят условиям.
- Для поиска максимального числа фигур для заданного поля – Проверяется, можно ли поставить одну фигуру, две, три и так далее, пока фигур больше поставить будет нельзя.
Скачать можно тут.
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 }
Краткое описание алгоритма: доска представлена в виде динамического массива, при выводе на экран пустые клетки обозначаются точками, а клетки, заполненные фигурами, обозначаются буквами (каждая буква соответствует первой букве названия фигуры на английском языке). Для каждой фигуры написаны функции проверки на возможность установки фигуры и функции расстановки. Кроме того, программа аналитически считает максимальное количество фигур для доски заданного пользователем размера и, при наличии команды пользователя, выводит все возможные расстановки рассчитанного максимального количества фигур на экран.
Инструкция: при запуске программа предлагает пользователю ввести размер доски, при этом число должно быть четным (если же пользователь вводит нечетное число, программа предлагает ввести размер еще раз, и так до тех пор, пока не будет введено четное число). Далее пользователь выбирает режим работы программы - либо расстановка фигур, либо расчет максимального количества фигур. В режиме расстановки фигур программа предлагает выбрать тип фигуры, выводит максимальное число фигур для доски заданного размера и предлагает ввести желаемое число фигур для расстановки (если оно больше максимального, предлагается повторная попытка ввода). В режиме расчета максимального числа программа предлагает выбрать тип фигуры, выводит рассчитанное число и задает вопрос о необходимости вывода всех возможных расстановок максимального количества для данной фигуры. Оба режима работают (т.е. все запросы повторяются) до тех пор, пока пользователь не даст команду на завершение цикла. Кроме того, в программе есть возможность изменения размера доски после выхода из всех циклов. При положительном ответе пользователя и изменении размера доступны оба режима работы.
Скачать можно здесь.
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 }
Работа программы: Программа предлагает 2 режима работы 1 режим это нахождение для 1 из 5 фигур таких расстановок L фигур, на доске M*N, что они не бьют друг друга, второй режим возможно найти максимальное число фигур, которое можно расставить на этом поле, чтобы они не били друг друга.
Идея алгоритма: Основная идея заключается в присваиванию клетке 1 из 3 значений, пустая клетка, битая клетка или клетка, в которой стоит фигура. В точку ставится фигура, дальше маркируются поля, в которые уже невозможно поставить фигуру, затем мы ставим следующую фигуру и снова маркируем поля, в которые не можем ничего поставить и так далее до нужного пользователю числа фигур. Поиск максимального числа это попытка поставить на доску как можно больше фигур, он пользуется алгоритмами первого пункта.
Скачать можно тут.
