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:

‘.’ * 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