leetcode算法题之N皇后
N皇后也是一道很经典的问题，问题如下：
题目地址
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
解法：回溯
回溯是基于 DFS 的一种算法，它通过在解空间树中深度探索并尝试所有可能的解来解决问题。当发现当前路径无法满足问题的约束条件时，算法会“回溯”到上一步，尝试另一条路径
首先我们先建立一个二维数组，方便我们在回溯时直接更改对应的状态
const dp = new Array(n).fill(0).map(() => new Array(n).fill("."));由当前问题我们可得知棋盘的每行必定要放置一个皇后，不然不会有满足题目的解，所以可以把每一列当作一层，把皇后放置后再到下一层继续放置，基本代码如下
const backtrack = (line) => {// 遍历每一行，放置皇后for (let i = 0; i < n; i++) {dp[line][i] = "Q";backtrack(line + 1)// 回溯的核心，当我们使用完后一定要将状态恢复，不然会影响下一个结果dp[line][i] = ".";}
}backtrack(0);接下来的问题就是我们要怎么判断当前位置可不可以放置皇后，有的童鞋可能想着所有方向都遍历一下，其实不用这么麻烦，因为我们是由上往下放置，所以只需要判断左上，上，右上的方向就可以啦
// 检测位置是否可以放皇后
const checkPosition = (x, y) => {// 检测上方let tx = x;while (--tx > -1) {if (dp[tx][y] === "Q") {return false;}}// 检测上斜左let lx = x,ly = y;while (--lx > -1 && --ly > -1) {if (dp[lx][ly] === "Q") {return false;}}// 检测上斜右let rx = x,ry = y;while (--rx > -1 && ++ry < n) {if (dp[rx][ry] === "Q") {return false;}}return true;
};既然说到回溯，那肯定涉及到剪枝问题了，其实也不用做啥，当我们发现某一行无法放置任何皇后时，我们什么都不做，直接回溯到上一行即可
完整代码如下：
/*** @param {number} n* @return {string[][]}*/
var solveNQueens = function (n) {let dp = new Array(n).fill(0).map(() => new Array(n).fill("."));const result = [];let queenNum = n;// 检测位置是否可以放皇后const checkPosition = (x, y) => {// 检测上方let tx = x;while (--tx > -1) {if (dp[tx][y] === "Q") {return false;}}// 检测上斜左let lx = x,ly = y;while (--lx > -1 && --ly > -1) {if (dp[lx][ly] === "Q") {return false;}}// 检测上斜右let rx = x,ry = y;while (--rx > -1 && ++ry < n) {if (dp[rx][ry] === "Q") {return false;}}return true;};const pushResult = () => {let newDp = [];for (let i = 0; i < n; i++) {newDp[i] = dp[i].join("");}result.push(newDp);};const backtrack = (line) => {if (line === n) {pushResult();return;}for (let i = 0; i < n; i++) {// 判断是否可以放置皇后if (line === 0 || (line > 0 && checkPosition(line, i))) {dp[line][i] = "Q";backtrack(line + 1);dp[line][i] = ".";}}};backtrack(0);return result;
};