python ordinary solution works OK (102ms)


  • 0
    Z
    class Solution:    
        # @return a list of lists of string
        def solveNQueens(self, n):
            self.result=[] # stores the position of Queens at each row
            for i in range(n):            
                self.check([i],n)        
            return self.output(self.result,n)
            
        def check(self, Qs,n): 
            ql=len(Qs)
            if ql==n: # the condition to end
                self.result.append(Qs)
                return
            for i in range(n): # the loop of choosing the current pos
                if i in Qs: # should not be another Queen in the same column
                    continue
                else:
                    success=True
                    for j,Qj in enumerate(Qs):
    # the key requirement to continue to next row
    # namely we do not accept a previous Queen which already occupied a 
    # diagonal line of the current position
                        if i==Qj+ql-j or i==Qj-ql+j: 
                            success=False
                            break                        
                    if success:  # Qj loop finishes
                        Qs2=Qs[:] # a copy of Qs                  
                        Qs2.append(i)                   
                        self.check(Qs2,n)
              
    
        def output(self,Qs,n):
            out=[]
            for qs1 in Qs: # qs1 is a list 
                temp1=[]
                for i in qs1:
                    temp=''
                    temp+='.'*i + 'Q' + '.'*(n-i-1)
                    temp1.append(temp)
                out.append(temp1)
          
            return out
    

Log in to reply
 

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