# Python, Simple solution with Comments beats 75%. Let me know if you know how to accelerate.

• The idea is back tracking. For each recursion, the current position is marked as 'Q' and positions under attack is marked as '.'. Backtrack if there is no possible position. Append the current board to results if all n Queens are added to the board.

Notice:

1. The board is initialized as all '_'s. Any symbol besides 'Q' and '.' will work;
2. Since no Queens can stay in the same row obviously, we search for each row incrementally;
3. The board is restored to previous status (backtracking) using a buff called oldBoard.

'''

``````def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.res = [] # List to append all possible results
board = [['_']*n for _ in xrange(n)] # initialization of board
self.putQueen(board, 0, n) # recursive and backtracking
return self.res

def putQueen(self, board, i, n):
'''
:type board: List[List[str]]
:type i: int current row index
:type n: int total number of Queens
'''
if i == n:
board = [''.join(x) for x in board]
self.res.append(board)
return

oldBoard = [x[:] for x in board]
for j in xrange(n):
if board[i][j] != '.':
board[i] = ['.']*n # mark rows
for k in xrange(i+1, n): # mark columns
board[k][j] = '.'
for k in xrange(1, n-i): # mark diagonal
if j+k<n:
board[i+k][j+k] = '.'
if j-k>=0:
board[i+k][j-k] = '.'
board[i][j] = 'Q'
self.putQueen(board, i+1, n)
board = [x[:] for x in oldBoard]
return``````

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