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]