# Python backtracking and space efficient solution - Easy to understand!

• 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

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