<p>The <strong>n-queens</strong> puzzle is the problem of placing <code>n</code> queens on an <code>n x n</code> chessboard such that no two queens attack each other.</p>

<p>Given an integer <code>n</code>, return <em>the number of distinct solutions to the&nbsp;<strong>n-queens puzzle</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;" />
<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are two distinct solutions to the 4-queens puzzle as shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 9</code></li>
</ul>

class Solution {
private:
    int ans;

    bool validQueenPosition(int row, int n, const vector<string>& board, int x, int y) {
        if (board[x][y] != 'Q') {
            return false;
        }

        // check in the row that there are no more queens
        int queens = 0;
        for (int i = 0; i < row; i++) {
            queens += board[i][y] == 'Q' ? 1 : 0;
        }
        if (queens != 1) {
            return false;
        }

        // check in the column that there are no more queens
        queens = 0; 
        for (int i = 0; i < n; i++) {
            queens += board[x][i] == 'Q' ? 1 : 0;
        }
        if (queens != 1) {
            return false;
        }

        // check diagonally that there are no queens
        //  - check diagonally up and down on the right
        int x_ = x + 1;
        int y_up = y - 1;
        int y_down = y + 1;
        queens = 0;
        while (true) {
            if (x_ == row) {
                break;
            }
            if (y_up >= 0) {
                queens += board[x_][y_up] == 'Q' ? 1 : 0;
                y_up--;
            }
            if (y_down < n) {
                queens += board[x_][y_down] == 'Q' ? 1 : 0;
                y_down++;
            }
            x_++;
        }
        if (queens != 0) {
            return false;
        }

        //  - check diagnoally up and down on the left
        x_ = x - 1;
        y_up = y - 1;
        y_down = y + 1;
        queens = 0;
        while (true) {
            if (x_ < 0) {
                break;
            }
            if (y_up >= 0) {
                queens += board[x_][y_up] == 'Q' ? 1 : 0;
                y_up--;
            }
            if (y_down < n) {
                queens += board[x_][y_down] == 'Q' ? 1 : 0;
                y_down++;
            }
            x_--;
        }
        if (queens != 0) {
            return false;
        }
        return true;
    }

    bool validBoard(int row, int n, const vector<string>& board) {
        // must have n queens

        // none of them should be in each other's way
        //  - exactly one queen in each row and column
        //  - there are no queens diagonally in either of the directions
        for (int i = 0; i < row; i++) {
            int queens = 0;
            for (int j = 0; j < n; j++) {
                // find the queen, when we do valid queen position
                if (board[i][j] == 'Q') {
                    queens++;
                    auto valid = validQueenPosition(row, n, board, i, j);
                    if (!valid) {
                        return false;
                    }
                }
            }
            if (queens != 1) {
                return false;
            }
        }
        return true;
    }

    void solve(int row, int n, vector<string> elems) {
        if (row == n) {
            if (validBoard(n, n, elems)) {
                ans++;
            }
            return;
        }

        // we can discard few of the possibilities much earlier
        if (!validBoard(row, n, elems)) {
            return;
        }

        // construct the row at `row`
        string r = string(n, '.');
        for (int i = 0; i < n; i++) {
            r[i] = 'Q';
            elems.push_back(r);
            solve(row + 1, n, elems);
            r[i] = '.';
            elems.pop_back();
        }
    }
public:
    int totalNQueens(int n) {
        vector<string> elems;
        solve(0, n, elems);
        return ans;
    }
};
42892