【详细】经典N-皇后问题的回溯解法

问题在n x n的棋盘大小放置n个皇后使得这n个皇后不能相互攻击找出所有摆放方案。坐标系设置原点棋盘的左上角。col轴方向向右。row轴方向向下。主对角线从原点出发的对角线解析方程为 row col故主对角线的点row - col为定值0。次对角线与主对角线垂直的对角线解析方程为 row -col n 故次对角线的点row col 为定值n。用到的方法join方法将一个数组变成字符串map方法对数组的各元素进行相同的操作并返回新数组。棋盘(board)使用二维数组标记每一行是一个子数组而output要求每一行以字符串输出故回溯终止时res.push(board.map((row) row.join()))./** * param {number} n * return {string[][]} */ var solveNQueens function(n) { //初始化棋盘其中Q代表皇后.代表空位 const board Array.from({ length: n }, () Array(n).fill(.)); const cols Array(n).fill(false); const diags1 Array(2 * n - 1).fill(false); const diags2 Array(2 * n - 1).fill(false); const res []; backtrack(0, n, board, res, cols, diags1, diags2); return res; function backtrack(row, n, board, res, cols, diags1, diags2){ //回溯结束条件放置完所有行 if (row n) { res.push(board.map((row) row.join())); return; } // 遍历所有列 for (let col 0; col n; col) { // 计算该格子对应的主对角线和次对角线 const diag1 row - col n - 1; const diag2 row col; // 列剪枝和对角线剪枝 if(!cols[col] !diags1[diag1] !diags2[diag2]) { // make choice board[row][col] Q; cols[col] diags1[diag1] diags2[diag2] true; // explore backtrack(row 1, n, board, res, cols, diags1, diags2); // undo choice board[row][col] .; cols[col] diags1[diag1] diags2[diag2] false; } } } };