88 ms recursive python solution


  • 0
    O
    1. ['.Q..', '...Q', 'Q...', '..Q.'] is represented as [1, 3, 0 ,2]

    2. If we have [1, 3] in the temporary list, we should avoid the elements already in the list.

    3. [1,3] can be seen as two points: (0,1) for 1, (1,3) for 3.

    4. The point (0,1) can attack any points on line x - y = "-1" and x + y = "1". I store "-1" in the list "banned1"
      and "1" in the list "banned2".

       def solveNQueens(self, n):
      
           result = []
           def helper(temp, banned1, banned2):
      
               L = len(temp)
               if L == n:
                   result.append(temp)
                   return
      
               for i in range(n):
                   if i not in temp and L-i not in banned1 and L+i not in banned2:
                       helper(temp +[i], banned1 + [L-i], banned2 + [L+i])
       
           helper([], [], [])
           return map(self.paint, result)

  • 0
    P

    A really excellent solution! But I'm afraid that you missed the paint part when pasting the code. A fuller version following your ideas is:
    class Solution:

    def solveNQueens(self, n):
        self.result = [] # define here
        self.helper([], [], [], n)
        return map(self.paint, self.result)
    
    def helper(self, tmp, banned1, banned2, n):
        L = len(tmp)
        if L == n:
            self.result.append(tmp)
            return
        for i in range(n):
            if i not in tmp and L-i not in banned1 and L+i not in banned2:
                self.helper(tmp +[i], banned1 + [L-i], banned2 + [L+i],n)
    
    def paint(self, array): # here is array as input to acc. map function
        n = len(self.result[0]) # n
        res = []
        for x in array:
            res.append("."*x + "Q" + "."*(n-x-1))
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.