Accepted backtracking Python solution. Very similar to the solution to N Queens I.


  • 2
    X
    class Solution:
        # @return an integer
        def totalNQueens(self, n):
            self.num = 0
            self.board = [["." for x in range(n)] for x in range(n)]
            self.n = n
            self.solve(0)
            return self.num
        
        def solve(self, col):
            if col == self.n:
                self.num += 1
                return
                
            for row in range(self.n):
                if self.isSafe(row, col):
                    self.board[row][col] = "Q"
                    self.solve(col+1)
                    self.board[row][col] = "."
            
        def isSafe(self, row, col):
            for c in range(col):
                if self.board[row][c] == "Q":
                    return False
            rup = row-1
            rdown = row+1
            c = col-1
            while c >= 0:
                if rup >= 0:
                    if self.board[rup][c] == "Q":
                        return False
                if rdown < self.n:
                    if self.board[rdown][c] == "Q":
                        return False
                rup -= 1
                rdown += 1
                c -= 1
            return True
    

    Just changed from appending all possible boards to self.result to incrementing self.num by 1 every time when a possible board is found.


Log in to reply
 

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