<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:
    def getBoard(self, sol, n):
        board = [['.']*n for _ in range(n)]
        for s in sol:
            board[s[0]][s[1]] = 'Q'
        return [''.join(row) for row in board]

    def totalNQueens(self, n: int) -> List[List[str]]:
        rows = list(range(n))
        cols = set(range(n))
        q = [(cols, 0, set())]

        res = 0
        while q:
            # print(q)
            cur_cols, next_row, taken = q.pop()
            if not cur_cols:
                res += 1
                continue
            
            for c in cur_cols:
                if (next_row, c) in taken:
                    continue
                new_taken = set(taken)
                for i in range(1, n - next_row):
                    left_c = c - i
                    right_c = c + i
                    f_row = next_row + i
                    if left_c >= 0:
                        new_taken.add((f_row, left_c))
                    if right_c < n:
                        new_taken.add((f_row, right_c))
                    if f_row < n:
                        new_taken.add((f_row, c))

                next_cols = set(cur_cols)
                next_cols.remove(c)

                # next_sol = list(sol)
                # next_sol.append((next_row, c))
                q.append((next_cols, next_row+1, new_taken))
        # print(res)
        return res
16800