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


  • 0
    M

    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

Log in to reply
 

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