<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 {
public:
    struct State {
        int c_i = 0;
        int c_j = 0;
        int queen = 0;
        vector<vector<bool>> can_attack;

        explicit State(int n) {
            can_attack = vector<vector<bool>>(n, vector<bool>(n, false));
        }
    };
    int totalNQueens(int n) {
        stack<State> st;
        st.push(State(n));

        int result = 0;
        while (!st.empty()) {
            State s = st.top();
            st.pop();
            if (s.queen == n) {
                result++;
                continue;
            }
            // cout << "getting queen at " << s.c_i << " " << s.c_j << " "
            //      << s.queen << endl;

            for (int i = 0; i < n; ++i) {
                int j = s.c_j;
                if (s.can_attack[i][j]) {
                    continue;
                }
                if (j + 1 > n) {
                    continue;
                }
                State next = s;
                for (int a = 0; a < n; ++a) {
                    next.can_attack[a][j] = true;
                    next.can_attack[i][a] = true;
                }

                // up and right
                int a = 1;
                while (i + a < n && j + a < n) {
                    next.can_attack[i + a][j + a] = true;
                    a++;
                }

                // down and left
                a = 1;
                while (i - a >= 0 && j - a >= 0) {
                    next.can_attack[i - a][j - a] = true;
                    a++;
                }

                a = 1;
                while (i - a >= 0 && j + a < n) {
                    next.can_attack[i - a][j + a] = true;
                    a++;
                }

                a = 1;
                while (i + a < n && j - a >= 0) {
                    next.can_attack[i + a][j - a] = true;
                    a++;
                }

                next.c_i = i;
                next.c_j = j + 1;
                next.queen++;
                // cout << "placing queen at " << next.c_i << " " << j << " "
                //      << next.queen << endl;
                st.push(next);
            }
        }
        return result;
    }
};
39287