leetcode51-N皇后
leetcode 51https://i-blog.csdnimg.cn/direct/33474cefbe8346e6937c9f6b4cea3a43.png
思绪
本题可以使用回溯算法来解决。回溯算法通过尝试全部大概的解决方案来找到题目的解的算法，当发现当前的选择无法得到有效的解决方案时，就回溯到上一步，尝试其他的选择。对于 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 = 'Q'
backtracking(dashboard, n, row + 1)
dashboard = '.'
}
}
}
[*]终止条件：当 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 === 'Q') {
return false
}
}
// 判断是否在45度角
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (dashboard === 'Q') {
return false
}
}
// 判断是否是135度角
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (dashboard === '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 = 'Q' backtracking(dashboard, n, row + 1) dashboard = '.' } }}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 === 'Q') {
return false
}
}
// 判断是否在45度角
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (dashboard === 'Q') {
return false
}
}
// 判断是否是135度角
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (dashboard === 'Q') {
return false
}
}
return true
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]