N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution:

这道题的区别就是不需要把具体方案打印出来，但是还是需要usedColumns变量来动态的存储方案的情况。

class Solution:
    """
    Calculate the total number of distinct N-Queen solutions.
    @param n: The number of queens.
    @return: The total number of distinct solutions.
    """
    def __init__(self):
        self.sum = 0
    def totalNQueens(self, n):
        # write your code here
        usedColumns = [0] * n
        self.dfs(usedColumns, 0)
        return self.sum
    def dfs(self, usedColumns, row):
        n = len(usedColumns)
        if n == row:
            self.sum += 1
            return
        for i in range(n):
            if self.isValid(usedColumns, row, i):
                usedColumns[row] = i 
                self.dfs(usedColumns, row + 1)
    def isValid(self, usedColumns, row, col):
        for i in range(row):
            if usedColumns[i] == col:
                return False
            if row - i == abs(col - usedColumns[i]):
                return False
        return True

回溯法：

class Solution:
    def totalNQueens(self, n: int) -> int:

        attack_zone = []
        directions = [(0,-1), (0,1), (-1,0), (1,0), (-1,1), (1,-1), (1,1), (-1,-1)]

        def is_not_under_attack(row = 0, col = 0):

            if (row, col) in attack_zone:
                return False

            return True

        def place_queen(row = 0, col = 0):

            attack_zone.append((row, col))

            for x, y in directions:

                moveX = row + x
                moveY = col + y

                while moveX >= 0 and moveX < n and moveY >= 0 and moveY < n:

                    attack_zone.append((moveX, moveY))

                    moveX += x
                    moveY += y

        def remove_queen(row = 0, col = 0):

            attack_zone.remove((row, col))

            for x, y in directions:

                moveX = row + x
                moveY = col + y

                while moveX >= 0 and moveX < n and moveY >= 0 and moveY < n:

                    attack_zone.remove((moveX, moveY))

                    moveX += x
                    moveY += y

        def backtrack_nqueen(row = 0, count = 0):

            for col in range(n):

                # iterate through columns at the curent row.
                if is_not_under_attack(row, col):

                    # explore this partial candidate solution, and mark the attacking zone
                    place_queen(row, col)

                    if row + 1 == n:
                        # we reach the bottom, i.e. we find a solution!
                        count += 1
                    else:
                        # we move on to the next row
                        count = backtrack_nqueen(row + 1, count)

                    # backtrack, i.e. remove the queen and remove the attacking zone.
                    remove_queen(row, col)

            return count

        if n == 0:
            return 1

        return backtrack_nqueen()