using namespace std;

class Solution {

    bool is_not_under_attack(vector<vector<int>>& board, int& row, int& col)
    {
        bool answer { true };
        if (board.at(row).at(col) != 0) {
            answer = false;
        }
        return answer;
    }

    void place_queen(vector<vector<int>>& board, const int& n, int row, int col)
    {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board.at(i).at(j) == 0 && (i == row || j == col || (i - row == j - col) || (i + j == col + row))) {
                    board.at(i).at(j) = 1;
                }
            }
        }
    }

    void remove_queen(vector<vector<int>>& board, const int& n, int row, int col)
    {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board.at(i).at(j) != 0 && (i == row || j == col || (i - row == j - col) || (i + j == col + row))) {
                    board.at(i).at(j) = 0;
                }
            }
        }
    }

    int backtrack_nqueens(vector<vector<int>>& board, const int& n, int row, int count)
    {
        for (int col = 0; col < n; ++col) {
            if (is_not_under_attack(board, row, col)) {
                place_queen(board, n, row, col);
                if (row + 1 == n) {
                    ++count;
                } else {
                    count = backtrack_nqueens(board, n, row + 1, count);
                }
                remove_queen(board, n, row, col);
            }
        }
        return count;
    }

public:
    int totalNQueens(int n)
    {
        vector<vector<int>> board(n, vector<int>(n, 0));
        int answer = backtrack_nqueens(board, n, 0, 0);
        return answer;
    }
};
int main()
{

    int n { 4 };

    Solution obj;
    int answer = obj.totalNQueens(n);
    cout << answer << endl;

    return 0;
}