Информатика: Расстановка шахматных фигур — различия между версиями

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

<syntaxhighlight lang="cpp" line start="1" enclose="div">

1. include <iostream>
2. include <math.h>
3. include <cmath>

using namespace std;

int n,type, *a, *stak, variant, maxst = 0;

void king(int x, int &top) //отметить битые клетки королем {

   // 012
   // 345
   // 678

   //0
   if (((x % n) > 1) && ((x / n) > 1))
   {
       int ii = x - n - 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   //1
   if ((x / n) > 0)
   {
       int ii = x - n;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   //2
   if (((x % n) < (n - 1)) && ((x / n) > 0))
   {
       int ii = x - n + 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   //3
   if ((x % n) > 0)
   {
       int ii = x - 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   //5
   if ((x % n) < (n - 1))
   {
       int ii = x + 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   //6
   if (((x % n ) > 0) && ((x / n) < (n - 1)))
   {
       int ii = x + n - 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   //7
   if ((x / n ) < (n - 1))
   {
       int ii = x + n;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   //8
   if (((x % n ) < (n - 1)) && ((x / n) < (n - 1)))
   {
       int ii = x + n + 1;
   if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

}

void bishop(int x, int &top) //отметить битые клетки слоном {

   //вверх влево
   for (int i = (x - (n + 1)); ((i >= 0) && ((i%n) != (n-1))); i -= (n+1))
   {
       if (a[i] != -2)
       {
           a[i]++;
           stak[top] = i;
           top++;
       }
   }

   //вниз вправо
   for (int i = (x + (n + 1)); ((i < n*n) && ((i%n) != 0)); i += (n+1))
   {
       if (a[i] != -2)
       {
           a[i]++;
           stak[top] = i;
           top++;
       }
   }

   //вверх вправо
   for (int i = x - (n - 1); ((i >= 0) && ((i%n) != 0)); i -= (n-1))
   {
       if (a[i] != -2)
       {
           a[i]++;
           stak[top] = i;
           top++;
       }
   }

   //вниз влево
   for (int i = x + (n - 1); ((i < n*n) && ((i%n) != (n-1))); i += (n-1))
   {
       if (a[i] != -2)
       {
           a[i]++;
           stak[top] = i;
           top++;
       }
   }

}

void knight(int x, int &top) //отметить битые клетки конем {

   if (((x%n) > 0) && (x/n) > 1)
   {
       int ii = x - 2*n - 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   if (((x%n) > 1) && (x/n) > 0)
   {
       int ii = x - n - 2;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   if (((x%n) > 1) && (x/n) < (n - 1))
   {
       int ii = x + n - 2;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   if (((x%n) > 0) && (x/n) < (n - 2))
   {
       int ii = x + 2*n - 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   if (((x%n) < (n - 1)) && (x/n) < (n - 2))
   {
       int ii = x + 2*n + 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   if (((x%n) < (n - 2)) && (x/n) < (n - 1))
   {
       int ii = x + n + 2;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   if (((x%n) < (n - 2)) && (x/n) < 0)
   {
       int ii = x - n + 2;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

   if (((x%n) < (n - 1)) && (x/n) < 1)
   {
       int ii = x - 2*n + 1;
       if (a[ii] != -2)
       {
           a[ii]++;
           stak[top] = ii;
           top++;
       }
   }

}

void rook(int x, int &top) //отметить битые клетки ладьей {

   int k = x - (x % n);
   while ((k/n) == (x/n))
   {

       if ((k != x) && (a[k] != -2))
       {
           a[k]++;
           stak[top] = k;
           top++;
       }
       k ++;
   }

   k = (x % n);
   while (((k/n)) != n)
   {
       if ((k != x) && (a[k] != -2))
       {
           a[k]++;
           stak[top] = k;
           top++;
       }
       k += n;
   }

} void set_figure(int x, int &top) //ставим фигуры на доску {

   //отмечаем "битые" клетки
   switch (type)
   {

//король

       case 1:
       {
           king(x,top);
           break;
       }

//слон case 2: { bishop(x,top);

           break;

}

//конь case 3: { knight(x,top); break; } //ладья

       case 4:
       {
           rook(x,top);
           break;
       }
       //ферзь
       case 5:
       {
           rook(x,top);
           bishop(x,top);
           break;
       }
   }

   //отмечаем,что в данной клетке стоит фигура

a[x] = -1;

   stak[top] = x;
   top++;

}

void step(int top,int x,int st) { int xtop = top; switch (variant) { case 1: { if (st != (n - 1)) { set_figure(x,top); for (int i = 0; i < (n*n); i++) if (a[i] == 0) step(top,i,st + 1); } else { set_figure(x,top);

               cout << endl;

for (int i = 0; i < (n*n); i++) { cout.width(3); if (((i % n) == 0) && (i != 0)) cout << endl; if (a[i] == -1) cout << 1; else cout << 0; } cout << endl; } break; } case 2: { set_figure(x,top); if ((st+1) > maxst) maxst = st + 1; for (int i = 0; i < (n*n); i++) if (a[i] == 0) step(top,i,st+1); break; } }

// обратный ход

   for (int i = xtop; i < top; i++)
   {
       if ((a[stak[i]] != -1) && (a[stak[i]] != -2))
           a[stak[i]]--;
       else
           //не забываем отметить,что фигура уже здесь стояла(чтобы избежать повторов)
           if (a[stak[i]] == -1)
               a[stak[i]] = -2;
//       cerr << " Back "  << stak[i] << endl;
   }

}

int main() {

   //cin >> n >> type >> variant;
   n = 5;
   type = 4;

variant = 1;

   a    = new int[n*n];
   stak = new int[n*n*4];

   for (int i = 0; i < (n*n); i++)
   {
       for (int j = 0; j < (n*n); j++)
           a[j] = 0;
       if (variant == 1)
           cout << "__________________________________" << endl;
       step(0,i,0);
   }

if (variant == 2) cout << maxst;

   return 0;