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 = 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