【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 皇后问题不同的是，本题需要填充一个二维数组。