LeetCode 52 [N-Queens II]

原题

根据n皇后问题，现在返回n皇后不同的解决方案的数量而不是具体的放置布局。

样例
比如n=4，存在2种解决方案

解题思路

• 比N-Queens还要简单一些，因为不需要画出board，只需要维护一个全局变量result
• 完整思路见 N-Queens

完整代码

class Solution(object):
    result = 0
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        cols = []
        self.search(n, cols)
        return self.result
        
    def search(self, n, cols):
        if len(cols) == n:
            self.result += 1
            return
        
        for col in range(n):
            if not self.isValid(cols, col):
                continue
            self.search(n, cols + [col])

    def isValid(self, cols, col):
        currentRowNumber = len(cols)
        for i in range(currentRowNumber):
            # same column
            if cols[i] == col:
                return False
            # left-top to right-bottom
            if i - cols[i] == currentRowNumber - col:
                return False
            # right-top to left-bottom
            if i + cols[i] == currentRowNumber + col:
                return False
        return True