The **n-queens** puzzle is the problem of placing `n`

queens on an `n x 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 1:**

**Input:** n = 4

**Output:** [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

**Explanation:** There exist two distinct solutions to the 4-queens puzzle as shown above

**Example 2:**

**Input:** n = 1

**Output:** [["Q"]]

**Constraints:**

`1 <= n <= 9`

‘.’ * n = ‘……’

a = []

a + [‘abc’] == a.append([‘abc’])

[1,2,3] + [3,2,1] = [1,2,3,3,2,1]

can only concatenate list to list

check for diagnal? x and y will be the same in the square

Solution

`class Solution(object):`

def solveNQueens(self, n):

“””

:type n: int

:rtype: List[List[str]]

“””

self.res = []

def dfs(nums, index, ans):

if index == len(nums):

self.res.append(ans)

return

for i in range(len(nums)):

nums[index] = i

if isValid(nums, index):

temp = “.”*len(nums)

dfs(nums, index+1, ans + [temp[:i]+”Q”+temp[i+1:]])

def isValid(nums, index):

for i in range(index):

if nums[i] == nums[index] or abs(nums[i] — nums[index]) == index — i:

return False

return True

dfs([-1]*n, 0, [])

return self.res