leetcode51-N皇后

leetcode 51

思路

本题可以使用回溯算法来解决。回溯算法通过尝试所有可能的解决方案来找到问题的解的算法，当发现当前的选择无法得到有效的解决方案时，就回溯到上一步，尝试其他的选择。对于 N 皇后问题，我们可以逐行放置皇后，在每一行选择一个合适的列来放置皇后，若当前选择导致冲突，就回溯到上一行，重新选择列

初始化棋盘

const dashboard = Array(n).fill().map(() => Array(n).fill('.'));

• dashboard 是一个 n×n 的二维数组，初始时每个位置都用 . 表示，表示该位置没有放置皇后

回溯函数

const backtracking = (dashboard, n, row) => {if (row === n) {result.push(dashboard.map(item => item.join('')))return;}for (let i = 0; i < n; i++) {if (isValid(dashboard, row, i, n)) {dashboard[row][i] = 'Q'backtracking(dashboard, n, row + 1)dashboard[row][i] = '.'}}
}

• 终止条件：当 row 等于 n 时，说明已经成功地在每一行都放置了一个皇后，此时将当前的棋盘布局加入到 result 数组中
• 遍历列：对于当前行 row，尝试在每一列 i 放置皇后
• 检查合法性：调用 isValid 函数检查在 (row, i) 位置放置皇后是否合法
• 递归：如果合法，将皇后放置在 (row, i) 位置，然后递归调用 backtracking 函数处理下一行
• 回溯：递归返回后，将 (row, i) 位置的皇后移除，恢复为 .，以便尝试其他列

棋盘的合法性校验：关键！！！

const isValid = (dashboard, row, col, n) => {if (row === 0) { return true }// 判断是否在同一列for (let i = 0; i < row; i++) {if (dashboard[i][col] === 'Q') {return false}}// 判断是否在45度角for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (dashboard[i][j] === 'Q') {return false}}// 判断是否是135度角for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (dashboard[i][j] === 'Q') {return false}}return true
}

• 第一行：如果 row 为 0，说明是第一行，任何位置都可以放置皇后，直接返回 true
• 列检查：检查当前列 col 上是否已经有皇后，如果有则返回 false
• 45 度斜线检查：从当前位置 (row, col) 向左上方遍历，如果发现有皇后则返回 false
• 135 度斜线检查：从当前位置 (row, col) 向右上方遍历，如果发现有皇后则返回 false
• 合法：如果以上检查都通过，则返回 true，表示该位置可以放置皇后

完整实现

var solveNQueens = function (n) {let result = [];// 初始化棋盘const dashboard = Array(n).fill().map(() => Array(n).fill('.'));const backtracking = (dashboard, n, row) => {if (row === n) {result.push(dashboard.map(item => item.join('')))return;}for (let i = 0; i < n; i++) {if (isValid(dashboard, row, i, n)) {dashboard[row][i] = 'Q'backtracking(dashboard, n, row + 1)dashboard[row][i] = '.'}}}backtracking(dashboard, n, 0)return result;
}const isValid = (dashboard, row, col, n) => {if (row === 0) { return true }// 判断是否在同一列for (let i = 0; i < row; i++) {if (dashboard[i][col] === 'Q') {return false}}// 判断是否在45度角for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (dashboard[i][j] === 'Q') {return false}}// 判断是否是135度角for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (dashboard[i][j] === 'Q') {return false}}return true
}