N-Queens

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
Input: n = 1
Output: [["Q"]]
  • 1 <= n <= 9
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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store