Python code using backtracking

  • 0
    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.