Js算法與數據結構拾萃（6.5）：回溯法解決數獨問題
- 2020 年 3 月 6 日
- 筆記
回顧N皇后問題的解決方案，並沒有採用二維數組。但實際上思路依然和所謂「回溯法通用解決模板」是一致的。
- result = []function backtrack(路徑, 選擇列表){ if 滿足結束條件: result.add(路徑) return result for 選擇 in 選擇列表: 做選擇 backtrack(路徑, 選擇列表) 撤銷選擇}
案例: 數獨問題（sudoku-solver）
對應leetcode第37題，難度：困難 https://leetcode.com/problems/sudoku-solver/
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
1.Each of the digits 1-9 must occur exactly once in each row.2.Each of the digits 1-9 must occur exactly once in each column.3.Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
編寫一個程序，通過已填充的空格來解決數獨問題。
一個數獨的解法需遵循如下規則：
•數字 1-9 在每一行只能出現一次。•數字 1-9 在每一列只能出現一次。•數字 1-9 在每一個以粗實線分隔的 3×3 宮內只能出現一次。•空白格用 '.' 表示。
一個數獨。
答案被標成紅色。
提示
•給定的數獨序列只包含數字 1-9 和字符 '.' 。•你可以假設給定的數獨只有唯一解。•給定數獨永遠是 9×9 形式的。
通用解法
數獨問題的解題思路和N皇后是一致的。
1.逐行逐列遍歷2.依次填入1-9：看此數字是否通過校驗。•校驗不通過則回退。•校驗通過，調用自身程序，看能否求出正解•能：輸出結果•不能：繼續填入下個數
- var solveSudoku = function(board) { // 判斷能否求出正解 const sudoku = board => { for (let row = 0; row < 9; row++) { for (let col = 0; col < 9; col++) { let cell = board[row][col] // 判斷是否有數 if (cell != '.') continue // 開始判斷1-9 for (let i = 1; i <= 9; i++) { if (find(board, row, col, i)) { //如果成立 => 落子，繼續調用sudoku往下求解 board[row][col] = i +'' // leetcode限制填入必須為字符串而非數字 // 如果能求出正解。返回true if (sudoku(board)){ return true }else{ // 否則當前步驟回歸上一步，繼續遍歷下個數 board[row][col] = '.' } } } // 遍歷完當前行，即可認為無解。 return false } } return true } sudoku(board) return board}
好了，回溯法總的解決框架來說似乎還是比較簡單的。另外一個難點在於find方法。
此處可在一個循環中進行判斷。
- const find = (board, row, col, index) => { for (let i = 0; i < 9; i++) { // 判斷行 if (board[row][i] == index) { return false } // 判斷列 if (board[i][col] == index) { return false } // 判斷九宮格 let _Row = parseInt(row / 3) * 3 + parseInt(i / 3) let _Col = parseInt(col / 3) * 3 + (i % 3) if (board[_Row][_Col] == index) { return false } } return true}
那麼問題就解決了。
當然算法的複雜度還是很高的。也許可以再針對測試用例進一步優化。
