Python short backtracking solution easy to understand


  • 0
    I
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        self.res,self.size=[],n
        self.backtrack([])
        return self.res
        
    def backtrack(self,positions):
        if len(positions)==self.size:
            self.res.append(['.'*i+'Q'+'.'*(self.size-i-1) for i in positions])
            return
        for j in range(self.size):
            if not positions:
                self.backtrack([j])
                continue
            if j in positions: continue
            i=len(positions)
            isValid=True
            for m,n in enumerate(positions):
                if (i-j)==(m-n) or (i+j)==(m+n): 
                    isValid=False
                    break
            if isValid: self.backtrack(positions+[j])

Log in to reply
 

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