题目：
难度：Hard
相关话题：回溯算法
n 皇后问题研究的是如何将 n 个皇后放置在 n ×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n ，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
思路：
基本与NO.51一致，甚至还更简单，不需要提供board去记录每个Q的位置，
定义3个hash，用来保存已经放置的Q能攻击到的范围，分别是col，dia1，dia2(竖线和2对角线)
由于每一行最多只可能存在一个Q，那么如果第i行放置了，那么就继续第i+1行，检查是否有位置能放置。
检查的过程有一个高效的方法，col很简单，关键在两条斜线，可以思考这两条斜线的延长线最终到达第一行的位置。
左下到右上斜线[i,j]延长线最终能到达第一行的位置就是[0,j+i]，因此只需要保存j+i；
左上到右下的斜线[i,j]延长线最终能到达第一行的位置就是[0,j-i]，因此只需要保存j-i。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number} n
* @return {number}
*/
var totalNQueens = function(n) {
let dia1=Array(2*n).fill(false),
dia2=Array(2*n).fill(false),
col=Array(n).fill(false)
let res=0
backtrack(0,0)
return res
function backtrack(setCount,rowId){
if(setCount===n) res++
for(let j=0;j<n;j++){
let lt2rd=j-rowId+n,rt2ld=j+rowId
// 检查竖线，两斜线是否冲突
if(col[j] || dia1[lt2rd] || dia2[rt2ld])continue
col[j]=true
dia1[lt2rd]=true
dia2[rt2ld]=true
backtrack(setCount+1,rowId+1)
dia2[rt2ld]=false
dia1[lt2rd]=false
col[j]=false
}
}
};
扩展阅读：