Python code using backtracking


  • 0
    H
    class Solution(object):
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            def check(n, x, y, Q_index):
                '''
                check existing Qs if we add a Q at (x,y)
                '''
                for i, j in Q_index:
                    if y==j or x+y==i+j or x-y==i-j:    # check column and diagnal
                        return False
                return True
            
            def backtrack(n, x, Q_index, mat):
                '''
                x: row index
                Q_index: a list of currently added Qs
                '''
                if x >= n:
                    board = ['.'*j + 'Q' + '.'*(n-1-j) for i,j in Q_index]  # create a board according to Q_index
                    mat.append(board)   # add the board to result list 
                    return 
                # try possible positions at this row
                for y in xrange(n):
                    if check(n, x, y, Q_index):
                        # add (x,y) to Q_index and treat the next row
                        backtrack(n, x+1, Q_index+[(x,y)], mat) 
                return 
            
            if n == 1:
                return [['Q']]
            elif n <=3:
                return []
            res = []
            backtrack(n, 0, [], res)
            
            return res
    

Log in to reply
 

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