Python code using backtracking


  • 0
    H
    class Solution(object):
        def totalNQueens(self, n):
            """
            :type n: int
            :rtype: int
            """
            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, num):
                '''
                x: row index
                Q_index: a list of currently added Qs
                num: number of found solutions
                '''
                if x >= n:
                    return num+1
                # 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
                        num = backtrack(n, x+1, Q_index+[(x,y)], num) 
                return num
            
            if n == 1:
                return 1
            elif n <=3:
                return 0
            
            return backtrack(n, 0, [], 0)
    

Log in to reply
 

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