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

def leftdiag(pos, placed, n):
    (x, y) = pos
    while x > 0 and y > 0:
        # reduce x and y and check if any element there.
        x -= 1
        y -= 1
        if (x, y) in placed:
            return True
    return False

def rightdiag(pos, placed, n):
    (x, y) = pos
    while x > 0 and y < n:
        # reduce x and y and check if any element there.
        x -= 1
        y += 1
        if (x, y) in placed:
            return True
    return False


def nq2(n):
    cols = set({})
    placed = set({})

    def helper(row_idx):
        c = 0
        for col in range(n):
            if col in cols:
                continue
            # check left upper
            if leftdiag((row_idx, col), placed, n) or rightdiag((row_idx, col), placed, n):
                continue
            placed.add((row_idx, col))
            cols.add(col)

            if row_idx == n - 1:
                c += 1
            else:
                c += helper(row_idx + 1)                
            placed.remove((row_idx, col))
            cols.remove(col)
        return c

    return helper(0)
    
    
    
class Solution:
    def totalNQueens(self, n: int) -> int:
        return nq2(n)
16400