LeetCode 37. 解数独
字数 2332 2025-10-26 10:28:42

LeetCode 37. 解数独

题目描述

请你编写一个程序，通过填充空格来解决数独问题。数独的解法需要遵循以下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫（也称为“块”或“盒子”）内只能出现一次。
    题目会提供一个部分填充的 9x9 数独板，用二维字符数组 board 表示。其中，字符 '.' 表示空格（需要填充），字符 '1' 到 '9' 表示已有数字。
    题目数据保证输入数独仅有一个解。你需要修改原二维数组 board 来得到这个解，不需要返回任何值。

解题过程

解数独是一个经典的、需要回溯算法（Backtracking）来解决的问题。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是解（或者至少不是最后一个解），回溯算法会丢弃该解，并在上一步进行一些修改后再次尝试。

我们可以将解数独的过程理解为，在一个 9x9 的棋盘上，依次为每个空格尝试填入一个有效的数字，并递归地去填下一个空格。如果某个空格填任何数字都会导致冲突，就说明之前的某个选择是错误的，我们需要“回溯”到上一个空格，尝试另一个数字。

步骤一：理解问题与约束

首先，我们需要一个方法来快速判断在某个位置 (row, col) 填入某个数字 num 是否有效。有效性检查需要满足三个条件：

  1. 行检查：第 row 行不能已经有 num。
  2. 列检查：第 col 列不能已经有 num。
  3. 3x3 宫检查：(row, col) 所在的 3x3 宫内不能已经有 num。

步骤二：设计回溯函数

我们将设计一个递归函数，通常命名为 backtrack 或 solve。这个函数的职责是尝试解决从当前位置开始的数独。

  1. 寻找下一个空格：函数首先需要找到数独板上的下一个空格（'.'）。我们可以按行优先的顺序（从左到右，从上到下）来遍历。
  2. 基准情况：如果整个棋盘上都没有空格了，这意味着我们已经成功填满了所有空格，找到了一个解。此时递归可以结束。
  3. 尝试填入数字：如果找到了一个空格 (i, j)，我们就尝试将数字 '1' 到 '9' 填入这个位置。
  4. 有效性检查：在填入一个数字 c 之前，必须用步骤一的方法检查在 (i, j) 填入 c 是否有效。
  5. 递归探索：如果有效，我们就将 c 填入 board[i][j]。然后，递归地调用 backtrack 函数，去尝试解决下一个空格。这个递归调用是解决问题的关键，它基于当前的选择去探索后续的可能性。
  6. 回溯：如果递归调用返回了，这有两种可能：
    • 成功：递归调用一直进行下去，最终填满了所有空格，解决了问题。这时我们可以直接返回成功，不再进行其他尝试。
    • 失败：递归调用进行到某一步时，发现基于当前在 (i, j) 填入 c 的选择，会导致后面的某个空格无法填入任何有效数字。这时，递归调用会返回到当前层。我们必须撤销当前的选择，也就是将 board[i][j] 恢复为 '.'，然后尝试下一个可能的数字 c+1。

步骤三：实现细节

  • 有效性检查的优化：我们可以使用三个二维数组（或类似结构）来记录数字的出现情况，避免每次检查都遍历整行、整列和整个宫格，但这道题规模较小（9x9），直接遍历检查也是可行的。
  • 确定3x3宫的索引：对于一个位置 (row, col)，它属于哪个 3x3 宫？我们可以用公式 box_index = (row // 3) * 3 + (col // 3) 来计算。// 是整数除法。这样，9个宫的索引就是从0到8。

步骤四：完整思路与示例

让我们用一个极简的示例来走一遍流程。假设有一个 2x2 的数独（规则类似，但宫格是 1x1），初始板子如下：

[['1', '.'],
 ['.', '.']]
  1. 我们从 (0,0) 开始，它有数字 1，跳过。
  2. 找到第一个空格 (0,1)。我们尝试填入 1，但检查发现与第一行的 (0,0) 冲突。尝试 2，有效。填入 2，板子变为 [['1','2'], ['.','.']]。
  3. 递归进入下一个空格 (1,0)。尝试 1，检查：与第一列的 (0,0) 冲突。尝试 2，检查：与第二行的 (0,1) 冲突？不，(0,1) 是 2，但不在同一行/列/宫？对于 2x2，宫是 1x1，所以 (1,0) 的宫里只有它自己。尝试 3？规则是数字 1-2，所以只能试 1 和 2。都冲突了！说明在 (1,0) 无解。
  4. 递归调用失败，回溯到上一步 (0,1)。我们将 (0,1) 恢复为 '.'。板子变回 [['1','.'], ['.','.']]。
  5. 我们在 (0,1) 尝试下一个数字。但 1 和 2 都试过了，没有其他数字了。说明基于 (0,0)=1 这个初始状态，在 (0,1) 无法找到解？这不可能，因为题目保证有解。这说明我们的初始板子可能不对，或者 2x2 数独本身无解。这个例子只是用来说明“回溯”的动作。

总结

解数独的回溯算法核心是：做出选择 -> 递归探索 -> 如果失败则撤销选择（回溯）。这是一个非常典型的“深度优先搜索”（DFS）过程，只不过在每一步，我们只尝试那些当前有效的选择，从而进行“剪枝”，提高效率。由于题目保证有唯一解，所以一旦找到一个解，整个递归就可以立即终止。

LeetCode 37. 解数独 题目描述 请你编写一个程序，通过填充空格来解决数独问题。数独的解法需要遵循以下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫（也称为“块”或“盒子”）内只能出现一次。 题目会提供一个部分填充的 9x9 数独板，用二维字符数组 board 表示。其中，字符 '.' 表示空格（需要填充），字符 '1' 到 '9' 表示已有数字。 题目数据保证输入数独仅有一个解。你需要修改原二维数组 board 来得到这个解，不需要返回任何值。 解题过程 解数独是一个经典的、需要 回溯算法 （Backtracking）来解决的问题。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是解（或者至少不是最后一个解），回溯算法会丢弃该解，并在上一步进行一些修改后再次尝试。 我们可以将解数独的过程理解为，在一个 9x9 的棋盘上，依次为每个空格尝试填入一个有效的数字，并递归地去填下一个空格。如果某个空格填任何数字都会导致冲突，就说明之前的某个选择是错误的，我们需要“回溯”到上一个空格，尝试另一个数字。 步骤一：理解问题与约束 首先，我们需要一个方法来快速判断在某个位置 (row, col) 填入某个数字 num 是否有效。有效性检查需要满足三个条件： 行检查 ：第 row 行不能已经有 num 。 列检查 ：第 col 列不能已经有 num 。 3x3 宫检查 ： (row, col) 所在的 3x3 宫内不能已经有 num 。 步骤二：设计回溯函数 我们将设计一个递归函数，通常命名为 backtrack 或 solve 。这个函数的职责是尝试解决从当前位置开始的数独。 寻找下一个空格 ：函数首先需要找到数独板上的下一个空格（ '.' ）。我们可以按行优先的顺序（从左到右，从上到下）来遍历。 基准情况 ：如果整个棋盘上都没有空格了，这意味着我们已经成功填满了所有空格，找到了一个解。此时递归可以结束。 尝试填入数字 ：如果找到了一个空格 (i, j) ，我们就尝试将数字 '1' 到 '9' 填入这个位置。 有效性检查 ：在填入一个数字 c 之前，必须用步骤一的方法检查在 (i, j) 填入 c 是否有效。 递归探索 ：如果有效，我们就将 c 填入 board[i][j] 。然后， 递归地调用 backtrack 函数，去尝试解决下一个空格。这个递归调用是解决问题的关键，它基于当前的选择去探索后续的可能性。 回溯 ：如果递归调用返回了，这有两种可能： 成功 ：递归调用一直进行下去，最终填满了所有空格，解决了问题。这时我们可以直接返回成功，不再进行其他尝试。 失败 ：递归调用进行到某一步时，发现基于当前在 (i, j) 填入 c 的选择，会导致后面的某个空格无法填入任何有效数字。这时，递归调用会返回到当前层。 我们必须撤销当前的选择 ，也就是将 board[i][j] 恢复为 '.' ，然后尝试下一个可能的数字 c+1 。 步骤三：实现细节 有效性检查的优化 ：我们可以使用三个二维数组（或类似结构）来记录数字的出现情况，避免每次检查都遍历整行、整列和整个宫格，但这道题规模较小（9x9），直接遍历检查也是可行的。 确定3x3宫的索引 ：对于一个位置 (row, col) ，它属于哪个 3x3 宫？我们可以用公式 box_index = (row // 3) * 3 + (col // 3) 来计算。 // 是整数除法。这样，9个宫的索引就是从0到8。 步骤四：完整思路与示例 让我们用一个极简的示例来走一遍流程。假设有一个 2x2 的数独（规则类似，但宫格是 1x1 ），初始板子如下： 我们从 (0,0) 开始，它有数字 1 ，跳过。 找到第一个空格 (0,1) 。我们尝试填入 1 ，但检查发现与第一行的 (0,0) 冲突。尝试 2 ，有效。填入 2 ，板子变为 [['1','2'], ['.','.']] 。 递归进入下一个空格 (1,0) 。尝试 1 ，检查：与第一列的 (0,0) 冲突。尝试 2 ，检查：与第二行的 (0,1) 冲突？不， (0,1) 是 2 ，但不在同一行/列/宫？对于 2x2 ，宫是 1x1 ，所以 (1,0) 的宫里只有它自己。尝试 3 ？规则是数字 1-2 ，所以只能试 1 和 2 。都冲突了！说明在 (1,0) 无解。 递归调用失败， 回溯 到上一步 (0,1) 。我们将 (0,1) 恢复为 '.' 。板子变回 [['1','.'], ['.','.']] 。 我们在 (0,1) 尝试下一个数字。但 1 和 2 都试过了，没有其他数字了。说明基于 (0,0)=1 这个初始状态，在 (0,1) 无法找到解？这不可能，因为题目保证有解。这说明我们的初始板子可能不对，或者 2x2 数独本身无解。这个例子只是用来说明“回溯”的动作。 总结 解数独的回溯算法核心是： 做出选择 -> 递归探索 -> 如果失败则撤销选择（回溯） 。这是一个非常典型的“深度优先搜索”（DFS）过程，只不过在每一步，我们只尝试那些当前有效的选择，从而进行“剪枝”，提高效率。由于题目保证有唯一解，所以一旦找到一个解，整个递归就可以立即终止。