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
}
