Ферзи

//Составить рекурсивную функцию, находящую все возможные расстановки
//n ферзей на шахматной доске размером n*n так,
//чтобы они не били друг друга

#include <iostream>
#include <vector>

using namespace std;

bool is_safe(vector<int>& board, int row, int col)
{
    for (int i = 0; i < row; ++i)
    {
        // Проверяем для каждой ранее размещенной фигуры
        // находится ли она на той же горизонтали или диагонали
        // с текущей позицией (row, col).
        if (board[i] == col || board[i] - i == col - row || board[i] + i == col + row)
            return false;
    }
    return true;
}

void placement_of_queens(int n, int row, vector<int>& board, vector<vector<int>>& result)
{
    if (row == n)
    {
        // Все ферзи были размещены на доске.
        // Добавляем текущую расстановку в результат.
        result.push_back(board);
        return;
    }

    // Размещаем ферзя на текущей строке
    for (int col = 0; col < n; ++col)
    {
        if (is_safe(board, row, col))
        {
            board[row] = col;
            // Рекурсивно размещаем ферзя на следующей строке
            placement_of_queens(n, row + 1, board, result);
        }
    }
}

vector<vector<int>> placement_of_queens(int n)
{
    vector<vector<int>> result;
    vector<int> board(n, 0);
    placement_of_queens(n, 0, board, result);
    return result;
}

void print_board(vector<int>& board)
{
    int n = board.size();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (board[i] == j)
                cout << "Q ";
            else
                cout << ". ";
        }
        cout << endl;
    }
    cout << endl;
}

int main()
{
    setlocale(LC_ALL, "rus");

    int n;
    cout << "Введите размер доски (n x n): ";
    cin >> n;

    vector<vector<int>> solutions = placement_of_queens(n);
    int count = solutions.size();

    cout << "Количество решений: " << count << endl;
    cout << "Расстановки ферзей:" << endl;

    for (vector<int> solution : solutions)
    {
        print_board(solution);
    }

    return 0;
}