原題
根據(jù)n皇后問題，現(xiàn)在返回n皇后不同的解決方案的數(shù)量而不是具體的放置布局亏拉。
樣例
比如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
