n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
提示：
- 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。（引用自 百度百科 – 皇后 ）
**难度**: Hard
**标签**: 回溯算法、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：56 ms, 在所有 Python3 提交中击败了80.87% 的用户
内存消耗：13.9 MB, 在所有 Python3 提交中击败了8.27% 的用户
解题思路：
回溯
同N皇后解题思路，但由于只需要计算题解数量
"""
class Solution:
def totalNQueens(self, n: int) -> int:
col = []
obl1 = []
obl2 = []
result = [0]
def backtrack(i:int, current:int):
if current == n:
result[0] += 1
return
for j in range(n):
if j not in col and j-i not in obl1 and j+i not in obl2:
col.append(j)
obl1.append(j-i)
obl2.append(j+i)
current += 1
backtrack(i+1, current)
current -= 1
col.pop()
obl1.pop()
obl2.pop()
backtrack(0, 0)
return result[0]