#include <iostream>

using namespace std;

int field_size, max_count, cnt = 0, result = 0;
int* row; // массив номеров строк
int* col; // массив номеров столбцов
int* main_diag; // массив номеров диагоналей, параллельных главной
int* side_diag; // массив номеров диагоналей, параллельных побочной

int** arr; // этот массив нужен только для визуализации, если не надо - можно не заполнять его

void print(int** arr) {
    for (int i = 0; i < field_size; ++i) {
        for (int j = 0; j < field_size; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void get_count(int i = 0, int k = 0) { // i - номер строки
    for (int j = k; j < field_size; ++j) { // j - номер столбца
        if (col[j] < 2 && row[i] < 2 && main_diag[i + j] < 2 && side_diag[field_size - i + j] < 2) {
            if (cnt == max_count - 1) {
                result++;
                // строки 29-31 только для визуализации, если не надо - закомментировать
                arr[i][j]++;
                print(arr);
                arr[i][j]--;
                return;
            }
            else {
                row[i]++;
                col[j]++;
                main_diag[i + j]++;
                side_diag[field_size - i + j]++;
                arr[i][j]++; // только для визуализации
                cnt++;

                row[i] == 2 ? get_count(i + 1, 0) : get_count(i, j + 1);

                row[i]--;
                col[j]--;
                main_diag[i + j]--;
                side_diag[field_size - i + j]--;
                arr[i][j]--; // только для визуализации
                cnt--;
            }
        }
    }
}

int main() {

    setlocale(LC_ALL, "ru");

    cout << "Введите размер поля: ";

    cin >> field_size;


    // этот массив нужен только для визуализации, если не надо - можно не заполнять его
    arr = new int* [field_size];

    for (int i = 0; i < field_size; ++i) {
        arr[i] = new int[field_size] {};
    }

    max_count = field_size * 2;

    row = new int[field_size] {};

    col = new int[field_size] {};

    main_diag = new int[field_size * 2] {};

    side_diag = new int[field_size * 2] {};

    get_count();
    cout << endl << "Количество расстановок: " << result << endl;

    for (int i = 0; i < field_size; ++i) {
        delete[] arr[i];
    }

    delete[] arr, row, col, main_diag, side_diag;
}