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}

那么问题就解决了。

当然算法的复杂度还是很高的。也许可以再针对测试用例进一步优化。