Clean Non-Recursive python solution using backtracking with comments


  • 0
    S

    Here is a non-recursive version.

    class Solution(object):
        def solveNQueens(self, n):
            ret = []
            grid = [['.']*n for _ in xrange(n)]
    
            # Use three lists to track if a queen can be placed
            col = [0] * n
            left_diag = [0] * (2*n-1)
            right_diag = [0] * (2*n-1)
    
            # A stack to do backtracking
            stack = []
            r = 0
            j = 0
            while 1:
                if r < n and j < n:
                    if self.can_place_queen(n, r, j, col, left_diag, right_diag):
                        # If a queen can be placed at (r,j)
                        self.place_queen(n, r, j, col, left_diag, right_diag, grid)
                        stack.append(j)
                        j = 0
                        r += 1
                    else:
                        j += 1
                else:
                    # backtracking
                    if r == n:
                        # Find a solution
                        ret.append([''.join(row) for row in grid])
                    if not stack:
                        # End
                        break
                    # Backtracking to last row and set j to last_j+1
                    r -= 1
                    j = stack.pop()
                    self.remove_queen(n, r, j, col, left_diag, right_diag, grid)
                    j += 1
            return ret
    
        def can_place_queen(self, n, r, j, col, left_diag, right_diag):
            return not col[j] and not left_diag[r + j] and not right_diag[n - 1 - r + j]
    
        def place_queen(self, n, r, j, col, left_diag, right_diag, grid):
            grid[r][j] = 'Q'
            col[j] = 1
            left_diag[r + j] = 1
            right_diag[n - 1 - r + j] = 1
    
        def remove_queen(self, n, r, j, col, left_diag, right_diag, grid):
            grid[r][j] = '.'
            col[j] = 0
            left_diag[r + j] = 0
            right_diag[n - 1 - r + j] = 0
    

Log in to reply
 

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