leetcode51-N皇后

leetcode 51

思绪

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

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

复制代码

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

回溯函数

1. const backtracking = (dashboard, n, row) => {
2.   if (row === n) {
3.     result.push(dashboard.map(item => item.join('')))
4.     return;
5.   }
6.   for (let i = 0; i < n; i++) {
7.     if (isValid(dashboard, row, i, n)) {
8.       dashboard[row][i] = 'Q'
9.       backtracking(dashboard, n, row + 1)
10.       dashboard[row][i] = '.'
11.     }
12.   }
13. }

复制代码

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

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

1. const isValid = (dashboard, row, col, n) => {
2.   if (row === 0) { return true }
3.   // 判断是否在同一列
4.   for (let i = 0; i < row; i++) {
5.     if (dashboard[i][col] === 'Q') {
6.       return false
7.     }
8.   }
9.   // 判断是否在45度角
10.   for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
11.     if (dashboard[i][j] === 'Q') {
12.       return false
13.     }
14.   }
15.   // 判断是否是135度角
16.   for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
17.     if (dashboard[i][j] === 'Q') {
18.       return false
19.     }
20.   }
21.   return true
22. }

复制代码

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

完备实现

1. var solveNQueens = function (n) {  let result = [];  // 初始化棋盘  const dashboard = Array(n).fill().map(() => Array(n).fill('.'));
2.   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) => {
3.   if (row === 0) { return true }
4.   // 判断是否在同一列
5.   for (let i = 0; i < row; i++) {
6.     if (dashboard[i][col] === 'Q') {
7.       return false
8.     }
9.   }
10.   // 判断是否在45度角
11.   for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
12.     if (dashboard[i][j] === 'Q') {
13.       return false
14.     }
15.   }
16.   // 判断是否是135度角
17.   for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
18.     if (dashboard[i][j] === 'Q') {
19.       return false
20.     }
21.   }
22.   return true
23. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。