【LeetCode】37. 解数独（困难）——代码随想录算法训练营Day30

题目链接：37. 解数独

题目描述

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

文章讲解：代码随想录

视频讲解：回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独_哔哩哔哩_bilibili

题解1：回溯法

思路：使用回溯法求解棋盘类问题。

回溯分析：

• 递归函数的参数和返回值：返回值是一个布尔值，表示是否填充完毕。参数为 num，表示当前已填充几个数字。
• 递归函数的终止条件：num 等于81，即填充完整个数独。
• 单层递归的逻辑：若当前格还未填充，则从1到9尝试填充，然后递归的填充下一格；已填充则直接递归的填充下一格。
• 剪枝：当与其他格数字冲突时，跳过本次填充。

/*** @param {character[][]} board* @return {void} Do not return anything, modify board in-place instead.*/
var solveSudoku = function(board) {const rowState = new Array(9).fill().map(() => new Array(9).fill(false)); // 行状态const colState = new Array(9).fill().map(() => new Array(9).fill(false)); // 列状态const squierState = new Array(3).fill().map(() => new Array(3).fill().map(() => new Array(9).fill(false))); // 单元状态// 初始化状态表for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] === ".") {continue;}rowState[i][board[i][j]] = true;colState[j][board[i][j]] = true;squierState[parseInt(i / 3)][parseInt(j / 3)][board[i][j]] = true;}}const backtracking = function (num) {if (num === 81) {return true; // 填充完毕，返回 true}const col = num % 9; // 计算列数const row = (num - col) / 9; // 计算行数if (board[row][col] !== ".") {return backtracking(num + 1); // 已经有数字了，向下遍历}// 从1到9尝试填充for (let j = 1; j <= 9; j++) {// 和规则冲突，尝试填充下一个数if (rowState[row][j] || colState[col][j] || squierState[parseInt(row / 3)][parseInt(col / 3)][j]) {continue;}board[row][col] = "" + j; // 填充rowState[row][j] = true; // 更新行状态colState[col][j] = true; // 更新列状态squierState[parseInt(row / 3)][parseInt(col / 3)][j] = true; // 更新单元状态// 向下遍历if (backtracking(num + 1)) {return true; // 已经填充完毕，返还 true}// 回溯board[row][col] = ".";rowState[row][j] = false;colState[col][j] = false;squierState[parseInt(row / 3)][parseInt(col / 3)][j] = false;}return false;}backtracking(0);
};

分析：设 m 为 . 的数量，则时间复杂度为 O(9 ^ m)，空间复杂度为 O(n²)。

收获

练习使用回溯法求解棋盘类问题，和 n 皇后问题不同的是，本题需要填充一个二维数组。