求出在 N * N的棋盤放上 N 個彼此無法互吃的解法數量。
最直觀的就是暴力解法，若 N = 4，就會有 16 格，於是第一步的可能下法就會有16種。
取出前面的結果，找出第二步下法的地方，得到第二步符合規則的所有下法，依序往下傳。
傳到第 N 步下完後，剩下多少種不相同的可行下法就是解答。(這樣會找到重複解。
這種暴力解法多計算了不需要的「流程」，每一步先後順序都沒有差。
換一種想法，有沒有更快速的下法？
每排上面一定有一個皇后，於是可以逐排安排皇后。
在逐排之下，要是該欄可以放皇后，就往下排從頭搜尋，到底則次數+1，不行則取走上排的皇后，退回上排再往下一欄搜尋。
回去偷看一下範例，才想到這樣的解法。(誰叫我當初選擇跳過不看呢，呵呵。
class Solution:
def totalNQueens(self, n: int) -> int:
def is_not_under_attack(Queens, y, x):
for queen in Queens:
qy, qx = queen
if qy == y: return False
if qx == x: return False
if abs(qx-x) == abs(qy-y): return False
return True
Queens = []
row, col = 0, 0
count = 0
while col <= n:
#print(row,col)
if col == n:
# remove queen
if Queens:
row, col = Queens.pop()
col = col+1
else: break
elif row == n:
count += 1
row, col = Queens.pop()
col = col+1
elif is_not_under_attack(Queens, row, col):
# place queen
Queens.append((row,col))
row, col = row + 1, 0
else:
col += 1
return count
當走到最後一排，順利放完就會觸發超出排數，這代表順利找到一個解法，成功將 N 個皇后放在棋盤上。取走上一個的皇后，然後繼續搜尋。
當走到最後一欄，超出欄數，就代表該排無法放置皇后，取走上一個皇后。如果在第 0 排，沒有皇后可取，就跳出迴圈，回傳計數。
有了這種思路，解答速度就會有所保證，接下來就是優化，讓速度更快速。
class Solution:
def totalNQueens(self, n: int) -> int:
result = []
queens, xy_sum, xy_dif = {}, {}, {}
def searchNext(row):
if row == n:
result.append("")
else:
for col in range(n):
xyS = row + col
xyD = row - col
if not col in queens and not xyS in xy_sum and not xyD in xy_dif:
queens[col] = xy_sum[xyS] = xy_dif[xyD] = None
searchNext(row+1)
del queens[col], xy_sum[xyS], xy_dif[xyD]
searchNext(0)
return len(result)
用了一個串列 result 接收結果，要解法可以添加 queens 當下所有鍵，只要解法數目最後用 len() 就能得到所有解的數目，要添加甚麼到result就隨便喜好。
這不得不說是參考前段班大神的解法，用xy相加與相減就能快速找到是否在斜線上，由於是一排排的下，所以也不會有同排(同y)的狀況要排除。
考慮到「查值是否存在」的速度差異，使用字典比起串列還快不少，所以都換成字典，畢竟只會使用 in 去查鍵是否存在，該鍵的值是甚麼就不重要。
在串列使用 append() 添加比 + 還快，用 + 會回傳一個新串列，如果沒有需要新生成或是有別的辦法替代，先用 append() 再傳會比較快。
這優化解法一開始就會直接到深處開始，不像前面的解法是一排排往下找，相快速度跟代碼長度就會快很多跟少很多。找完就刪掉最後一項(最後下的Queen)然後往右下一欄，走完所有欄，就會回上層繼續。