## Description

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.


## Solutions

### 1. Backtracking

res 记录每个 queen 在每一行的位置。有如下几个特点：

1. 正斜线（左下向右上）数组，该斜线特点为：斜线上每一格的行加列的和一定
2. 反斜线（左上向右下）数组，该斜线特点为：斜线上每一格的行减列的差一定

N 皇后问题的难点是要记录这正斜线和反斜线的结果，用于回溯剪枝。

# Time: O(n^2)
# Space: O(n)
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
if n <= 0:
return []
res = []
self.dfs(n, [], [], [], res)
return [['.' * i + 'Q' + (n - i - 1) * '.' for i in sol] for sol in res]

def dfs(self, n, xydiff_diag, xysum_diag, queens, res):
# q is the current row index, queen store every column position of a queen
r = len(queens)
if r == n:
res.append(queens)
return

# check every column position, c is the test column index
for c in range(n):
if c in queens or r - c in xydiff_diag or r + c in xysum_diag:
continue
self.dfs(n, xydiff_diag + [r - c], xysum_diag + [r + c], queens + [c], res)
# 9/9 cases passed (52 ms)
# Your runtime beats 97 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13 MB)