一直都没会几道hard题，难得解出一道，分享一下题解。

Leetcode原题：https://leetcode-cn.com/problems/eight-queens-lcci

题目描述

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

解题思路

N皇后问题是一种搜索问题，每次摆放一个位置，会有多种可能。而每一步的选择将会影响下一步的可选范围。比如说有四个皇后的话，摆放第三个皇后的时候显然会受到前两个摆放过的皇后的位置的约束。这时我们可以做剪枝等操作，及时停止并回溯，回避那些不可能进行下去的选择，将会省去很多时间。
Leetcode上这道N皇后也经过了改编，对于存在多种结果的N皇后问题，要将存在的结果都返回，采用递归将会简化我们的代码（迭代不好写，把自己给绕进去了）。
因此，我们采用DFS去寻找答案，并通过回溯寻找更多的可能，也就是回溯搜索。

Code

var solveNQueens = function(n) {let ans=[],// 摆放结果col=[],// 已摆放过的列下标dia1=[],// 已摆放过皇后的对角线1的下标（列）dia2=[]// 已摆放过皇后的对角线2的下标（列）// 在选择对应的格子放置皇后之后，更新三个数组let record=(rowIndex,columnIndex,bool)=>{col[columnIndex]=bool;dia1[rowIndex+columnIndex]=bool;// 对角线（左下到右上）dia2[rowIndex-columnIndex]=bool;// 对角线（左上到右下）}// 在某一行摆放一个皇后let setQueen=(rowIndex,prev)=>{// 遍历完毕，说明全部摆放成功，保存结果if(rowIndex==n){ans.push(setResult(prev))return}for(let columnIndex=0;columnIndex<n;columnIndex++){// 判断列上是否已摆放过let columnNotConflict=!col[columnIndex];// 判断对角线1上是否已摆放过let dia1NotConflict=!dia1[rowIndex+columnIndex];// 判断对角线2上是否已摆放过let dia2NotConflict=!dia2[rowIndex-columnIndex];if(columnNotConflict&&dia1NotConflict&&dia2NotConflict){// 记录当前行record(rowIndex,columnIndex,true);// 进入下一行的递归setQueen(rowIndex+1,prev.concat(columnIndex));// 递归出栈，清除当前行的标记，防止污染其他循环record(rowIndex,columnIndex,false);}}}setQueen(0,[]);// 从[0,0]作为入口，开始尝试return ans;
};
// 生成结果矩阵
function setResult(row){let n=row.length;let res=[]for(let i=0;i<n;i++){// 生成行let cur="";for(let j=0;j<n;j++){if(j==row[i]){cur+="Q";}else{cur+=".";}}res.push(cur)}return res;
}