问题：在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; } } } };
