#include <iostream>

using namespace std;

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


void get_count(int i = 0, int k = 0) { // i - номер строки
    for (int j = k; j < field_size; ++j) { // j - номер столбца
        if (row[i] < 2 && col[j] < 2 && main_diag[i + j] < 2 && side_diag[field_size - i + j] < 2) {

            if (cnt == max_count - 1) {
                result++;
                return;
            }
            else {
                row[i]++;
                col[j]++;
                main_diag[i + j]++;
                side_diag[field_size - 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]--;
                cnt--;
            }
        }
    }
}

int main() {

    setlocale(LC_ALL, "ru");

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

    cin >> 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;

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