回溯法

思路:

参考51.N皇后

 

代码:

class Solution:
    def totalNQueens(self, n: int) -> int:
        def could_place(row,col):
            return not(cols[col]+hill_diagonal[row-col]+dale_diagonal[row+col])
        def place_queen(row,col):
            cols[col] = 1
            hill_diagonal[row-col] = 1
            dale_diagonal[row+col] = 1
        def remove_queen(row,col):
            cols[col] = 0
            hill_diagonal[row-col] = 0
            dale_diagonal[row+col] = 0
        def backtrack(row = 0,count = 0):
            for col in range(n):
                if could_place(row,col):
                    place_queen(row,col)
                    if row + 1 == n:
                        count += 1
                    else:
                        count = backtrack(row+1,count)
                    remove_queen(row,col)
            return count
        cols = [0]*n
        hill_diagonal = [0]*(2*n-1)
        dale_diagonal = [0]*(2*n-1)
        return backtrack()