当下最火的前端面试题，回溯算法来了( 二 ) _前端

输入：4
输出：[ [".Q..", Q","Q...","..Q."], ["..Q.","Q...", "...Q", ".Q.."] ]

遍历每一行的每一列，如果当前位置不会产生攻击就记录当前位置并结束本行循环，往下一行走；如果本行没有一个位置能安放，或者已经走完所有行，就回退到上一个安放的位置，继续看此处的下一个位置能否安放，往复循环。
那么，重点是怎么判断当前位置能否安放，在循环中，一行只能放一个，放下之后就立马进入下一行，所以一行中不会有重复的项，那列和对角线呢？我们使用三个数组来分别记录列和主副对角线的使用情况，当某个位置放下一个皇后之后，记录该列到列数组中，此后该列不能使用；
关于对角线：

主对角线规律：x-y=k（行-列=固定值）
副对角线规律：x+y=k（行+列=固定值）
所以，当某个位置放下一个皇后之后，记录当前行+列的值，和行-列的值，此后的位置如果行+列或行-列有与数组中重复的，都不可使用。
代码实现：

var solveNQueens = function(n) {if(n==0) return res;let col = [], main = [], sub = []; // boolean[]let res = []; // string[]let path = []; //number[]dfs(0, path);return res;function dfs(row, path){// 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果if(row == n){const board = convert2board(path);res.push(board);return;}// 针对下标为 row 的每一列，尝试是否可以放置for(let j=0; j<n; j++){if(!col[j] && !main[row-j+n-1] && !sub[row+j]){path.push(j);// 记录该位置的攻击范围col[j] = true;main[row-j+n-1] = true; //加n-1是为了防止数组索引为负数sub[row+j] = true;// 进入下一行dfs(row+1, path);// 回溯, 去掉path中最后一个值，尝试其他选项col[j] = false;main[row-j+n-1] = false;sub[row+j] = false;path.pop();}}}// 输出一个结果function convert2board(path){let board = []; // string[]for(let i=0; i<path.length; i++){let ret = new Array(n).fill('.');ret[path[i]] = 'Q';board.push(ret.join(''))}return board;}};复制代码

回溯算法解题模板通过以上几个问题不难发现，回溯算法解题的要点就是要定义好状态变量，不断对状态进行推进、回退，尝试所有可能的解，并在状态处于递归树的叶子节点时输出此时的方案。

// 简单模版function backtrack(){let res = [];let used = [];function dfs(depth, path){ // depth表示当前所在的阶段// 递归终止条件if(depth === len){res.push(path);return;}// 针对当前depth尝试所有可能的结果for(let i=0; i<len; i++){if(!used[i]){ // 此路不通的标记path.push(nums[i]);used[i] = true;// depth+1 前往下一个阶段dfs(depth+1, path);// 重置本阶段状态，尝试本阶段的其他可能used[i] = false;path.pop();}}}}

【当下最火的前端面试题，回溯算法来了】