Информатика: Расстановка шахматных фигур

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск

Лебедев Станислав

Функционал программы: получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n;

Идея алгоритма: рекурсивно вызывается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается.

Скачать можно тут.

  1 #include <iostream>
  2 #include <math.h>
  3 #include <cmath>
  4 
  5 using namespace std;
  6 
  7 int n,type, *a, *stak, variant, maxst = 0;
  8 
  9 void king(int x, int &top)                      //отметить битые клетки королем
 10 {
 11     // 012
 12     // 345
 13     // 678
 14 
 15     //0
 16     if (((x % n) > 1) && ((x / n) > 1))
 17     {
 18         int ii = x - n - 1;
 19         if (a[ii] != -2)
 20         {
 21             a[ii]++;
 22             stak[top] = ii;
 23             top++;
 24         }
 25     }
 26 
 27     //1
 28     if ((x / n) > 0)
 29     {
 30         int ii = x - n;
 31         if (a[ii] != -2)
 32         {
 33             a[ii]++;
 34             stak[top] = ii;
 35             top++;
 36         }
 37     }
 38 
 39     //2
 40     if (((x % n) < (n - 1)) && ((x / n) > 0))
 41     {
 42         int ii = x - n + 1;
 43         if (a[ii] != -2)
 44         {
 45             a[ii]++;
 46             stak[top] = ii;
 47             top++;
 48         }
 49     }
 50 
 51     //3
 52     if ((x % n) > 0)
 53     {
 54         int ii = x - 1;
 55         if (a[ii] != -2)
 56         {
 57             a[ii]++;
 58             stak[top] = ii;
 59             top++;
 60         }
 61     }
 62 
 63     //5
 64     if ((x % n) < (n - 1))
 65     {
 66         int ii = x + 1;
 67         if (a[ii] != -2)
 68         {
 69             a[ii]++;
 70             stak[top] = ii;
 71             top++;
 72         }
 73     }
 74 
 75     //6
 76     if (((x % n ) > 0) && ((x / n) < (n - 1)))
 77     {
 78         int ii = x + n - 1;
 79         if (a[ii] != -2)
 80         {
 81             a[ii]++;
 82             stak[top] = ii;
 83             top++;
 84         }
 85     }
 86 
 87     //7
 88     if ((x / n ) < (n - 1))
 89     {
 90         int ii = x + n;
 91         if (a[ii] != -2)
 92         {
 93             a[ii]++;
 94             stak[top] = ii;
 95             top++;
 96         }
 97     }
 98 
 99     //8
100     if (((x % n ) < (n - 1)) && ((x / n) < (n - 1)))
101     {
102         int ii = x + n + 1;
103     if (a[ii] != -2)
104         {
105             a[ii]++;
106             stak[top] = ii;
107             top++;
108         }
109     }
110 }
111 
112 void bishop(int x, int &top)                                                              //отметить битые клетки слоном
113 {
114     //вверх влево
115     for (int i = (x - (n + 1)); ((i >= 0) && ((i%n) != (n-1))); i -= (n+1))
116     {
117         if (a[i] != -2)
118         {
119             a[i]++;
120             stak[top] = i;
121             top++;
122         }
123     }
124 
125     //вниз вправо
126     for (int i = (x + (n + 1)); ((i < n*n) && ((i%n) != 0)); i += (n+1))
127     {
128         if (a[i] != -2)
129         {
130             a[i]++;
131             stak[top] = i;
132             top++;
133         }
134     }
135 
136     //вверх вправо
137     for (int i = x - (n - 1); ((i >= 0) && ((i%n) != 0)); i -= (n-1))
138     {
139         if (a[i] != -2)
140         {
141             a[i]++;
142             stak[top] = i;
143             top++;
144         }
145     }
146 
147     //вниз влево
148     for (int i = x + (n - 1); ((i < n*n) && ((i%n) != (n-1))); i += (n-1))
149     {
150         if (a[i] != -2)
151         {
152             a[i]++;
153             stak[top] = i;
154             top++;
155         }
156     }
157 }
158 
159 void knight(int x, int &top)                                            //отметить битые клетки конем
160 {
161     if (((x%n) > 0) && (x/n) > 1)
162     {
163         int ii = x - 2*n - 1;
164         if (a[ii] != -2)
165         {
166             a[ii]++;
167             stak[top] = ii;
168             top++;
169         }
170     }
171 
172     if (((x%n) > 1) && (x/n) > 0)
173     {
174         int ii = x - n - 2;
175         if (a[ii] != -2)
176         {
177             a[ii]++;
178             stak[top] = ii;
179             top++;
180         }
181     }
182 
183     if (((x%n) > 1) && (x/n) < (n - 1))
184     {
185         int ii = x + n - 2;
186         if (a[ii] != -2)
187         {
188             a[ii]++;
189             stak[top] = ii;
190             top++;
191         }
192     }
193 
194     if (((x%n) > 0) && (x/n) < (n - 2))
195     {
196         int ii = x + 2*n - 1;
197         if (a[ii] != -2)
198         {
199             a[ii]++;
200             stak[top] = ii;
201             top++;
202         }
203     }
204 
205     if (((x%n) < (n - 1)) && (x/n) < (n - 2))
206     {
207         int ii = x + 2*n + 1;
208         if (a[ii] != -2)
209         {
210             a[ii]++;
211             stak[top] = ii;
212             top++;
213         }
214     }
215 
216     if (((x%n) < (n - 2)) && (x/n) < (n - 1))
217     {
218         int ii = x + n + 2;
219         if (a[ii] != -2)
220         {
221             a[ii]++;
222             stak[top] = ii;
223             top++;
224         }
225     }
226 
227     if (((x%n) < (n - 2)) && (x/n) < 0)
228     {
229         int ii = x - n + 2;
230         if (a[ii] != -2)
231         {
232             a[ii]++;
233             stak[top] = ii;
234             top++;
235         }
236     }
237 
238     if (((x%n) < (n - 1)) && (x/n) < 1)
239     {
240         int ii = x - 2*n + 1;
241         if (a[ii] != -2)
242         {
243             a[ii]++;
244             stak[top] = ii;
245             top++;
246         }
247     }
248 }
249 
250 void rook(int x, int &top)                                                      //отметить битые клетки ладьей
251 {
252     int k = x - (x % n);
253     while ((k/n) == (x/n))
254     {
255 
256         if ((k != x) && (a[k] != -2))
257         {
258             a[k]++;
259             stak[top] = k;
260             top++;
261         }
262         k ++;
263     }
264 
265     k = (x % n);
266     while (((k/n)) != n)
267     {
268         if ((k != x) && (a[k] != -2))
269         {
270             a[k]++;
271             stak[top] = k;
272             top++;
273         }
274         k += n;
275     }
276 
277 }
278 void set_figure(int x, int &top)                                    //ставим фигуры на доску
279 {
280     //отмечаем "битые" клетки
281     switch (type)
282     {
283 		//король
284         case 1:
285         {
286             king(x,top);
287             break;
288         }
289 
290 		//слон
291 		case 2:
292 		{
293 		    bishop(x,top);
294             break;
295 		}
296 
297 		//конь
298 		case 3:
299 		{
300 		    knight(x,top);
301 			break;
302 		}
303 		//ладья
304         case 4:
305         {
306             rook(x,top);
307             break;
308         }
309         //ферзь
310         case 5:
311         {
312             rook(x,top);
313             bishop(x,top);
314             break;
315         }
316     }
317 
318     //отмечаем,что в данной клетке стоит фигура
319 	a[x] = -1;
320     stak[top] = x;
321     top++;
322 }
323 
324 void step(int top,int x,int st)
325 {
326 	int xtop = top;
327 	switch (variant)
328 	{
329 		case 1:
330 		{
331 			if (st != (n - 1))
332 			{
333 				set_figure(x,top);
334 				for (int i = 0; i < (n*n); i++)
335 					if (a[i] == 0)
336 						step(top,i,st + 1);
337 			}
338 			else[[:File:Шахматы.rar]]
339 			{
340 				set_figure(x,top);
341                 cout << endl;
342 				for (int i = 0; i < (n*n); i++)
343 				{
344 					cout.width(3);
345 					if (((i % n) == 0) && (i != 0))
346 						cout << endl;
347 					if (a[i] == -1)
348 						cout << 1;
349 					else
350 						cout << 0;
351 				}
352 				cout << endl;
353 			}
354 			break;
355 		}
356 		case 2:
357 		{
358 			set_figure(x,top);
359 			if ((st+1) > maxst)
360 				maxst = st + 1;
361 			for (int i = 0; i < (n*n); i++)
362 				if (a[i] == 0)
363 					step(top,i,st+1);
364 			break;
365 		}
366 	}
367 
368 
369 
370 // обратный ход
371     for (int i = xtop; i < top; i++)
372     {
373         if ((a[stak[i]] != -1) && (a[stak[i]] != -2))
374             a[stak[i]]--;
375         else
376             //не забываем отметить,что фигура уже здесь стояла(чтобы избежать повторов)
377             if (a[stak[i]] == -1)
378                 a[stak[i]] = -2;
379  //       cerr << " Back "  << stak[i] << endl;
380     }
381 }
382 
383 int main()
384 {
385 
386     //cin >> n >> type >> variant;
387     n = 5;
388     type = 4;
389 	variant = 1;
390     a    = new int[n*n];
391     stak = new int[n*n*4];
392 
393     for (int i = 0; i < (n*n); i++)
394     {
395         for (int j = 0; j < (n*n); j++)
396             a[j] = 0;
397         if (variant == 1)
398             cout << "__________________________________" << endl;
399         step(0,i,0);
400     }
401 	if (variant == 2)
402 	  cout << maxst;
403     return 0;
404 }


Иванова Яна

Краткое описание алгоритма: Функция, которая выполняет поиск расстановок, пытается поставить фигуру в каждую клетку. В случае неудачи программа отмечает клетки, в которых фигура уже побывала, но постановка не удалась, отрицательной величиной, равной по модулю шагу, на котором эта постановка была испробована. В случае пустой клетки она отмечается нулем, в случае успеха клетка отмечается положительным числом, равным шагу, соответствующему попытке постановки. Также программа аналитически просчитывает максимальное количество фигур для каждого размера доски.

Инструкция: В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей. Он вводит размер доски и тип фигуры. Если он выбирает максимальное число расстановок, то программа выводит их количество, а также предлагает вывести все расстановки на экран. Другой вариант работы программы - вывод расстановок N фигур.

Посмотреть программу можно здесь

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <exception>
  4 #include <string>
  5 #include <algorithm>
  6 
  7 //пусть для определенности максимальный размер доски - 128 клеток
  8 #define MAX_SIZE 128
  9 
 10 // перечисление для определения типа фигуры
 11 enum figure_type
 12 {
 13     KING,
 14     QUEEN,
 15     ROOK,
 16     BISHOP,
 17     KNIGHT
 18 };
 19 
 20 // класс для создания доски и расстановки фигур
 21 class chess_board
 22 {
 23 public:
 24     // конструктор (принимает только размеры)
 25     chess_board(const int &size)
 26     {
 27         if (size >= 0 && size <= MAX_SIZE)
 28         {
 29             size_ = size;
 30             clean_board();
 31         }
 32 
 33         else
 34         {
 35             std::cout << "wrong size" << std::endl;
 36             throw std::string("wrong size");
 37         }
 38     }
 39 
 40 
 41     // функция очистки доски (занулить все клетки)
 42     void clean_board()
 43     {
 44         //обнулить счетчик количества фигур на доске
 45         figures_on_board_ = 0;
 46         //присвоить всем клеткам значение 0
 47         for (int i = 0; i < size_; ++i)
 48         {
 49             for (int j = 0; j < size_; ++j)
 50             {
 51                 board_[i][j] = 0;
 52             }
 53         }
 54     }
 55 
 56     // функция, принимающая размер доски
 57     int get_size()
 58     {
 59         return size_;
 60     }
 61     // функция, обновляющая количество фигур на доске
 62     int get_figures_number()
 63     {
 64         return figures_on_board_;
 65     }
 66 
 67     //функция, пытающаяся поставить фигуру на свободное место и возвращающая
 68     //истину в случае успеха и ложь в случае неудачи
 69     bool put_figure (const figure_type& figure, const int& x, const int& y, const int& step)
 70     {
 71         if (board_[x][y] > 0 || board_[x][y] < -step)
 72         {
 73            //если здесь уже стоит фигура или мы когда-то пытались ее сюда поставить, вернуть ложь
 74             return false;
 75         }
 76 
 77         if (check_figure(figure, x, y))
 78         {
 79             board_[x][y] = step;
 80             ++figures_on_board_;
 81             return true;
 82         }
 83         else
 84         {
 85             return false;
 86         }
 87     }
 88 
 89     //отметить клетку как ранее пройденную функцией
 90     //вычесть единицу из количества фигур на доске
 91     void remove_figure(const int& x, const int& y)
 92     {
 93         board_[x][y] *= -1;
 94         --figures_on_board_;
 95     }
 96 
 97     //функция печати доски на экран
 98     void print() const
 99     {
100         using namespace std;
101         cout << "==========================================" << endl;
102         for (int i = 0; i < size_; ++i)
103         {
104             for (int j = 0; j < size_; ++j)
105             {
106                 //если фигура стоит в клетке, то вывести "*", если нет - вывести "-"
107                 cout << (board_[i][j] > 0?"*":"-") << " ";
108             }
109             cout << endl;
110         }
111         cout << "==========================================" << endl;
112     }
113 
114 private:
115 
116     //функция, проверяющая возможность или невозможность постановки фигуры на данную клетку
117     bool check_figure(const figure_type& figure, const int& x, const int& y)
118     {
119         //выбор следующего действия в зависимости от типа фигуры
120         switch (figure)
121         {
122             case KING:
123                 return check_king(x, y);
124             case QUEEN:
125                 return check_queen(x, y);
126             case ROOK:
127                 return check_rook(x, y);
128             case BISHOP:
129                 return check_bishop(x, y);
130             case KNIGHT:
131                 return check_knight(x, y);
132                 //в случае ошибки ввода вернуть ложь
133             default:
134                 return false;
135         }
136     }
137 
138     //поиск расстановок короля
139     bool check_king(const int& x, const int& y)
140     {
141         int min_x = std::max(x - 1, 0);
142         int max_x = std::min(x + 1, size_ - 1);
143         int min_y = std::max(y - 1, 0);
144         int max_y = std::min(y + 1, size_ - 1);
145 
146         for (int i = min_x; i <= max_x; ++i)
147         {
148             for (int j = min_y; j <= max_y; ++j)
149             {
150                 if (board_[i][j] > 0)
151                 {
152                     return false;
153                 }
154             }
155         }
156         return true;
157     }
158 
159     //поиск расстановок ладьи
160     bool check_rook(const int& x, const int& y)
161     {
162         for (int i = 0; i < size_; ++i)
163         {
164             if (board_[i][y] > 0)
165             {
166                 return false;
167             }
168         }
169         for (int j = 0; j < size_; ++j)
170         {
171             if (board_[x][j] > 0)
172             {
173                 return false;
174             }
175         }
176         return true;
177     }
178 
179     //поиск расстановок слона
180     bool check_bishop(const int& x, const int& y)
181     {
182         bool check = true;
183 
184         int k_start_1 = -std::min(x, y);
185         int k_end_1 = std::min( size_ - x, size_ - y) - 1;
186 
187         int k_start_2 = -std::min( x, size_ - y - 1);
188         int k_end_2 = std::min( y, size_ - x - 1);
189 
190 
191         for (int k = k_start_1; k <= k_end_1; ++k)
192         {
193             check = check_coord(x + k, y + k) && check ;
194         }
195         for (int k = k_start_2; k <= k_end_2; ++k)
196         {
197             check = check_coord(x + k, y - k) && check;
198         }
199 
200         return check;
201     }
202 
203 
204     //поиск расстановок коня
205     bool check_knight(const int& x, const int& y)
206     {
207         bool check =
208             check_coord(x - 2, y - 1) &&
209             check_coord(x - 2, y + 1) &&
210             check_coord(x - 1, y - 2) &&
211             check_coord(x - 1, y + 2) &&
212             check_coord(x + 1, y - 2) &&
213             check_coord(x + 1, y + 2) &&
214             check_coord(x + 2, y - 1) &&
215             check_coord(x + 2, y + 1);
216         return check;
217     }
218 
219     //поиск расстановок королевы
220     bool check_queen(const int& x, const int& y)
221     {
222         return check_rook(x, y) && check_bishop(x, y);
223     }
224 
225    //функция поиска расстановок, в случае, когда на доске что-то стоит, вернуть ложь
226    //иначе поставить вернуть истину
227     bool check_coord(const int& x, const int& y)
228     {
229         if (x >= 0 && x < size_ && y >= 0 && y < size_)
230         {
231             if (board_[x][y] > 0)
232             {
233                 return false;
234             }
235         }
236         return true;
237     }
238 
239     // if board_[x][y] == 0
240     //     клетка свободна
241     // if board_[x][y] == s
242     //     фигура была поставлена на шаге S
243     // if board_[x][y] == -s
244     //     клетка свободна, но была попытка поставить фигуру на шаге S
245     int board_[MAX_SIZE][MAX_SIZE];
246     int size_;
247     int figures_on_board_;
248 };
249 
250 //функция расчета максимума для любой доски в зависимости от типа фигуры
251 int get_max_figures (const figure_type& figure, const int& size)
252 {
253     switch (figure)
254     {
255         case KING:
256             return (size + 1) / 2;
257         case QUEEN:
258             if (size <= 2)
259             {
260                 return 1;
261             }
262             else if (size == 3)
263             {
264                 return 2;
265             }
266             else
267             {
268                 return size;
269             }
270         case ROOK:
271             return size;
272         case BISHOP:
273             if (size == 1)
274             {
275                 return size;
276             }
277             else
278             {
279                 return 2 * (size - 1);
280             }
281         case KNIGHT:
282             if (size <= 2)
283             {
284                 return size * size;
285             }
286             else
287             {
288                 return (size * size + 1) / 2;
289             }
290         default:
291             return 1;
292     }
293 }
294 
295 //функция для расстановки максимального числа фигур на доске
296 void place_figures_for_max(chess_board &board, const figure_type& figure, const int& max_figures, int step)
297 {
298     ++step;
299     const int size = board.get_size();
300     for (int i = 0; i < size; ++i)
301     {
302         for (int j = 0; j < size; ++j)
303         {
304             //если мы можем поставить фигуру, то добавляем к максимуму единицу и запускаем цикл снова
305             if (board.put_figure(figure, i, j, step))
306             {
307                 //если число фигур на доске достигло максимума, то вывести доску
308                 if (board.get_figures_number() == max_figures)
309                 {
310                     board.print();
311                 }
312                 //если число фигур не достигло максимума, продолжить выполнение функции
313                 else
314                 {
315                     place_figures_for_max(board, figure, max_figures, step);
316                 }
317                 board.remove_figure(i, j);
318             }
319         }
320     }
321 }
322 
323 //функция, принимающая ввод с клавиатуры как строковый тип данных
324 figure_type get_figure_type(const std::string& str)
325 {
326     using namespace std;
327 
328     figure_type figure;
329     if (str == string("king"))
330     {
331         figure = KING;}
332     else if (str == string("queen"))
333     {
334         figure = QUEEN;}
335     else if (str == string("rook"))
336     {
337         figure = ROOK;
338     }
339     else if (str == string("bishop"))
340     {
341         figure = BISHOP;
342     }
343     else if (str == string("knight"))
344     {
345        figure = KNIGHT;
346     }
347     //вывести ошибку в случае неверного ввода
348     else
349     {
350         cout << "wrong figure type" << endl;
351         throw string("wrong figure type");
352     }
353 
354     return figure;
355 }
356 
357 int main()
358 {
359     //использовать стандартное пространств имен
360     using namespace std;
361 
362     int size;
363     string type_of_figure;
364     string type_of_action;
365     figure_type figure;
366 
367     cout << "Возможные фигуры: king, queen, rook, bishop, knight" << endl;
368     cout << "Возможные действия: max, placing" << endl;
369     cout << "----------------------------------------------------" << endl;
370 
371     cout <<"Введите размер доски: ";
372     cin >> size;
373     chess_board board(size);
374 
375     cout << "Введите тип фигуры: ";
376     cin >> type_of_figure;
377     figure = get_figure_type(type_of_figure);
378 
379     cout << "Введите необходимое действие: ";
380     cin >> type_of_action;
381 
382     if (type_of_action == string("max"))
383     {
384 
385         int max_figures = get_max_figures(figure, size);
386         cout << "Max figures: " << max_figures << endl;
387 
388         cout << "Хотите ли вы просмотреть все варианты? (yes/no) ";
389         string answer;
390         cin >> answer;
391         //если нужно вывести все расстановки, то применить непосредственно функцию поиска расстановок максимума
392         if (answer == string("yes"))
393         {
394             int step = 0;
395             place_figures_for_max(board, figure, max_figures, step);
396         }
397     }
398     //иначе если нужно расставить определенное количество фигур, то применить функцию поиска расстановок
399     //относительно введенного числа
400     else if (type_of_action == string("placing"))
401     {
402         int figures_to_place;
403         cout << "Сколько фигур нужно расставить: ";
404         cin >> figures_to_place;
405 
406         int step = 0;
407         place_figures_for_max(board, figure, figures_to_place, step);
408     }
409     //иначе вывести ошибку действия
410     else
411     {
412         cout << "wrong type of action" << endl;
413         throw string("wrong type of action");
414     }
415 
416     return 0;
417 }

Андреева Полина

Краткое описание алгоритма:если шахматную доску представить в виде одной строчки(вторую поставить следом за первой, третью за второй и тд), то получится двоичное число. Максимальное число которое может получиться если 111...111 перевести в десятичное ,это число М*М. Тогда абсолютно ВСЕ варианты расстановки фигур это двоичные записи чисел от 0 до М*М. В программе есть цикл, который рассматривает каждый вариант для числа от 0 до М*М, переводит его в двоичную форму. Программа рассматривает каждую клетку, где стоит фигура. Если эта фигура бьет других, то цикл прерывается, нам такой вариант не подходит. Если никакая фигура не бьет никакую другую, то идет подсчет количества фигур на доске. Если фигур столько, сколько нужно, то вывод на экран.

Инструкция: На экране показано соответствие каждому номеру типа фигуры. Пользователь выбирает тип фигуры, испольуя номер. Дальше нужно ввести размер доски. Затем на экране появляется два варианта количества фигур на доске: максимальное или введенное пользователем. Пользователь выбирает вариант. Если второй, то затем надо будет ввести количество фигур. Программа

Бальцер Анастасия

Краткое описание алгоритма: Для каждой фигуры написана отдельная функция, выполняющая поиск расстановок. После выбора типа фигуры, соответствующая функция выполняет поиск возможных расстановок. Она проходя по строкам двумерного массива пытается поставить фигуру в каждую клетку. Проходя по массиву она маркирует клетки, ставит 0 (если клетка свободна), 1 (если клетка находится под ударом), 2 (если клетка занята). Программа аналитически считает максимальное количество фигур для заданного размера доски, возможное число расстановок для заданных типа фигуры, размера доски и количества фигур.

Инструкция: При запуске программы появляется меню, в котором каждому типу фигуры сопоставлен номер, с помощью которого пользователь и выбирает тип фигуры. Затем пользователю на выбор предлагается 2 режима работы программы: первый выводит число возможных расстановок на экран, а список возможных расстановок в отдельный файл (при этом пользователь дополнительно выбирает число фигур); второй выводит на экран максимальное число фигур выбранного типа, которые можно расставить на заданной доске.

Посмотреть программу можно тут