Python backtracking and space efficient solution - Easy to understand!


  • 0
    S

    The interesting part of my solution is how storing previous queens is handled. I use a dictionary of previous positions instead of a 2D grid.

    class Solution(object):
        def recurse(self, row, solution, queens, n):
            if len(queens) == n:
                return solution.append(dict(queens))
            
            # "row" also serves as the queen count
            for col in range(n):
                # can another queen attack this placement?
                col_is_free = col not in queens
                diag_is_free = True
                for _, position in queens.items():
                    q_row, q_col = position
                    if abs(row - q_row) == abs(col - q_col):
                        diag_is_free = False
                # row is assumed to be free since we drop down from top of board
                if col_is_free and diag_is_free:
                    queens[col] = (row, col)
                    self.recurse(row + 1, solution, queens, n)
                    del queens[col]
                    
        def draw_boards(self, solution, n):
            # takes a dict of queen configerations and generates the boards
            boards = []
            for queens in solution:
                board = [['.' for y in range(n)] for x in range(n)]
                for _, position in queens.items():
                    row, col = position
                    board[col][row] = 'Q'
                boards.append([''.join(row) for row in board])
            return boards
    
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            if n == 0:
                return []
        
            # list of map of queen configerations (map of col -> (row, col))
            solution = []  
            self.recurse(0, solution, {}, n)
                
            boards = self.draw_boards(solution, n)
            return boards
    

    O(N!) time complexity and O(N) space complexity


Log in to reply
 

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