在 N-Queens 的基础上计算出共同拥有多少种不同的解法。
注意点:
样例:
输入: n = 8
输出: 92
思路与 N-Queens 一样。只是把原先用来最后拼装的參数之类都去掉了。换了一个计数器来记录数量。
- class Solution(object) : def totalNQueens(self, n) : """
- :type n: int
- :rtype: int
- """self.col = [False] * n self.diag = [False] * (2 * n) self.anti_diag = [False] * (2 * n) self.result = 0 self.recursive(0, n) return self.result
- def recursive(self, row, n) :
- if row == n: self.result += 1
- else: for i in range(n) : if not self.col[i] and not self.diag[row + i] and not self.anti_diag[n - i + row] : self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = True self.recursive(row + 1, n) self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = False
- if __name__ == "__main__": assert Solution().totalNQueens(8) == 92
欢迎查看我的 Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。
来源: http://www.bubuko.com/infodetail-2226812.html