# Clean Non-Recursive python solution using backtracking with comments

• 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
``````

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