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

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
Строка 859: Строка 859:
 
'''Инструкция''': На экране показано соответствие каждому номеру типа фигуры. Пользователь выбирает тип фигуры, испольуя номер. Дальше нужно ввести размер доски. Затем на экране появляется два варианта количества фигур на доске: максимальное или введенное пользователем. Пользователь выбирает вариант. Если второй, то затем надо будет ввести количество фигур.
 
'''Инструкция''': На экране показано соответствие каждому номеру типа фигуры. Пользователь выбирает тип фигуры, испольуя номер. Дальше нужно ввести размер доски. Затем на экране появляется два варианта количества фигур на доске: максимальное или введенное пользователем. Пользователь выбирает вариант. Если второй, то затем надо будет ввести количество фигур.
 
[http://tm.spbstu.ru/Файл:ШахматыАП.rar Программа]
 
[http://tm.spbstu.ru/Файл:ШахматыАП.rar Программа]
 +
 +
<div class="mw-collapsible mw-collapsed" style="width:100%" >
 +
<syntaxhighlight lang="cpp" line start="1" enclose="div">
 +
#include <cstring>
 +
#include <iostream>
 +
#include"math.h"
 +
#include <fstream>
 +
using namespace std;
 +
 +
int M, N;  // M-размер доски, N-коичество шахмат.
 +
int    sum;//нужно в процессе для подсчета количества шахмат
 +
int **ChessBoard= new int* [M];
 +
 +
void ChessBoards(int k) //создание доски, k-число, которое переводим в двоичную запись, чтобы отобразить на доске расстановку фигур, 1-фигура есть, 0-нет.
 +
{
 +
    for (int i=0; i<M; i++) //создание массива
 +
    {
 +
        ChessBoard[i] = new int[M];
 +
    }
 +
    for (int x=(M-1); x>=0; x=x-1)//заполнение массива фигурами (переводя k в двоичную форму)
 +
    {
 +
        for (int y=(M-1); y>=0; y=y-1)
 +
        {
 +
            ChessBoard[x][y]=(k%2);
 +
            k=k/2;
 +
        }
 +
    }
 +
}
 +
void print (char filename[] ) ///создание функции вывода массива в файл
 +
    {
 +
        ofstream fout(filename, ios::app);
 +
 +
        for (int x=0; x<M; ++x)
 +
        {
 +
            for(int y=0; y<M; ++y)
 +
            {
 +
                fout << ChessBoard[x][y]<<" "; ///вывод массива в файл
 +
            }
 +
            fout <<'\n';
 +
 +
        }
 +
        fout <<"\n\n";
 +
 +
        fout.close();
 +
    }
 +
 +
 +
 +
bool CheckHorse(int x, int y)//проверка для коня в клетке с номером x, y
 +
{
 +
 +
    if (((x+1)<M) && ((y+2)<M) && (ChessBoard[x+1][y+2]==1))//если в клетке, куда может сходить конь (х+1,у+2) уже есть фигура, то этот вариант не подходит, так как один конь бьет другого.
 +
    {
 +
        return false;
 +
 +
    }
 +
    else if (((x+1)<M ) && ((y-2)>=0) && (ChessBoard[x+1][y-2]==1))//то же самое и в остальных случаях проверяем бьет ли один конь другого.
 +
    {
 +
        return false;
 +
 +
    }
 +
    else if (((x-1)>=0) && ((y+2)<M) && (ChessBoard[x-1][y+2]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x-1)>=0) && ((y-2)>=0) && (ChessBoard[x-1][y-2]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x+2)<M) && ((y+1)<M) && (ChessBoard[x+2][y+1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x+2)<M ) && ((y-1)>=0) && (ChessBoard[x+2][y-1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x-2)>=0 ) && ((y+1)<M) && (ChessBoard[x-2][y+1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x-2)>=0 ) && ((y-1)>=0) && (ChessBoard[x-2][y-1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else //в итоге, если конь, стоящий в данной клетке никого не бьет, то этот вариант подходит
 +
    {
 +
        return true;
 +
    }
 +
}
 +
 +
int Horse(int k)//k-то число которое нужно будет перевести в двоичную форму, это делается в main'е
 +
//в этой функции считаем количество фигур, если он равно введенному  или максимальному,то доска подходит и выводится в файл (все это в main'е)
 +
{
 +
    for (int x=0; x<M; x++)
 +
    {
 +
        int y;
 +
        for (y=0; y<M; y++)
 +
        {
 +
            if (ChessBoard[x][y]==1)//если в данной клетке стоит конь, то нужно проверить,
 +
            // бьет оно кого-то или нет...
 +
            //если в клетке нет коня, то ее проверять не нужно
 +
            {
 +
                if (CheckHorse(x,y))//...делаем это с помощью этой функции,если конь в данной клетке х;у 
 +
                //никого не бьет, то прибавляем 1 к количеству шахмат на доске и считаем дальше 
 +
                {
 +
                    sum=sum+1;
 +
                }
 +
                else //а если бьет, то выходим из цикла, на данной этапе выйдем только из внуреннего
 +
                {
 +
                    sum=0;//количество фигур обнуляем
 +
                    break;
 +
                }
 +
            }
 +
        }
 +
        if (y<M)//если из внутреннего цикла вышли раньше, значит у досчитался не до конца,
 +
        //то есть он меньше своего максимального значения М
 +
        {
 +
           
 +
            break;//тогда выходим и из внешнего цикла
 +
        }
 +
    }
 +
    return sum; //возвращаем количество фигур
 +
}
 +
 +
bool CheckKing(int x, int y) //все то же самое для проверки короля, стоящего в клетке х,у
 +
{
 +
 +
    if (((x+1)<M) && ((y+1)<M) && (ChessBoard[x+1][y+1])==1)//если в клетке куда может сходить король
 +
    //уже есть фигура, то клетка не подходит и т.д
 +
    {
 +
        return false;
 +
 +
    }
 +
    else if (((x+1)<M ) && (ChessBoard[x+1][y]==1))
 +
    {
 +
        return false;
 +
 +
    }
 +
    else if (((x+1)<M) && ((y-1)>=0) && (ChessBoard[x+1][y-1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x-1)>=0) && ((y-1)>=0) && (ChessBoard[x-1][y-1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x-1)>=0) && ((y+1)<M) && (ChessBoard[x-1][y+1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((x-1)>=0) &&  (ChessBoard[x-1][y]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((y+1)<M) && (ChessBoard[x][y+1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else if (((y-1)>=0) && (ChessBoard[x][y-1]==1))
 +
    {
 +
        return false;
 +
    }
 +
    else
 +
    {
 +
        return true;
 +
    }
 +
}
 +
 +
int King(int k) //так же как и для коня, проверяем каждую клетку
 +
//подходит-прибавляем к количеству фигур sum единичку, нет-обнуляем сумму и выходим из цикла
 +
{
 +
    for (int x=0; x<M; x++)
 +
    {
 +
        int y;
 +
        for (y=0; y<M; y++)
 +
        {
 +
            if (ChessBoard[x][y]==1)
 +
            {
 +
                if (CheckKing(x,y))
 +
                {
 +
                    sum=sum+1;
 +
                }
 +
                else
 +
                {
 +
                    sum=0;
 +
                    break;
 +
                }
 +
            }
 +
        }
 +
        if (y<M)
 +
        {
 +
            break;
 +
        }
 +
    }
 +
    return sum;
 +
}
 +
 +
int CheckQueen(int x, int y)///проверка для королевы, принцип тот же, королева стит в клеке x,y
 +
///1 значит как true в bool (как в коне или короле), 0 - false
 +
{ int returnn=1;//начала true, дальше если будет false, то return примет значение 0, а если все пдходит
 +
///то так и стается 1
 +
int m;
 +
    for (m=1; m<M; m++)
 +
  { //проверяем для диагоналей
 +
    ///если по диагонале клетки х,у стоит еще королва, то такой вариант не подходит, выходим из цикла
 +
    ///разбито на 4 услвия, так как если не разбивать, то клетка в кторой стоит данная королева
 +
    ///тоже будет считаться и выходить из цикла
 +
      if (((x+m)<M)&&((y+m)<M))
 +
      {
 +
          if (ChessBoard[x+m][y+m]==1)
 +
          {returnn=0;
 +
          break;
 +
          }
 +
      }
 +
      if (((x-m)>=0)&&((y+m)<M))
 +
      {
 +
          if (ChessBoard[x-m][y+m]==1)
 +
          {returnn=0;
 +
          break;}
 +
      }
 +
      if (((x+m)<M)&&((y-m)>=0))
 +
      {
 +
          if (ChessBoard[x+m][y-m]==1)
 +
        {returnn=0;
 +
          break;}
 +
      }
 +
      if (((x-m)>=0)&&((y-m)>=0))
 +
      { if (ChessBoard[x-m][y-m]==1)
 +
          {returnn=0;
 +
          break;}
 +
      }
 +
      if (m!=x) ///тут считаем по вертикали и горизонтали, так как длаем в цикле для m, то m меняется
 +
        ///и в какой-то момент может стать х, и тогда роверятьбуде клетку в которой стоит ДАННАЯ и выходить
 +
        ///это не нужно так что выходим только если m не равен x
 +
        {
 +
            if (ChessBoard[m][y]==1) //если по горизонтали есть какая-о клетка, где стоит королева, то выходим
 +
            {
 +
                returnn=0;
 +
                break;
 +
            }
 +
        }
 +
        if (m!=y)//то же по вертикали
 +
        {
 +
          if (ChessBoard[x][m]==1)
 +
            {
 +
                returnn=0;
 +
                break;
 +
            }
 +
        }
 +
  }
 +
  return returnn;
 +
}
 +
 +
int Queen(int k)//тут также как и для коня и короля
 +
{
 +
for (int x=0; x<M; x++)
 +
    {
 +
        int y;
 +
        for (y=0; y<M; y++)
 +
        {
 +
            if (ChessBoard[x][y]==1)//если в клетке королева, проверяем подходи ли она нам
 +
            {
 +
                if (CheckQueen(x,y))
 +
                {
 +
                    sum=sum+1;
 +
                }
 +
                else
 +
                {
 +
                    sum=0;
 +
                    break;
 +
                }
 +
            }
 +
        }
 +
        if (y<M)
 +
        {
 +
            break;
 +
        }
 +
    }
 +
    return sum;
 +
}
 +
 +
int CheckRook(int x, int y)///ладья, просто берем ту часть из проверки королевы, где проверка по горизонтали и вертикали
 +
{ int returnn=1;
 +
int m;
 +
    for (m=0; m<M; m++)
 +
 +
    {
 +
        if (m!=x)
 +
        {
 +
            if (ChessBoard[m][y]==1)
 +
            {
 +
                returnn=0;
 +
                break;
 +
            }
 +
        }
 +
        if (m!=y)
 +
        {
 +
          if (ChessBoard[x][m]==1)
 +
            {
 +
                returnn=0;
 +
                break;
 +
            }
 +
        }
 +
    }
 +
 +
 +
      return returnn;
 +
}
 +
 +
int Rook(int k)//все то же самое, количество фигур на доске
 +
{
 +
    for (int x=0; x<M; x++)
 +
    {
 +
        int y;
 +
        for (y=0; y<M; y++)
 +
        {
 +
            if (ChessBoard[x][y]==1)
 +
            {
 +
                if (CheckRook(x,y)==1)
 +
                {
 +
                    sum=sum+1;
 +
 +
                }
 +
                else
 +
                {
 +
                    sum=0;
 +
                    break;
 +
                }
 +
            }
 +
        }
 +
        if (y<M)
 +
        {
 +
            break;
 +
        }
 +
    }
 +
 +
    return sum;
 +
}
 +
 +
int CheckElephant(int x, int y)//для слона берем ту часть прроверки королевы, где по диагонали
 +
{ int returnn=1;
 +
  for (int i=1; i<M; i++)
 +
  {
 +
      if (((x+i)<M)&&((y+i)<M))
 +
      {
 +
          if (ChessBoard[x+i][y+i]==1)
 +
          {returnn=0;
 +
          break;
 +
          }
 +
      }
 +
      if (((x-i)>=0)&&((y+i)<M))
 +
      {
 +
          if (ChessBoard[x-i][y+i]==1)
 +
          {returnn=0;
 +
          break;}
 +
      }
 +
      if (((x+i)<M)&&((y-i)>=0))
 +
      {if (ChessBoard[x+i][y-i]==1)
 +
        {returnn=0;
 +
          break;}
 +
      }
 +
      if (((x-i)>=0)&&((y-i)>=0))
 +
      { if (ChessBoard[x-i][y-i]==1)
 +
          {returnn=0;
 +
          break;}
 +
      }
 +
  }
 +
  return returnn;
 +
}
 +
 +
int Elephant(int k)///считаем кличесво фигур
 +
{
 +
for (int x=0; x<M; x++)
 +
    {
 +
        int y;
 +
        for (y=0; y<M; y++)
 +
        {
 +
            if (ChessBoard[x][y]==1)
 +
            {
 +
                if (CheckElephant(x,y))
 +
                {
 +
                    sum=sum+1;
 +
                }
 +
                else
 +
                {
 +
                    sum=0;
 +
                    break;
 +
                }
 +
            }
 +
        }
 +
        if (y<M)
 +
        {
 +
            break;
 +
        }
 +
    }
 +
    return sum;
 +
}
 +
 +
int main ()
 +
{
 +
    ofstream MyFile("MyFile", ios::trunc);
 +
    MyFile.close(); // очищаем файл, чтоб при новой записи не было из рошлого запуска
 +
 +
int figure, z;
 +
    cout<<"enter a figure 1-queen, 2-king, 3-rook , 4-horse or 5-elephant ";
 +
    cin>>figure;///тип фигуры, 1 - королевА, 2-король,3-ладья,4-конь,6-слон
 +
      cout << "\n enter a size of a board M - even number ";///ввести ЧЕТНЫЙ размер доски М
 +
    cin >> M;
 +
    if ( M%2 != 0)///проверка М на четность, с помощью остатка от деления на 2
 +
    {
 +
        while (M%2 != 0)
 +
        {
 +
            cout<<" you need EVEN number, enter one more time ";
 +
            cin>>M;
 +
        }
 +
    }
 +
 +
    cout<<"\n choose  1- max amount or 2 - your amount of figures ";
 +
    cin>>z;///z-один из вариантов 1-максимаьное число фигур на доске,2-пользователь сам вводит
 +
 +
    switch (figure)///выбираем фигуру
 +
    {
 +
    case 1:///королева
 +
    {
 +
        if (z==2)///пользоватеь сам вводит количество
 +
        {
 +
            cout<<"\n enter an amount of figures ";
 +
            cin >> N;///ввести количество
 +
            if (N>M)///проверка на то, сможет ли такое количество уместиться на доске в правильном виде
 +
            {
 +
                while (N>M)
 +
                {
 +
                    cout<<" too many figures, enter one more time ";
 +
                    cin>>N;
 +
                }
 +
            }
 +
            ///вот ниже i- те числа которые нужно перевести в двоичную форму
 +
            for (int i=0; i<=pow(2,(M*M)); i++)///каждый i-новый вариант расстановик фигур
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Queen(k)==N)///если в данной варианте фигур столько. сколько ввел пользователь, то выводим
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        else ///вариант максимального числа фигур на доске
 +
        {  ///так же как и в предыдущем пункте, только количество фигур N максимально,
 +
            /// в случае королевы оно равно размеру доски 
 +
            N=M;
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Queen(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
 +
        break;
 +
    }
 +
    case 2:///то же самое для короля
 +
    {
 +
        if (z==2)
 +
        {
 +
            cout<<"\n enter an amount of figures ";
 +
            cin >> N;
 +
              if ( N>(M*M)/4)
 +
            {
 +
                while (N>(M*M)/4)
 +
                {
 +
                    cout<<" too many figures, enter one more time ";
 +
                    cin>>N;
 +
                }
 +
            }
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (King(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
else
 +
        {
 +
            N=(M*M)/4;
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (King(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        break;
 +
    }
 +
    case 3:///для ладьи
 +
    {
 +
        if (z==2)
 +
        {
 +
            cout<<"\n enter an amount of figures ";
 +
            cin >> N;
 +
              if (N>M)
 +
            {
 +
                while (N>M)
 +
                {
 +
                    cout<<" too many figures, enter one more time ";
 +
                    cin>>N;
 +
                }
 +
            }
 +
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Rook(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        else
 +
        {
 +
            N=M;
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Rook(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        break;
 +
    }
 +
    case 4:///конь
 +
    {
 +
        if (z==2)
 +
        {
 +
            cout<<"\n enter an amount of figures ";
 +
            cin >> N;
 +
              if (N>(M*M)/2)
 +
            {
 +
                while (N>(M*M)/2)
 +
                {
 +
                    cout<<" too many figures, enter one more time ";
 +
                    cin>>N;
 +
                }
 +
            }
 +
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Horse(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        else
 +
        {
 +
            N=(M*M)/2;
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Horse(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        break;
 +
    }
 +
    case 5:///слон
 +
    {
 +
        if (z==2)
 +
        {
 +
            cout<<"\n enter an amount of figures ";
 +
            cin >> N;
 +
                if (N>2*M-2)
 +
            {
 +
                while (N>2*M-2)
 +
                {
 +
                    cout<<" too many figures, enter one more time ";
 +
                    cin>>N;
 +
                }
 +
            }
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Elephant(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        else
 +
        {
 +
            N=2*M-2;
 +
            for (int i=0; i<=pow(2,(M*M)); i++)
 +
            {
 +
                sum=0;
 +
                int k=i;
 +
                ChessBoards(k);
 +
                if (Elephant(k)==N)
 +
                {
 +
                    print("MyFile");
 +
                }
 +
            }
 +
        }
 +
        break;
 +
    }
 +
    default : ///а это еси пользоватеь ввел цифру, которая не соответстует ни одной фигуре
 +
    {
 +
        cout<<"NOOOOO";
 +
        break;
 +
    }
 +
    };
 +
 +
 +
    return 0;
 +
    }
 +
</syntaxhighlight>
 +
</div>
  
 
'''[[Бальцер Анастасия]]'''
 
'''[[Бальцер Анастасия]]'''
Строка 867: Строка 1512:
  
 
Посмотреть программу можно [http://tm.spbstu.ru/Файл:Расстановка.zip тут]
 
Посмотреть программу можно [http://tm.spbstu.ru/Файл:Расстановка.zip тут]
 +
  
  

Версия 14:13, 17 января 2016

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

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

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

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

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


Иванова Яна

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

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

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

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

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

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

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

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

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

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

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

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


Васильева Анастасия

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

Инструкция: Сначала программа просит выбрать фигуру, с которой будем работать. Затем 2 варианта развития событий: 1 - вывод в файл всех расстановок, 2 - максимальное количество фигур. В зависимости от выбора, в первом случае еще нужно ввести количество фигур, и программа запишет в файл все возможные варианты и выведет на экран число расстановок, а во втором - на экране появится максимальное кол-во фигур. Скачать можно тут.

Белоусова Екатерина

Краткое описание алгоритма: доска представлена в виде динамического массива, заполненного 1 и 0. 1-стоит фигура, 0-пустое место. Программа при помощи рекурсии вызывает функцию, которая ставит фигуру в пустую клетку и проверяет, находится ли эта фигура под ударом других.

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

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

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