def solveNQueens(self, n): res =  self.dfs([-1]*n, 0, , res) return res # nums is a one-dimension array, like [1, 3, 0, 2] means # first queen is placed in column 1, second queen is placed # in column 3, etc. def dfs(self, nums, index, path, res): if index == len(nums): res.append(path) return # backtracking for i in xrange(len(nums)): nums[index] = i if self.valid(nums, index): # pruning tmp = "."*len(nums) self.dfs(nums, index+1, path+[tmp[:i]+"Q"+tmp[i+1:]], res) # check whether nth queen can be placed in that column def valid(self, nums, n): for i in xrange(n): if abs(nums[i]-nums[n]) == n -i or nums[i] == nums[n]: return False return True
Python recursive dfs solution with comments.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.