# N-Queens

N-Queens

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 = 4Output: [[".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 = 1Output: [["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`