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

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
Строка 3743: Строка 3743:
 
</syntaxhighlight>
 
</syntaxhighlight>
 
</div>
 
</div>
 +
 +
'''[[Савельева Ольга]]'''
 +
 +
 +
'''Инструкция''': В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей: либо максимальное число вариантов, либо посмотреть наглядно на варианты. Человек вводит размер доски и тип фигуры.
 +
 +
Скачать программу можно  [http://tm.spbstu.ru/:File:Шахматы0001.zip    ]
 +
 +
<div class="mw-collapsible mw-collapsed" style="width:100%" >
 +
<syntaxhighlight lang="cpp" line start="1" enclose="div">
 +
 +
#define windows
 +
 +
#include <stdio.h>
 +
#include <vector>
 +
 +
#ifdef windows
 +
#include <windows.h>
 +
#endif  // windows
 +
 +
using namespace std;
 +
 +
#ifdef windows
 +
HANDLE hCon;
 +
#endif // windows
 +
 +
unsigned fact(int n)  //factorial of a number
 +
{
 +
    unsigned long long ret = 1;
 +
    for(int i = 2; i <= n; i++)
 +
        ret *= i;
 +
    return ret;
 +
}
 +
 +
struct desk
 +
{
 +
    char **deskFigures, **deskOccupy;  //desk with figures, desk with occupation counter for each cell
 +
    int x, y, size, a, f;  //pointer position(x, y), size of the desk, amount of prints, amount of figures
 +
    vector<pair<int, int> > *s; //stack of placed figures
 +
    bool stackIsUsed;  //if stack is needed
 +
    desk(int size, bool stackIsUsed = true):x(0), y(0), size(size), a(0), f(0), stackIsUsed(stackIsUsed)
 +
    {
 +
        deskFigures = new char*[size];
 +
        for(int i = 0; i < size; i++)
 +
            deskFigures[i] = new char[size];
 +
        deskOccupy = new char*[size];
 +
        for(int i = 0; i < size; i++)
 +
            deskOccupy[i] = new char[size];
 +
        if(stackIsUsed)
 +
            s = new vector<pair<int, int> >;
 +
        clear();
 +
    }
 +
    ~desk()
 +
    {
 +
        for(int i = 0; i < size; i++)
 +
            delete deskFigures[i];
 +
        delete deskFigures;
 +
        for(int i = 0; i < size; i++)
 +
            delete deskOccupy[i];
 +
        delete deskOccupy;
 +
        if(stackIsUsed)
 +
            delete s;
 +
    }
 +
    void setKnight(int x, int y, int z) //increase all cells occupied by knight at (x, y) on z
 +
    {
 +
        if(x + 2 < size)
 +
        {
 +
            if(y - 1 >= 0)
 +
                deskOccupy[x + 2][y - 1] += z;
 +
            if(y + 1 < size)
 +
                deskOccupy[x + 2][y + 1] += z;
 +
        }
 +
        if(y + 2 < size)
 +
        {
 +
            if(x - 1 >= 0)
 +
                deskOccupy[x - 1][y + 2] += z;
 +
            if(x + 1 < size)
 +
                deskOccupy[x + 1][y + 2] += z;
 +
        }
 +
        if(x - 2 >= 0)
 +
        {
 +
            if(y - 1 >= 0)
 +
                deskOccupy[x - 2][y - 1] += z;
 +
            if(y + 1 < size)
 +
                deskOccupy[x - 2][y + 1] += z;
 +
        }
 +
        if(y - 2 >= 0)
 +
        {
 +
            if(x - 1 >= 0)
 +
                deskOccupy[x - 1][y - 2] += z;
 +
            if(x + 1 < size)
 +
                deskOccupy[x + 1][y - 2] += z;
 +
        }
 +
    }
 +
    void setBishop(int x, int y, int z) //increase all cells occupied by bishop at (x, y) on z
 +
    {
 +
        for(int ix = 0, iy1 = y - x, iy2 = y + x; ix < size; ix++, iy1++, iy2--)
 +
            if(ix != x)
 +
            {
 +
                if((iy1 >= 0)and(iy1 < size))
 +
                    deskOccupy[ix][iy1] += z;
 +
                if((iy2 >= 0)and(iy2 < size))
 +
                    deskOccupy[ix][iy2] += z;
 +
            }
 +
    }
 +
    void setRook(int x, int y, int z)  //increase all cells occupied by rook at (x, y) on z
 +
    {
 +
        for(int i = 0; i < size; i++)
 +
        {
 +
            if(i != x)
 +
                deskOccupy[i][y] += z;
 +
            if(i != y)
 +
                deskOccupy[x][i] += z;
 +
        }
 +
    }
 +
    void setKing(int x, int y, int z)  //increase all cells occupied by king at (x, y) on z
 +
    {
 +
        for(int ix = x - 1; ix <= x + 1; ix++)
 +
            for(int iy = y - 1; iy <= y + 1; iy++)
 +
                if((ix >= 0)and(ix < size)and(iy >= 0)and(iy < size)and((ix != 0)or(iy != 0)))
 +
                    deskOccupy[ix][iy] += z;
 +
    }
 +
    void setFigure(int x, int y, int z, char figure)    //increase all cells occupied by figure
 +
                                                        //and (x, y) on z
 +
    {
 +
        deskOccupy[x][y] += z;
 +
        switch(figure)
 +
        {
 +
            case 'N':
 +
                setKnight(x, y, z);
 +
                break;
 +
            case 'B':
 +
                setBishop(x, y, z);
 +
                break;
 +
            case 'R':
 +
                setRook(x, y, z);
 +
                break;
 +
            case 'Q':
 +
                setBishop(x, y, z);
 +
                setRook(x, y, z);
 +
                break;
 +
            case 'K':
 +
                setKing(x, y, z);
 +
                break;
 +
        }
 +
    }
 +
    bool putFigure(int x, int y, char figure)  //place figure on desk and update occupied cells
 +
    {
 +
        if(deskFigures[x][y] > 0)
 +
            return false;
 +
        deskFigures[x][y] = figure;
 +
        if(stackIsUsed)
 +
            s -> push_back(make_pair(x, y));
 +
        setFigure(x, y, 1, figure);
 +
        f++;
 +
        return true;
 +
    }
 +
    int cellsLeft() //amount of cells after pointer
 +
    {
 +
        return (size - y) * size - x;
 +
    }
 +
    bool putNextFree(char figure)  //attempt to put figure on the next free(and not occupied) place
 +
    {
 +
        if(y >= size)
 +
            return false;
 +
        while(deskOccupy[x][y] > 0)
 +
        {
 +
            if(++x == size)
 +
            {
 +
                if(++y == size)
 +
                    return false;
 +
                x = 0;
 +
            }
 +
        }
 +
        return putFigure(x, y, figure);
 +
    }
 +
    void removeFigure(int x, int y) //remove figure from (x, y)
 +
    {
 +
        if(deskFigures[x][y]!=0)
 +
            setFigure(x, y, -1, deskFigures[x][y]);
 +
        deskFigures[x][y] = 0;
 +
        f--;
 +
    }
 +
    void removeBishop(int diag, bool color, bool left)  //remove bishop
 +
    {
 +
        if(color)  //true - white, false - black
 +
        {
 +
            if(diag > 0)    //diag - number of diagonal
 +
            {
 +
                int diff = left ? 0 : diag * 2;
 +
                removeFigure(diff, diag * 2 - diff);
 +
                removeFigure(size - diff - 1, size - diag * 2 + diff - 1);
 +
            }
 +
            else
 +
            if(left)    //determine position of the bishop on the diagonal
 +
                removeFigure(0, 0);
 +
            else
 +
                removeFigure(size - 1, size - 1);
 +
        }
 +
        else
 +
        {
 +
            if(diag > 0)
 +
            {
 +
                int diff = left ? 0 : diag * 2;
 +
                removeFigure(size - diff - 1, diag * 2 - diff);
 +
                removeFigure(diff, size - diag * 2 + diff - 1);
 +
            }
 +
            else
 +
            if(left)
 +
                removeFigure(0, size - 1);
 +
            else
 +
                removeFigure(size - 1, 0);
 +
        }
 +
    }
 +
    void putBishop(int diag, bool color, bool left) //place bishop
 +
    {
 +
        if(color)
 +
        {
 +
            if(diag > 0)
 +
            {
 +
                int diff = left ? 0 : diag * 2;
 +
                putFigure(diff, diag * 2 - diff, 'B');
 +
                putFigure(size - diff - 1, size - diag * 2 + diff - 1, 'B');
 +
            }
 +
            else
 +
            if(left)
 +
                putFigure(0, 0, 'B');
 +
            else
 +
                putFigure(size - 1, size - 1, 'B');
 +
        }
 +
        else
 +
        {
 +
            if(diag > 0)
 +
            {
 +
                int diff = left ? 0 : diag * 2;
 +
                putFigure(size - diff - 1, diag * 2 - diff, 'B');
 +
                putFigure(diff, size - diag * 2 + diff - 1, 'B');
 +
            }
 +
            else
 +
            if(left)
 +
                putFigure(0, size - 1, 'B');
 +
            else
 +
                putFigure(size - 1, 0, 'B');
 +
        }
 +
    }
 +
    void swapBishops(int diag, bool color, bool left)  //move pair bishops to another borders
 +
    {
 +
        removeBishop(diag, color, left);
 +
        putBishop(diag, color, not(left));
 +
    }
 +
    void figureBefore() //remove one figure from stack and change pointer to the next position after figure was placed
 +
    {
 +
        pair<int, int> c = s -> back();
 +
        s -> pop_back();
 +
        x = c.first;
 +
        y = c.second;
 +
        removeFigure(x, y);
 +
        if(++x == size)
 +
        {
 +
            x = 0;
 +
            y++;
 +
        }
 +
    }
 +
    void clear()    //clear the desk
 +
    {
 +
        for(int ix = 0; ix < size; ix++)
 +
            for(int iy = 0; iy < size; iy++)
 +
            {
 +
                deskFigures[ix][iy] = 0;
 +
                deskOccupy[ix][iy] = 0;
 +
            }
 +
        x = 0;
 +
        y = 0;
 +
        if(stackIsUsed)
 +
            s -> empty();
 +
        f = 0;
 +
    }
 +
    void show() //show the desk
 +
    {
 +
        a++;
 +
        printf("%i:\n", a);
 +
        #ifdef windows
 +
        unsigned background = 4;
 +
        #else
 +
        printf("\x1b[31m");
 +
        char background = 47;
 +
        #endif  //windows
 +
        for(int y = 0; y < size; y++)
 +
            for(int x = 0; x < size; x++)
 +
            {
 +
                #ifdef windows
 +
                SetConsoleTextAttribute(hCon, background);
 +
                #else
 +
                printf("\x1b[%dm", background);
 +
                #endif  //windows
 +
                if(deskFigures[x][y] == 0)
 +
                    putchar(' ');
 +
                else
 +
                    putchar(deskFigures[x][y]);
 +
                #ifdef windows
 +
                if(x < size - 1)
 +
                    background = background == 4 ? 116 : 4;
 +
                else
 +
                {
 +
                    SetConsoleTextAttribute(hCon, 7);
 +
                    putchar('\n');
 +
                }
 +
                #else
 +
                if(x < size - 1)
 +
                    background = background == 47 ? 40 : 47;
 +
                else
 +
                {
 +
                    printf("\x1b[0m\n");
 +
                    if(y < size - 1)
 +
                        printf("\x1b[31m");
 +
                }
 +
                #endif // windows
 +
            }
 +
    }
 +
};
 +
 +
int m = -1; //0 for number of arrangements, 1 for all variants
 +
 +
unsigned lookForFigure(int size, int amount, char figure, bool show = true) //brute-force
 +
{
 +
    desk *d  = new desk(size);
 +
    unsigned ret = 0;
 +
    while((d -> f > 0)or(d -> cellsLeft() >= amount))
 +
        if(not(d -> putNextFree(figure)))
 +
        {
 +
            if(d -> f == amount)
 +
            {
 +
                if(show)
 +
                    d -> show();
 +
                ret++;
 +
            }
 +
            d -> figureBefore();
 +
        }
 +
    delete d;
 +
    return ret;
 +
}
 +
 +
void lookForKnight(int size, int amount)    //arrangements of knights
 +
{
 +
    if(m == 0)
 +
    {
 +
        printf("Amount of arrangements: ");
 +
        if(size == 2)
 +
            printf("1\n");
 +
        else
 +
        if(size == 4)
 +
            printf("6\n");
 +
        else
 +
            printf("2\n");
 +
    }
 +
    else
 +
    {
 +
        desk *d = new desk(size);
 +
        if(size == 2)
 +
        {
 +
            d -> putFigure(0, 0, 'N');
 +
            d -> putFigure(0, 1, 'N');
 +
            d -> putFigure(1, 0, 'N');
 +
            d -> putFigure(1, 1, 'N');
 +
            d -> show();
 +
        }
 +
        else
 +
        if(size==4)
 +
            lookForFigure(size, amount, 'N');
 +
        else
 +
        {
 +
            for(int x = 0; x < size; x++)
 +
                for(int y = 0;y < size; y++)
 +
                    if(x + y % 2 == 0)
 +
                        d -> putFigure(x, y, 'N');
 +
            d -> show();
 +
            d -> clear();
 +
            for(int x = 0; x < size; x++)
 +
                for(int y = 0;y < size; y++)
 +
                    if(x + y % 2 == 1)
 +
                        d -> putFigure(x, y, 'N');
 +
            d -> show();
 +
        }
 +
    }
 +
}
 +
 +
void lookForBishop(int size, int amount)    //arrangements of bishops
 +
{
 +
    if(m == 0)
 +
        printf("Amount of arrangements: %u", (unsigned) 1 << size);
 +
    else
 +
    {
 +
        desk *d = new desk(size, false);
 +
        bool *b = new bool[size];
 +
        for(int dw = 0; dw < size/2; dw++)
 +
        {
 +
            d -> putBishop(dw, true, false);
 +
            d -> putBishop(dw, false, false);
 +
        }
 +
        int p = size - 1;
 +
        for(;;)
 +
        {
 +
            d -> show();
 +
            while(b[p])
 +
            {
 +
                d -> swapBishops(p % (size / 2), p < size / 2, true);
 +
                b[p--] = false;
 +
                if(p < 0)
 +
                    return;
 +
            }
 +
            b[p] = true;
 +
            d -> swapBishops(p % (size / 2), p < size / 2, false);
 +
            p = size - 1;
 +
        }
 +
    }
 +
}
 +
 +
void lookForRook(int size, int amount)  //arrangements of rooks
 +
{
 +
    if(m == 0)
 +
        printf("Amount of arrangements: %u", fact(size));
 +
    else
 +
        lookForFigure(size, amount, 'R');
 +
}
 +
 +
void lookForQueen(int size, int amount) //arrangements of queens
 +
{
 +
    if(m == 0)
 +
        printf("Amount of arrangements: %u", lookForFigure(size, amount, 'Q', false));
 +
    else
 +
        lookForFigure(size, amount, 'Q');
 +
}
 +
 +
void lookForKing(int size, int amount)  //arrangements of kings
 +
{
 +
    if(m == 0)
 +
        printf("Amount of arrangements: %u", lookForFigure(size, amount, 'K', false));
 +
    else
 +
        lookForFigure(size, amount, 'K');
 +
}
 +
 +
int main()
 +
{
 +
    int s = -1, f = -1; //s - size, f - figure
 +
    #ifdef windows
 +
    hCon = GetStdHandle(STD_OUTPUT_HANDLE);
 +
    #endif // windows
 +
    sizeInput:
 +
    printf("Enter size of the desk:\n");
 +
    scanf("%i", &s);
 +
    if((s<=0)or(s%2!=0))
 +
    {
 +
        printf("Size must be above 0 and even\n");
 +
        goto sizeInput;
 +
    }
 +
    modeInput:
 +
    printf("Enter mode:\n\t0: Print amount of results\n\t1: Print all results\n");
 +
    scanf("%i", &m);
 +
    if((m<0)or(m>1))
 +
    {
 +
        printf("Mode can be 0 or 1\n");
 +
        goto modeInput;
 +
    }
 +
    figureInput:
 +
    printf("Enter figures to be placed\n\t0: Knight (N)\n\t1: Bishop (B)\n\t2: Rook (R)\n\t3: Queen (Q)\n\t4: King (K)\n");
 +
    scanf("%i", &f);
 +
    if((f<0)or(f>4))
 +
    {
 +
        printf("Figure number ranges from 0 to 4\n");
 +
        goto figureInput;
 +
    }
 +
    switch(f)
 +
    {
 +
        case 0:
 +
            if(s==2)
 +
                lookForKnight(s, 4);
 +
            else
 +
                lookForKnight(s, s *s / 2);
 +
            break;
 +
        case 1:
 +
            lookForBishop(s, 2 * s - 2);
 +
            break;
 +
        case 2:
 +
            lookForRook(s, s);
 +
            break;
 +
        case 3:
 +
            if(s==2)
 +
                lookForQueen(s, 1);
 +
            else
 +
                lookForQueen(s, s);
 +
            break;
 +
        case 4:
 +
            lookForKing(s, (s / 2) * (s / 2));
 +
            break;
 +
    }
 +
    return 0;
 +
}
 +
 +
 +
 +
</syntaxhighlight>
 +
</div>
 +
  
 
'''[[Козловская Анна]]'''
 
'''[[Козловская Анна]]'''

Версия 00:54, 18 января 2016

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

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

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

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

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


Иванова Яна

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

Тимошенко Валентина

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

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

Скачать можно здесь. 

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




Александр Сюрис

Программа работает в двух режимах: поиск максимального числа фигур для заданного поля и количество возможных расстановок заданного числа фигур для заданного поля.

Алгоритм:

  1. Для поиска количества возможных расстановок заданного числа фигур для заданного поля – Проверяется, возможно ли поставить фигуру в данную клетку, рекурсивно перебирает для каждой клетки поля, как начальной клетки, все варианты расстановки заданного количества фигур относительно нее и выводит на экран все расстановки, которые подходят условиям.
  2. Для поиска максимального числа фигур для заданного поля – Проверяется, можно ли поставить одну фигуру, две, три и так далее, пока фигур больше поставить будет нельзя.

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

  1 #include <vector>
  2 #include <iostream>
  3 #include <algorithm>
  4 
  5 
  6 using namespace std;
  7 
  8 int n,k, o, m, l, g, maxi, a, sum=0,y, mozno=1;//mozno=1 если можно поставить n фигур
  9 vector<vector<int> > matrix;// двухмерный вектор
 10 
 11 bool ladia(int x, int y) {      //проверка, можно ли в эту клетку поставить ладью
 12     for(int i = 0; i<n; i++)
 13         if(matrix[x][i] == 1)
 14             return false;
 15     for(int j=0; j<n; j++)
 16         if(matrix[j][y]==1)
 17             return false;
 18     return true;
 19 }
 20 
 21 bool slon(int x, int y) {   //    --//-- слона
 22 
 23    for (int i=x, j=y;i<n && j>=0; i++, j--)
 24        if(matrix[i][j] == 1)
 25             return false;
 26    for (int i=x, j=y;i>=0 && j>=0; i--, j--)
 27        if(matrix[i][j] == 1)
 28             return false;
 29    for (int i=x, j=y;i>=0 && j<n; i--, j++)
 30        if(matrix[i][j] == 1)
 31             return false;
 32    for (int i=x, j=y;i<n && j<n; i++, j++)
 33        if(matrix[i][j] == 1)
 34             return false;
 35 
 36     return true;
 37 
 38 }
 39 
 40 bool fruz(int x, int y){      //    --//-- ферзя
 41     if(slon(x,y) && ladia(x,y))
 42         return true;
 43 
 44     return false;
 45 
 46 
 47 }
 48 
 49 bool kon(int x, int y) {   // --//-- коня
 50 
 51    if (x-1>=0 && y-2>=0 && matrix[x-1][y-2]==1)
 52         return false;
 53    if (y-2>=0 && x+1<n && matrix[x+1][y-2]==1)
 54         return false;
 55    if (x-2>=0 && y-1>=0 && matrix[x-2][y-1]==1)
 56         return false;
 57    if (x+2<n && y-1>=0 && matrix[x+2][y-1]==1)
 58         return false;
 59    if (x-2>=0 && y+1<n && matrix[x-2][y+1]==1)
 60         return false;
 61    if (x+2<n && y+1<n && matrix[x+2][y+1]==1)
 62         return false;
 63    if (x-1>=0 && y+2<n && matrix[x-1][y+2]==1)
 64         return false;
 65    if (x+1<n && y+2<n && matrix[x+1][y+2]==1)
 66         return false;
 67 return true;
 68 }
 69 
 70 bool king(int x, int y) {   // --//--  короля
 71 
 72     if (x-1>=0 && y-1>=0 && matrix[x-1][y-1]==1)
 73         return false;
 74     if (x-1>=0 && matrix[x-1][y]==1)
 75         return false;
 76     if (y+1<n && x-1>=0 && matrix[x-1][y+1]==1)
 77         return false;
 78     if (y+1<n && matrix[x][y+1]==1)
 79         return false;
 80     if (y+1<n && x+1>n && matrix[x+1][y+1]==1)
 81         return false;
 82     if (x+1<n && matrix[x+1][y]==1)
 83         return false;
 84     if (x+1<n && y-1>=0 && matrix[x+1][y-1]==1)
 85         return false;
 86     if (y-1>=0 && matrix[x][y-1]==1)
 87         return false;
 88     return true;
 89 
 90 }
 91 
 92 int mass() {  // вывод доски на экран
 93 
 94 for(int i = 0; i<n; i++)
 95   {
 96 
 97     for(int j = 0; j<n; j++)
 98         cout<<matrix[i][j]<<" ";
 99 
100         cout<<endl;
101     }
102 
103 }
104 
105 int del() {  // очистка доски(все нули)
106 
107 for (int i=0; i<n; i++) {
108 
109     for (int j=0; j<n; j++)
110         matrix[i][j]=0;
111 }
112 
113 }
114 
115 
116 
117 void vsevarintyrasstavitnfigur(int x,int y){  // рекурсивный поиск всех вараинтов расстановок заданнного количества фигур (x - номер фигуры в доске, если ее растянуть в линию, y - кол-во фигур)
118     if(y==0) {
119         if (a==1){
120             mass();
121             cout<<'\n';
122         }
123         if(a==2) {
124                 mozno = 1;  //mozno=1 если можно поставить n фигур
125 
126         }
127 
128         return;
129     }
130 
131     for(int i=x;i<n*n;i++){
132 
133         if (o==1)
134         if(fruz(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
135 
136         if (o==2)
137         if(ladia(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
138 
139         if (o==3)
140         if(slon(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
141 
142         if (o==4)
143         if(kon(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
144 
145         if (o==5)
146         if(king(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;}
147 
148 
149         vsevarintyrasstavitnfigur(i+1, y);
150         matrix[i/n][i%n]=0;//удаление фигуры из прошлой клетки для проверки других вариантов
151         y++;
152 
153     }
154 
155 }
156 
157 void maxfig(){  //поиск максимального количества фигур
158     int i=0;
159 while(mozno==1){ //проверяет для данной доски возможность расставить 1,2... фигуры, пока не доходит до количества, которое расставить невозхможно. Тогда это количество фигур -1 - искомая величина
160         i++;
161         mozno=0;
162         vsevarintyrasstavitnfigur(0,i);
163     }
164     setlocale(LC_ALL, "Russian");
165     cout<<"Максимальное количество фигур = "<<i-1<<endl;
166 }
167 
168 
169 int main() {
170 setlocale(LC_ALL, "Russian");
171     g=0;
172     cout<<"Введите размер доски:"<<endl;
173     cin >>n;
174         for(int i=0; i<n; i++) {
175             vector<int> z;
176             for(int j=0; j<n; j++){
177                     z.push_back(0);   //создание вектора z  из n нулей и добавление его к двухмерному вектору
178             }
179             matrix.push_back(z);
180         }
181 
182         cout<<"1 - расстановки фигур на доске n*n"<<endl<<"2 - максимум фигур на доске n*n"<<endl;
183            cin>>a;
184 
185         while(2>1){
186             cout<<" 1 - ферзь"<<endl;
187             cout<<" 2 - ладья"<<endl;
188             cout<<" 3 - слон"<<endl;
189             cout<<" 4 - конь"<<endl;
190             cout<<" 5 - король"<<endl;
191             cout<<" 6 - выход"<<endl;
192 
193            cout<<"Введите число от 1 до 6:"<<endl;
194            cin>>o;
195             mozno=1;
196             if(o==6) break;
197 
198 
199 
200 
201 
202 
203     if (o==1)   {
204                 cout<<"Ферзь"<<endl;
205 
206             if(a==1)
207                 {
208                     cin>>y;
209                     vsevarintyrasstavitnfigur(0,y);
210                 }
211 
212 
213             if (a==2)
214                 maxfig();
215 
216                 }
217 
218 
219 
220 
221 
222 
223     if (o==2)   {
224                 cout<<endl<<"Ладья"<<endl;
225 
226                     if(a==1)
227                     {
228 
229                         cin>>y;
230                         vsevarintyrasstavitnfigur(0,y);
231                     }
232 
233                     if (a==2)
234                         maxfig();
235 
236                 }
237 
238 
239     if (o==3)   {
240                 cout<<endl<<"Слон"<<endl;
241 
242                 if(a==1)
243                     {
244                     cin>>y;
245                     vsevarintyrasstavitnfigur(0,y);
246                     }
247 
248                     if (a==2)
249                     maxfig();
250 
251                 }
252 
253 
254     if (o==4)  {
255                 cout<<endl<<"Конь"<<endl;
256 
257                 if(a==1)
258                     {
259                     cin>>y;
260                     vsevarintyrasstavitnfigur(0,y);
261                     }
262                     if (a==2)
263                     maxfig();
264 
265                }
266 
267     if (o==5)   {
268                 cout<<"Король"<<endl;
269 
270                 if(a==1)
271                 {
272                     cin>>y;
273                     vsevarintyrasstavitnfigur(0,y);
274 
275                 }
276                  if (a==2)
277 
278                        maxfig();
279 
280                 }
281 
282             }
283 
284 
285 
286 }



Лосева Татьяна

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

Инструкция : Пользователя попросят ввести размер доски,затем выбрать один из вариантов работы программы:1.поиск возможных расстановок для M фигур или 2.поиск максимального количества расстановок для данного поля,затем попросят выбрать тип фигуры и в первом случае количество фигур.При выводе на экран выводится номер расстановки и доска,на доске F- обозначены занятые клетки,0-пуская клетка. Для 2 пункта выводится лишь число: максимальное количество фигур,которое можно расставить.

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


  1 #include<iostream>
  2 using namespace std;
  3 int N;//размер доски NxN
  4 int **a;
  5 int *ax;
  6 int *by;
  7 int l = 0;//L-номер пункта в меню
  8 int M;//количество фигур
  9 bool isPrint = false;//переменная для вывода на экран,когда требуется,для удобства обозначим в начале false
 10 
 11 
 12 void print()//функция вывода на экран
 13 {
 14 	for (int i = N - 1; i >= 0; --i)
 15 	{
 16 		for (int j = 0; j < N; ++j)
 17 		{
 18 			cout << ((a[j][i]) ? "F " : "0 ");//если (a[j][i]) истина,то есть клетка занята,ставим F,в другом случае,т.е.свободна,ставим 0
 19 		}
 20 		cout << '\n';
 21 	}
 22 	cout << '\n';
 23 
 24 }
 25 bool Lad(int x, int y)//Ладья
 26 {
 27 	for (int i = 0; i < N; ++i)
 28 	{
 29 		if (a[i][y] == 1 )//проверяем горизонталь:если клетка занята
 30 		{
 31 			return false;//возвращаем false
 32 		}
 33 		if (a[x][i] == 1)//проверяем вертикаль : если хотя бы одна клетка занята,то
 34 		{
 35 			return false;//возврашаем false
 36 		}
 37 	}
 38 	return true;//ничего выше не выполняется,значит возвращаем правду:вертикаль и горизонталь свободна
 39 
 40 }
 41 
 42 bool Kon(int x, int y)//Коняша
 43 {
 44 	int i[8] = {-2, -2, -1, -1, 1, 1, 2, 2};//координаты клеток,на которые может ходить конь,относительно текущей (8 вариантов)
 45 	int j[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
 46 	
 47 	for (int k = 0; k < 8; k++)//8 вариантов хода
 48 	
 49 	{
 50 		if (x + i[k] >= 0 && x + i[k] < N && y + j[k] >= 0 && y + j[k] < N)//проверка выхода за границы массива
 51 		{
 52 			if (a[x + i[k]][y + j[k]] != 0)//клетка занята 
 53 			{
 54 				return false;//возвращем false
 55 			}
 56 		}
 57 	}
 58 	return true;////ничего выше не выполняется,значит возвращаем правду:все варианты ходов  свободны и конь никого не перебивает,тогда можно занять клетку
 59 
 60 }
 61 
 62 
 63 
 64 
 65 bool Korol(int x, int y)//Король
 66 	{
 67 
 68 	int i[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };//координаты клеток,на которые может ходить король,относительно текущей 
 69     int j[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 70 
 71 	for(int k = 0; k < 8; k++)//8 вариантов хода
 72 	{
 73 		if (x + i[k] >= 0 && x + i[k] < N && y + j[k] >= 0 && y + j[k] < N)//прроверяем не выходит ли фигура за границы массива
 74 		{
 75 			if (a[x + i[k]][y + j[k]] != 0)//если какой нибудь из вариантов хода занят
 76 			{
 77 				return false;//то false
 78 			}
 79 		}
 80 	}
 81 	return true;//свободно,можно занимать
 82 }
 83 
 84 bool Slon(int x, int y)
 85 {
 86 	int p1 = y - x;//номер диагонали слева направо
 87 	int p2 = y + x;//номер диагонали с права налево
 88 	for (int i = 0; i < N; i++)//проверяем левую диагональ
 89 	{
 90 		if (i + p1 >= 0 && i + p1 < N)//проверка на выход за границы массива
 91 		{
 92 			if (a[i][i + p1] == 1) //проверяем диагональ
 93 			{
 94 				return false;//диагональ занята
 95 			}
 96 		}
 97 		if (-i + p2 >= 0 && -i + p2 < N)//вторая диагональ
 98 		{
 99 			if (a[i][-i + p2] == 1) 
100 			{
101 				return false;//вторая диагональ занята
102 			}
103 		}
104 	}
105 	return true;//обе диагонали свободны,ура!
106 }
107 
108 bool Check(int x, int y)//Ферзь=Ладья+Слон
109 {
110 	int p1 = y - x;//диагональ 1
111 	int p2 = y + x;//диагональ 2
112 	for (int i = 0; i < N; ++i)
113 	{
114 		if (a[i][y] == 1 )//проверяем горизонталь
115 		{
116 			return false;//занято
117 		}
118 		if (a[x][i] == 1)//проверяем вертикаль
119 		{
120 			return false;//занято
121 		}
122 		
123 		if (i + p1 >= 0 && i + p1 < N)//выход за границы массива
124 		{
125 			if (a[i][i + p1] == 1) //проверяем 1 диагональ
126 			{
127 				return false;//занято
128 			}
129 		}
130 		if (-i + p2 >= 0 && -i + p2 < N)//выход за границы массива
131 		{
132 			if (a[i][-i + p2] == 1)//проверяем 2ую диагональ
133 			{
134 				return false;//занято
135 			}
136 		}
137 	}
138 	return true;//свободно!
139 }
140 
141 int  menu1()
142 {
143 	cout << "Type of figure:" << endl << "1 - Ferz" << endl << "2 - Ladya" << endl << "3 - Slon" << endl << "4 - Kon" << endl << "5 - Korol" << endl;
144 	cin >> l;
145 	return l;
146 }
147 
148 int num = 0;//номер расстановки
149 			//пробует найти результаты решений.
150 
151 void Func(int d,int K) //d-глубина рекурсии;K-сколько фигур нужно расставить
152 {
153 	if (d == K)//когда расставили нужное количество
154 	{
155 		if (isPrint)//если true,то печатаем(в случае с MAX количеством доску печатать не нужно)
156 		{
157 			cout << "Result: " << num + 1 << '\n';//выводим нормер расстановки
158 			print();//печатаем доску
159 		}
160 		num++;//номер расстановки увеличивается
161 		return;
162 	}
163 
164 	int minX = d != 0 ? ax[d - 1] : 0;//исходя из того куда быда поставлена предыдущая фигура
165 	//,накладываются ограничения для выбора места новой,чтобы избежать поторений
166 	int minY = d != 0 ? by[d - 1] + 1 : 0;
167 
168 
169 	bool isPossible = false;//Проверяет,возможно ли занять клетку
170 	for (int i = minX; i < N; ++i)
171 	{
172 
173 		for (int j = (i != minX) ? 0 : minY; j < N; ++j)
174 		{
175 			switch (l)//l- номер пункта в меню с фигурами
176 			{
177 			case 1://ферзь
178 				isPossible = Check(i, j);
179 				break;
180 			case 2://Ладья
181 				isPossible = Lad(i, j);
182 				break;
183 			case 3://Слон
184 				
185 				isPossible = Slon(i, j);
186 				break;
187 			case 4://Конь
188 				isPossible = Kon(i, j);
189 				break;
190 			case 5://Король
191 				isPossible = Korol(i, j);
192 				break;
193 			}
194 			if (isPossible)//если клетку занять возмоно(функция вернула true)
195 			{
196 			   a[i][j] = 1;//занимаем клетку
197 				ax[d] = i;//запоминаем куда была поставлена фигура
198 				by[d] = j;//запоминаем куда была поставлена фигура
199 				Func(d + 1, K);//вызываем рекурсивно
200 				a[i][j] = 0;
201 			}
202 		}
203 	}
204 
205 	return;
206 }
207 
208 int main()
209 {
210 
211 	cout << "Enter size: ";//нужно ввести размер доски
212 	cin >> N;//считываем размер доски
213 
214 	a = new int*[N];//создаём двумерный массив,т.е.нашу доску
215 	for (int i = 0; i < N; i++)
216 	{
217 		a[i] = new int[N];
218 		for (int j = 0; j < N; j++)
219 			a[i][j] = 0;//заполняем нулями
220 	}
221 	
222 	ax = new int[N];//массивы для сохранения координаты каждой фигуры,чтобы избежать повторений
223 	by = new int[N];
224 
225 	int d;//пункт в меню
226 	cout<<"1 - Rasstanovka figur"<<endl<<"2 - MAX znachenie"<<endl;//два варианта работы программы
227 	cin>>d;//считываем выбор пользователя
228 	if(d==1)//если выбирает расстановку
229 	{   
230 		menu1();//то спрашиваем для какой фигуры
231 		cout<<"How many figures?"<<endl;//и как много будет фигур
232 	    cin>>M;//считываем количество фигур
233 		isPrint = true;//в этом случае будем выводить на экран
234 		Func(0,M);//запуск рекурсивной функции
235 	}
236 
237 	if (d == 2)//случай подсчёта максимального значения
238 	{
239 		int n = 0;//изачально max=0
240 		menu1();//выбираем фигуру
241 		
242 		do//начало цикла 
243 		{
244 			num = 0;
245 			Func(0, ++n);//запускаем каждый раз увеличивая значение фигур и считаем количество расстановок
246 		} while (num != 0);//количество вариантов не должно быть равно нулю
247 		cout <<"MAX ="<< n - 1 << endl;//если количество вариантов = 0,то выходим из цикла и предыдущее значение  максимальное
248 	}
249 	
250 
251 	int z;
252 	cin >> z;
253 
254 	return 0;
255 }

Степанянц Степан

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

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

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

  1 #include <iostream>
  2 #include <vector>
  3 
  4 using namespace std;
  5 
  6 
  7 
  8 //задаю массивы в которых изображены все ходы определенных фигур
  9 int d = 0;
 10 int d_knight[2][8] = {{1, 1, -1, -1, 2, 2, -2, -2},
 11     {2, -2, 2, -2, 1, -1, 1, -1}};
 12 int d_bish[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
 13 int d_king[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
 14 //Проверяем, не выходим ли мы за поле
 15 bool ok(int x, int y, int n) {
 16     if (x < 0 || y < 0 || x >= n || y >= n)
 17         return false;
 18     return true;
 19 }
 20 
 21 void print(int n, vector<vector<pair<bool, int> > > board) {
 22     for (int i = 0; i < n; i++) {
 23         for (int j = 0; j < n; j++) {
 24             cout << ((board[i][j].first) ? " X " : " 0 ");
 25         }
 26         cout << '\n';
 27     }
 28     cout << "-------------------------------------\n";
 29 }
 30 //Рекурсивная функция
 31 int func(int n, int k, int count, vector<vector<pair<bool, int> > > board, int ii, int jj, int fig, int task) {
 32     int ans = 0;
 33     if (count == k && !task) {
 34         print(n, board);
 35         return 1;
 36     }
 37     else if(task) {
 38         ans = max(ans, count);
 39     }
 40     for (int i = ii + jj / n; i < n; i++) {
 41         for (int j = jj % n; j < n; j++) {
 42             if (!board[i][j].first && !board[i][j].second) {
 43                 switch (fig) {
 44                     case 1://конь
 45                         for (int k = 0; k < 8; k++) {
 46                             if (ok(i + d_knight[0][k], j + d_knight[1][k], n))
 47                                 board[i + d_knight[0][k]][j + d_knight[1][k]].second++;
 48                         }
 49                         break;
 50                     case 2://слон
 51                         for (int k = 0; k < n; k++) {
 52                             for (int l = 0; l < 4; l++) {
 53                                 if (ok(i + k * d_bish[l][0], j + k * d_bish[l][1], n))
 54                                     board[i + k * d_bish[l][0]][j + k * d_bish[l][1]].second++;
 55                             }
 56                         }
 57                         break;
 58                     case 3: // ладья
 59                         for (int k = 0; k < n; k++)
 60                             board[i][k].second++, board[k][j].second++;
 61                         break;
 62                     case 4: // король
 63                         for (int k = 0; k < 8; k++)
 64                             if (ok(i + d_king[k][0], j + d_king[k][1], n))
 65                                 board[i + d_king[k][0]][j + d_king[k][1]].second++;
 66                         break;
 67                     case 5: // ферзь
 68                         for (int k = 0; k < 8; k++)
 69                             for (int l = 0; l < n; l++)
 70                                 if (ok(i + l * d_king[k][0], j + l * d_king[k][1], n))
 71                                     board[i + l * d_king[k][0]][j + l * d_king[k][1]].second++;
 72                         break;
 73                         
 74                 }
 75                 //Рекурсия
 76                 board[i][j].first = true;
 77                 if (!task)
 78                     ans += func(n, k, count + 1, board, i, j + 1, fig, task);
 79                //обратный ход
 80                 else
 81                     ans = max(ans, func(n, k, count + 1, board, i, j + 1, fig, task));
 82                 board[i][j].first = false;
 83                 switch (fig) {
 84                     case 1:
 85                         for (int k = 0; k < 8; k++) {
 86                             if (ok(i + d_knight[0][k], j + d_knight[1][k], n))
 87                                 board[i + d_knight[0][k]][j + d_knight[1][k]].second--;
 88                         }
 89                         break;
 90                     case 2:
 91                         for (int k = 0; k < n; k++) {
 92                             for (int l = 0; l < 4; l++) {
 93                                 if (ok(i + k * d_bish[l][0], j + k * d_bish[l][1], n))
 94                                     board[i + k * d_bish[l][0]][j + k * d_bish[l][1]].second--;
 95                             }
 96                         }
 97                         break;
 98                     case 3:
 99                         for (int k = 0; k < n; k++)
100                             board[i][k].second--, board[k][j].second--;
101                         break;
102                     case 4:
103                         for (int k = 0; k < 8; k++)
104                             if (ok(i + d_king[k][0], j + d_king[k][1], n))
105                                 board[i + d_king[k][0]][j + d_king[k][1]].second--;
106                         break;
107                     case 5:
108                         for (int k = 0; k < 8; k++)
109                             for (int l = 0; l < n; l++)
110                                 if (ok(i + l * d_king[k][0], j + l * d_king[k][1], n))
111                                     board[i + l * d_king[k][0]][j + l * d_king[k][1]].second--;
112                         break;
113                 }
114             }
115         }
116         jj = 0;
117     }
118     return ans;
119 }
120 //меню
121 int main() {
122     int fig, task;
123     int n, k;
124     cout << "Please, input the task number: 1 - amount of solutions, 2 - maximum of figures\n";
125     cin >> task;
126     task--;
127     cout << "Please, input figure type: 1 - knight, 2 - bishop, 3 - castle, 4 - king, 5 - queen\n";
128     cin >> fig;
129     cout << "Please, input the size of the board\n";
130     cin >> n;
131     if (!task) {
132         cout << "Please, input number of figures\n";
133         cin >> k;
134     }
135     vector<vector<pair<bool, int> > > v = vector<vector<pair<bool, int> > >(n, vector <pair<bool, int> >(n, {false, 0}));
136     cout << func(n, k, 0, v, 0, 0, fig, task);
137 }

Лобанов Илья

Описание алгоритма:

Программа проверяет возможность расстановки фигур на доске M*M . При выводе на экран на экран клетки,занятые фигурами ,помечаются буквами,соответствующими первой букве типа фигуры. Также программа считает максимальное число фигур определенного типа,которые можно расставить на доске.

Инструкция:

В окне консоли пользователю предлагается выбрать 2 типа работы программы, затем пользователь вводит размер доски(четный),тип и количество фигур,которые необходимо разместить на доске.В зависимости от режима работы программы ,будет выведено либо максимально возможное число расстановок фигур,либо максимальное число фигур. Скачать можно [тут] 

  1 #include <iostream>
  2 #include <windows.h>
  3 using namespace std;
  4 
  5 enum type{peshka, king, kon, ladya, slon, queen}; // все возможные типы фигур
  6 const char symbols[] = "pKklsQ"; // буквенное обозначение каждой фигуры:p - пешка, K - король, k - конь, l- ладья, s - слон, Q - ферзь
  7 const int NONE = INT_MAX;//константа для обозначения пустой клетки
  8 int M, **desk, *colons, *rows, *diag_1, *diag_2;
  9 
 10 // структура для описания клектки доски
 11 struct point 
 12 {
 13 	int x, y;
 14 	point(int x = 0, int y = 0): x(x), y(y) {}
 15 	point &operator++()
 16 	{
 17 		if (y == M - 1)
 18 		{
 19 			++x;
 20 			y = 0;
 21 		}
 22 		else 
 23 			++y;
 24 		return *this;
 25 	}
 26 	point operator+(const point &p) const
 27 	{
 28 		return point(x + p.x, y + p.y);
 29 	}
 30 	point next() const
 31 	{
 32 		point r = *this;
 33 		return ++r;
 34 	}
 35 };
 36 
 37 
 38 int *new_array(int n)
 39 {
 40 	int *a = new int[n];
 41 	fill(a, a + n, NONE);
 42 	return a;
 43 }
 44 
 45 // Количество свободных клеток от клетки p до конца доски
 46 int rest(const point &p, type t)
 47 {
 48 	int r0 = (M - p.x) * M - p.y, r,
 49 		m = M - p.x,
 50 		s_2 = (m + 1) / 2 * M;
 51 	switch (t)
 52 	{
 53 	case peshka:
 54 	case kon:
 55 		r = s_2; break;
 56 	case king:
 57 		r = s_2 / 2; break;
 58 	case ladya:
 59 	case queen:
 60 		return m;
 61 	case slon:
 62 		r = m + M - 1;
 63 	}
 64 	return min(r0, r);
 65 }
 66 
 67 // Помечает клетку доски номером i
 68 void set(const point &p, type t, int i)
 69 {
 70 	if (t == peshka || t == king || t == kon)
 71 		desk[p.x][p.y] = i;
 72 	else
 73 	{
 74 		if (t == ladya || t == queen)
 75 			colons[p.y] = rows[p.x] = i;
 76 		if (t == slon || t == queen)
 77 			diag_1[p.x+p.y] = diag_2[p.x-p.y+M-1] = i;
 78 	}
 79 }
 80 
 81 // Можно ли поставить фигуру номер i на клетку p
 82 bool empty(const point &p, type t, int i)
 83 {
 84 	const int n_attack[3] = {4, 8, 8};
 85 	const point attack[3][8] = {{point(1, 1), point(1, -1), point(-1, 1), point(-1, -1)}, //кол-во вариантов атаки для пешки
 86 	{point(1, 1), point(1, -1), point(-1, 1), point(-1, -1), point(1, 0), point(-1, 0), point(0, 1), point(0, -1)}, // кол-во вариантов атаки для короля
 87 	{point(1, 2),point(-1, 2),point(1, -2), point (-1,-2), point (2, 1), point (2,-1), point (-2, 1),point (-2,-1)}};  //количество вариантов атаки для коня
 88 	switch(t)
 89 	{
 90 	case peshka:
 91 	case king:
 92 	case kon:
 93 		for (int k = 0; k < n_attack[t]; k++)
 94 		{
 95 			point q = p + attack[t][k];
 96 			if (q.x >= 0 && q.x < M && q.y >= 0 && q.y < M && desk[q.x][q.y] < i)
 97 				return false;
 98 		}
 99 		return true;
100 	case ladya:
101 		return colons[p.y] > i && rows[p.x] > i;
102 	case slon:
103 		return diag_1[p.x+p.y] > i && diag_2[p.x-p.y+M-1] > i;
104 	case queen:
105 		return colons[p.y] > i && rows[p.x] > i && diag_1[p.x+p.y] > i && diag_2[p.x-p.y+M-1] > i;
106 	}
107 }
108 
109 //печатает заданное количество досок на экране
110 void print(point **figures, int n_desks, int N, type t, ostream &out = cout)
111 {
112 	HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
113 	for (int n = 0; n < n_desks; n++)
114 	{
115 		out << " \xdb";
116 		for (int i = 0; i < M * 2 + 2; i++)
117 			out << "\xdf";
118 		out << "\xdb";
119 	}
120 	out << endl;
121 
122 	int *K = new int[n_desks];
123 	fill(K, K + n_desks, 0);
124 	for (int i = 0; i < M; i++)
125 	{
126 		for (int n = 0; n < n_desks; n++)
127 		{
128 			int &k = K[n];
129 			out << " \xdb ";
130 			for (int j = 0; j < M; j++)
131 			{
132 				SetConsoleTextAttribute(hConsole, (i + j) % 2 == 0 ? 0xf0 : 0xf);
133 				if (k < N && i == figures[n][k].x && j == figures[n][k].y)
134 				{			
135 					out << ' ' << symbols[t];
136 					k++;
137 				}
138 				else
139 					out << "  ";
140 			}
141 			SetConsoleTextAttribute(hConsole, 0x70);
142 			out << " \xdb";
143 		}
144 		out << endl;
145 	}
146 	delete[] K;
147 
148 	for (int n = 0; n < n_desks; n++)
149 	{
150 		out << " \xdb";
151 		for (int i = 0; i < M * 2 + 2; i++)
152 			out << "\xdc";
153 		out << "\xdb";
154 	}
155 	out << endl << endl;
156 }
157 
158 // Вывести все возможные расположения на доске N фигур
159 void all_placements(int N, type t)
160 {
161 	desk = NULL;
162 	colons = rows = diag_1 = diag_2 = NULL;
163 	// создание необходимых массивов, отмечающих занятость клеток, в зависимости от вида фигуры
164 	if (t == peshka || t == king || t == kon)
165 	{
166 		desk = new int*[M];
167 		for (int j = 0; j < M; j++)
168 			desk[j] = new_array(M);
169 	}
170 	else
171 	{
172 		if (t == ladya || t == queen)
173 		{
174 			colons = new_array(M);
175 			rows = new_array(M);
176 		}
177 		if (t == slon || t == queen)
178 		{
179 			diag_1 = new_array(2*M-1);
180 			diag_2 = new_array(2*M-1);
181 		}
182 	}
183 	
184 	const int W = 80 / (2 * M + 5);//количество досок,помещающихся на экране
185 	point **figures = new point*[W];//массив фигур
186 	for (int j = 0; j < W; j++)
187 		figures[j] = new point[N];
188 
189 	int i = 0, // номер фигуры
190 		k = 0; //номер комбинации
191 	while (true)
192 	{
193 		if (rest(figures[k%W][i], t) < N - i) // если оставшиеся фигуры не помещаются на доске
194 		{
195 			if (i == 0) // если все комбинации закончились
196 			{
197 				// вывод оставшихся досок
198 				if (k % W)
199 					print(figures, k % W, N, t);
200 				cout << "Amount of combinations: " << k << endl;
201 				break;
202 			}
203 			// переходим к предыдущей фигуре и помечаем клетку пустой
204 			set(figures[k%W][--i], t, NONE);
205 			// сдвигаем фигуру на шаг вперёд
206 			++figures[k%W][i];
207 		}
208 		else if (!empty(figures[k%W][i], t, i)) // если фигуры помещаются, но текущая клетка под ударом
209 			// сдвигаем текущую фигуру на шаг вперёд
210 			++figures[k%W][i];
211 		else if (i == N - 1) // если ставим последнюю фигуру
212 		{
213 			// если текущая доска - последняя на строке экрана, выводим W досок
214 			if ((k + 1) % W == 0)
215 				print(figures, W, N, t);
216 			// копирование комбинаций фигур на следующую доску
217 			for (int j = 0; j < N; j++)
218 				figures[(k+1)%W][j] = figures[k%W][j];
219 			// переход к следующей доске
220 			k++;
221 			//сдвигаем текущую фигуру на шаг вперёд
222 			++figures[k%W][i];
223 		}
224 		else // если ставим не последнюю фигуру
225 		{
226 			// помечаем текущую клетку номером i
227 			set(figures[k%W][i], t, i);
228 			//ставим следующую фигуру на клетку после текущей
229 			figures[k%W][i+1] = figures[k%W][i].next();
230 			// переходим к следующей фигуре
231 			i++;
232 		}
233 	}
234 
235 	//освобождение памяти
236 	for (int j = 0; j < W; j++)
237 		delete[] figures[j];
238 	delete[] figures;
239 	if (desk)
240 	{
241 		for (int j = 0; j < M; j++)
242 			delete[] desk[j];
243 		delete[] desk;
244 	}
245 	if (colons)
246 	{
247 		delete[] colons;
248 		delete[] rows;
249 	}
250 	if (diag_1)
251 	{
252 		delete[] diag_1;
253 		delete[] diag_2;
254 	}
255 }
256 
257 
258 int main()
259 {
260 	system("color 70"); // Установка серого фона и чёрного текста
261 	while (true)
262 	{
263 		cout << "Choose the mode:\n1 - all possible variants of figures' placement\n2 - maximum number of figures which can be placed on the desk\nq - quit\n\n";
264 		char c;
265 		cin >> c;
266 		cin.ignore(100, '\n');
267 		switch (c)
268 		{
269 		case '1':
270 		case '2':
271 			cout << "Enter the desk size please. (The number must be even and not more than 37.)\n";
272 			cin >> M;
273 			while (!cin || M % 2 != 0 || M > 37 || M <= 0)
274 			{
275 				cout << "Error: wrong desk size. Try again please.\n";
276 				cin.clear();
277 				cin.ignore(100, '\n');
278 				cin >> M;
279 			}
280 			cin.ignore(100, '\n');
281 			cout << "Choose a figure, please.\n p - peshka, k - kon, l - ladya, s - slon, Q - Queen, K - King\n";
282 			char f;
283 			cin >> f;
284 			cin.ignore(100, '\n');
285 			type t;
286 			int i;
287 			do
288 			{
289 				for (i = 0; i < 6; i++)
290 				{
291 					if (symbols[i] == f)
292 					{
293 						t = type(i);
294 						break;
295 					}
296 				}
297 				if (i == 6)
298 				{
299 					cout << "Enter the right letter, you've chosen the wrong one.\n";
300 					cin >> f;
301 					cin.ignore(100, '\n');
302 				}
303 			} while (i == 6);
304 			if (c == '1')
305 			{
306 				cout << "Enter the number of figures please.\n";
307 				int N;
308 				cin >> N;
309 				while (!cin || N <= 0)
310 				{
311 					cout << "Error: wrong argument. Try again please.\n";
312 					cin.clear();
313 					cin.ignore(100, '\n');
314 					cin >> N;
315 				}
316 				cin.ignore(100, '\n');
317 				all_placements(N, t);
318 			}
319 			else
320 			{
321 				cout << "The maximal number of figures is ";
322 				switch (t)
323 				{
324 				case peshka:
325 					cout << M*M/2; break;
326 				case king:
327 					cout << M*M/4; break;
328 				case kon: 
329 					cout << (M == 2 ? 4 : M*M/2); break;
330 				case ladya:
331 					cout << M; break;
332 				case slon:
333 					cout << 2*M - 2; break;
334 				case queen:
335 					cout << (M == 2 ? 1 : M);
336 				}
337 				cout << ".\n";
338 			}
339 			break;
340 		case 'q':
341 			cout << endl;
342 			return 0;
343 		default:
344 			cout << "You've chosen the wrong command, try again please.\n";
345 		}
346 		cout << endl << endl;
347 	}
348 }

Савельева Ольга


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

Скачать программу можно [1] 

  1 #define windows
  2 
  3 #include <stdio.h>
  4 #include <vector>
  5 
  6 #ifdef windows
  7 #include <windows.h>
  8 #endif  // windows
  9 
 10 using namespace std;
 11 
 12 #ifdef windows
 13 HANDLE hCon;
 14 #endif // windows
 15 
 16 unsigned fact(int n)  //factorial of a number
 17 {
 18     unsigned long long ret = 1;
 19     for(int i = 2; i <= n; i++)
 20         ret *= i;
 21     return ret;
 22 }
 23 
 24 struct desk
 25 {
 26     char **deskFigures, **deskOccupy;   //desk with figures, desk with occupation counter for each cell
 27     int x, y, size, a, f;   //pointer position(x, y), size of the desk, amount of prints, amount of figures
 28     vector<pair<int, int> > *s; //stack of placed figures
 29     bool stackIsUsed;   //if stack is needed
 30     desk(int size, bool stackIsUsed = true):x(0), y(0), size(size), a(0), f(0), stackIsUsed(stackIsUsed)
 31     {
 32         deskFigures = new char*[size];
 33         for(int i = 0; i < size; i++)
 34             deskFigures[i] = new char[size];
 35         deskOccupy = new char*[size];
 36         for(int i = 0; i < size; i++)
 37             deskOccupy[i] = new char[size];
 38         if(stackIsUsed)
 39             s = new vector<pair<int, int> >;
 40         clear();
 41     }
 42     ~desk()
 43     {
 44         for(int i = 0; i < size; i++)
 45             delete deskFigures[i];
 46         delete deskFigures;
 47         for(int i = 0; i < size; i++)
 48             delete deskOccupy[i];
 49         delete deskOccupy;
 50         if(stackIsUsed)
 51             delete s;
 52     }
 53     void setKnight(int x, int y, int z) //increase all cells occupied by knight at (x, y) on z
 54     {
 55         if(x + 2 < size)
 56         {
 57             if(y - 1 >= 0)
 58                 deskOccupy[x + 2][y - 1] += z;
 59             if(y + 1 < size)
 60                 deskOccupy[x + 2][y + 1] += z;
 61         }
 62         if(y + 2 < size)
 63         {
 64             if(x - 1 >= 0)
 65                 deskOccupy[x - 1][y + 2] += z;
 66             if(x + 1 < size)
 67                 deskOccupy[x + 1][y + 2] += z;
 68         }
 69         if(x - 2 >= 0)
 70         {
 71             if(y - 1 >= 0)
 72                 deskOccupy[x - 2][y - 1] += z;
 73             if(y + 1 < size)
 74                 deskOccupy[x - 2][y + 1] += z;
 75         }
 76         if(y - 2 >= 0)
 77         {
 78             if(x - 1 >= 0)
 79                 deskOccupy[x - 1][y - 2] += z;
 80             if(x + 1 < size)
 81                 deskOccupy[x + 1][y - 2] += z;
 82         }
 83     }
 84     void setBishop(int x, int y, int z) //increase all cells occupied by bishop at (x, y) on z
 85     {
 86         for(int ix = 0, iy1 = y - x, iy2 = y + x; ix < size; ix++, iy1++, iy2--)
 87             if(ix != x)
 88             {
 89                 if((iy1 >= 0)and(iy1 < size))
 90                     deskOccupy[ix][iy1] += z;
 91                 if((iy2 >= 0)and(iy2 < size))
 92                     deskOccupy[ix][iy2] += z;
 93             }
 94     }
 95     void setRook(int x, int y, int z)   //increase all cells occupied by rook at (x, y) on z
 96     {
 97         for(int i = 0; i < size; i++)
 98         {
 99             if(i != x)
100                 deskOccupy[i][y] += z;
101             if(i != y)
102                 deskOccupy[x][i] += z;
103         }
104     }
105     void setKing(int x, int y, int z)   //increase all cells occupied by king at (x, y) on z
106     {
107         for(int ix = x - 1; ix <= x + 1; ix++)
108             for(int iy = y - 1; iy <= y + 1; iy++)
109                 if((ix >= 0)and(ix < size)and(iy >= 0)and(iy < size)and((ix != 0)or(iy != 0)))
110                     deskOccupy[ix][iy] += z;
111     }
112     void setFigure(int x, int y, int z, char figure)    //increase all cells occupied by figure
113                                                         //and (x, y) on z
114     {
115         deskOccupy[x][y] += z;
116         switch(figure)
117         {
118             case 'N':
119                 setKnight(x, y, z);
120                 break;
121             case 'B':
122                 setBishop(x, y, z);
123                 break;
124             case 'R':
125                 setRook(x, y, z);
126                 break;
127             case 'Q':
128                 setBishop(x, y, z);
129                 setRook(x, y, z);
130                 break;
131             case 'K':
132                 setKing(x, y, z);
133                 break;
134         }
135     }
136     bool putFigure(int x, int y, char figure)   //place figure on desk and update occupied cells
137     {
138         if(deskFigures[x][y] > 0)
139             return false;
140         deskFigures[x][y] = figure;
141         if(stackIsUsed)
142             s -> push_back(make_pair(x, y));
143         setFigure(x, y, 1, figure);
144         f++;
145         return true;
146     }
147     int cellsLeft() //amount of cells after pointer
148     {
149         return (size - y) * size - x;
150     }
151     bool putNextFree(char figure)   //attempt to put figure on the next free(and not occupied) place
152     {
153         if(y >= size)
154             return false;
155         while(deskOccupy[x][y] > 0)
156         {
157             if(++x == size)
158             {
159                 if(++y == size)
160                     return false;
161                 x = 0;
162             }
163         }
164         return putFigure(x, y, figure);
165     }
166     void removeFigure(int x, int y) //remove figure from (x, y)
167     {
168         if(deskFigures[x][y]!=0)
169             setFigure(x, y, -1, deskFigures[x][y]);
170         deskFigures[x][y] = 0;
171         f--;
172     }
173     void removeBishop(int diag, bool color, bool left)  //remove bishop
174     {
175         if(color)   //true - white, false - black
176         {
177             if(diag > 0)    //diag - number of diagonal
178             {
179                 int diff = left ? 0 : diag * 2;
180                 removeFigure(diff, diag * 2 - diff);
181                 removeFigure(size - diff - 1, size - diag * 2 + diff - 1);
182             }
183             else
184             if(left)    //determine position of the bishop on the diagonal
185                 removeFigure(0, 0);
186             else
187                 removeFigure(size - 1, size - 1);
188         }
189         else
190         {
191             if(diag > 0)
192             {
193                 int diff = left ? 0 : diag * 2;
194                 removeFigure(size - diff - 1, diag * 2 - diff);
195                 removeFigure(diff, size - diag * 2 + diff - 1);
196             }
197             else
198             if(left)
199                 removeFigure(0, size - 1);
200             else
201                 removeFigure(size - 1, 0);
202         }
203     }
204     void putBishop(int diag, bool color, bool left) //place bishop
205     {
206         if(color)
207         {
208             if(diag > 0)
209             {
210                 int diff = left ? 0 : diag * 2;
211                 putFigure(diff, diag * 2 - diff, 'B');
212                 putFigure(size - diff - 1, size - diag * 2 + diff - 1, 'B');
213             }
214             else
215             if(left)
216                 putFigure(0, 0, 'B');
217             else
218                 putFigure(size - 1, size - 1, 'B');
219         }
220         else
221         {
222             if(diag > 0)
223             {
224                 int diff = left ? 0 : diag * 2;
225                 putFigure(size - diff - 1, diag * 2 - diff, 'B');
226                 putFigure(diff, size - diag * 2 + diff - 1, 'B');
227             }
228             else
229             if(left)
230                 putFigure(0, size - 1, 'B');
231             else
232                 putFigure(size - 1, 0, 'B');
233         }
234     }
235     void swapBishops(int diag, bool color, bool left)   //move pair bishops to another borders
236     {
237         removeBishop(diag, color, left);
238         putBishop(diag, color, not(left));
239     }
240     void figureBefore() //remove one figure from stack and change pointer to the next position after figure was placed
241     {
242         pair<int, int> c = s -> back();
243         s -> pop_back();
244         x = c.first;
245         y = c.second;
246         removeFigure(x, y);
247         if(++x == size)
248         {
249             x = 0;
250             y++;
251         }
252     }
253     void clear()    //clear the desk
254     {
255         for(int ix = 0; ix < size; ix++)
256             for(int iy = 0; iy < size; iy++)
257             {
258                 deskFigures[ix][iy] = 0;
259                 deskOccupy[ix][iy] = 0;
260             }
261         x = 0;
262         y = 0;
263         if(stackIsUsed)
264             s -> empty();
265         f = 0;
266     }
267     void show() //show the desk
268     {
269         a++;
270         printf("%i:\n", a);
271         #ifdef windows
272         unsigned background = 4;
273         #else
274         printf("\x1b[31m");
275         char background = 47;
276         #endif  //windows
277         for(int y = 0; y < size; y++)
278             for(int x = 0; x < size; x++)
279             {
280                 #ifdef windows
281                 SetConsoleTextAttribute(hCon, background);
282                 #else
283                 printf("\x1b[%dm", background);
284                 #endif  //windows
285                 if(deskFigures[x][y] == 0)
286                     putchar(' ');
287                 else
288                     putchar(deskFigures[x][y]);
289                 #ifdef windows
290                 if(x < size - 1)
291                     background = background == 4 ? 116 : 4;
292                 else
293                 {
294                     SetConsoleTextAttribute(hCon, 7);
295                     putchar('\n');
296                 }
297                 #else
298                 if(x < size - 1)
299                     background = background == 47 ? 40 : 47;
300                 else
301                 {
302                     printf("\x1b[0m\n");
303                     if(y < size - 1)
304                         printf("\x1b[31m");
305                 }
306                 #endif // windows
307             }
308     }
309 };
310 
311 int m = -1; //0 for number of arrangements, 1 for all variants
312 
313 unsigned lookForFigure(int size, int amount, char figure, bool show = true) //brute-force
314 {
315     desk *d  = new desk(size);
316     unsigned ret = 0;
317     while((d -> f > 0)or(d -> cellsLeft() >= amount))
318         if(not(d -> putNextFree(figure)))
319         {
320             if(d -> f == amount)
321             {
322                 if(show)
323                     d -> show();
324                 ret++;
325             }
326             d -> figureBefore();
327         }
328     delete d;
329     return ret;
330 }
331 
332 void lookForKnight(int size, int amount)    //arrangements of knights
333 {
334     if(m == 0)
335     {
336         printf("Amount of arrangements: ");
337         if(size == 2)
338             printf("1\n");
339         else
340         if(size == 4)
341             printf("6\n");
342         else
343             printf("2\n");
344     }
345     else
346     {
347         desk *d = new desk(size);
348         if(size == 2)
349         {
350             d -> putFigure(0, 0, 'N');
351             d -> putFigure(0, 1, 'N');
352             d -> putFigure(1, 0, 'N');
353             d -> putFigure(1, 1, 'N');
354             d -> show();
355         }
356         else
357         if(size==4)
358             lookForFigure(size, amount, 'N');
359         else
360         {
361             for(int x = 0; x < size; x++)
362                 for(int y = 0;y < size; y++)
363                     if(x + y % 2 == 0)
364                         d -> putFigure(x, y, 'N');
365             d -> show();
366             d -> clear();
367             for(int x = 0; x < size; x++)
368                 for(int y = 0;y < size; y++)
369                     if(x + y % 2 == 1)
370                         d -> putFigure(x, y, 'N');
371             d -> show();
372         }
373     }
374 }
375 
376 void lookForBishop(int size, int amount)    //arrangements of bishops
377 {
378     if(m == 0)
379         printf("Amount of arrangements: %u", (unsigned) 1 << size);
380     else
381     {
382         desk *d = new desk(size, false);
383         bool *b = new bool[size];
384         for(int dw = 0; dw < size/2; dw++)
385         {
386             d -> putBishop(dw, true, false);
387             d -> putBishop(dw, false, false);
388         }
389         int p = size - 1;
390         for(;;)
391         {
392             d -> show();
393             while(b[p])
394             {
395                 d -> swapBishops(p % (size / 2), p < size / 2, true);
396                 b[p--] = false;
397                 if(p < 0)
398                     return;
399             }
400             b[p] = true;
401             d -> swapBishops(p % (size / 2), p < size / 2, false);
402             p = size - 1;
403         }
404     }
405 }
406 
407 void lookForRook(int size, int amount)  //arrangements of rooks
408 {
409     if(m == 0)
410         printf("Amount of arrangements: %u", fact(size));
411     else
412         lookForFigure(size, amount, 'R');
413 }
414 
415 void lookForQueen(int size, int amount) //arrangements of queens
416 {
417     if(m == 0)
418         printf("Amount of arrangements: %u", lookForFigure(size, amount, 'Q', false));
419     else
420         lookForFigure(size, amount, 'Q');
421 }
422 
423 void lookForKing(int size, int amount)  //arrangements of kings
424 {
425     if(m == 0)
426         printf("Amount of arrangements: %u", lookForFigure(size, amount, 'K', false));
427     else
428         lookForFigure(size, amount, 'K');
429 }
430 
431 int main()
432 {
433     int s = -1, f = -1; //s - size, f - figure
434     #ifdef windows
435     hCon = GetStdHandle(STD_OUTPUT_HANDLE);
436     #endif // windows
437     sizeInput:
438     printf("Enter size of the desk:\n");
439     scanf("%i", &s);
440     if((s<=0)or(s%2!=0))
441     {
442         printf("Size must be above 0 and even\n");
443         goto sizeInput;
444     }
445     modeInput:
446     printf("Enter mode:\n\t0: Print amount of results\n\t1: Print all results\n");
447     scanf("%i", &m);
448     if((m<0)or(m>1))
449     {
450         printf("Mode can be 0 or 1\n");
451         goto modeInput;
452     }
453     figureInput:
454     printf("Enter figures to be placed\n\t0: Knight (N)\n\t1: Bishop (B)\n\t2: Rook (R)\n\t3: Queen (Q)\n\t4: King (K)\n");
455     scanf("%i", &f);
456     if((f<0)or(f>4))
457     {
458         printf("Figure number ranges from 0 to 4\n");
459         goto figureInput;
460     }
461     switch(f)
462     {
463         case 0:
464             if(s==2)
465                 lookForKnight(s, 4);
466             else
467                 lookForKnight(s, s *s / 2);
468             break;
469         case 1:
470             lookForBishop(s, 2 * s - 2);
471             break;
472         case 2:
473             lookForRook(s, s);
474             break;
475         case 3:
476             if(s==2)
477                 lookForQueen(s, 1);
478             else
479                 lookForQueen(s, s);
480             break;
481         case 4:
482             lookForKing(s, (s / 2) * (s / 2));
483             break;
484     }
485     return 0;
486 }


Козловская Анна

Краткое описание алгоритма: Доска представлена в виде динамического массива[m;m], при выводе на экран пустые клетки обозначаются звездочками,а клетки, заполненные фигурами-буквами(каждая буква соответствует первой букве названия фигуры на английском языке). Для всех фигур написаны алгоритмы проверки на возможность растановки фигуры. После выбора типа фигуры,используется рекурсивная функция,которая проверяет возможные расстановки через данную функцию проверки ,для данного типа фигуры. Во втором варианте работы программы,она аналитически высчитывает максимально возможное количество заданных фигур на доске.В программу встроена функция,проверяющая доску на повторные и симметричные относительно всех осей симметрии способы растановки фигур.

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

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

Источник — «http://tm.spbstu.ru/?title=Информатика:_Расстановка_шахматных_фигур&oldid=39000»