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.
- The board is initialized as all '_'s. Any symbol besides 'Q' and '.' will work;
- Since no Queens can stay in the same row obviously, we search for each row incrementally;
- 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