The idea is that

- To put n queens in a n by n board, each row should have and can only have exactly one queen. Thus a 4x4 board with 4 queens can be represented as [a, b, c, d], abcd here indicate index of the queen in each row.
- The queen in the new row cannot be in the same column with existing queens, thus d cannot be the same value of a, b, c in the case above.
- The queen in the new row cannot be diagonal to other existing queens. This can be expressed as 3 + d != 2 + a and 3 - d != 2 - a.

```
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
results = []
stack = [([], set(), set())]
while stack:
queens, diff, sums = stack.pop()
if len(queens) == n:
results.append(queens)
continue
for q in range(n):
minus = len(queens) - q
add = len(queens) + q
if q in queens or minus in diff or add in sums:
continue
stack.append((queens + [q], diff | set([minus]), sums | set([add])))
return [['.' * q + 'Q' + '.' * (n - q - 1) for q in queens] for queens in results]
```