原題

根據(jù)n皇后問題，現(xiàn)在返回n皇后不同的解決方案的數(shù)量而不是具體的放置布局。

樣例
比如n=4，存在2種解決方案

解題思路

• 比N-Queens還要簡(jiǎn)單一些，因?yàn)椴恍枰嫵鯾oard，只需要維護(hù)一個(gè)全局變量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