Leetcode37:解数独

Leetcode 37: 解数独 是经典的回溯算法问题，考察如何利用递归和剪枝高效求解数独问题。这题主要考察对回溯、递归、深度优先搜索 (DFS)、剪枝优化等算法思想的掌握。

---

题目描述

给定一个部分填充的数独（9 x 9）网格，用一个有效的算法将其完整解出。

数独规则： 每一行必须包含数字 1-9，不重复。每一列必须包含数字 1-9，不重复。每个 3x3 的子盒子必须包含数字 1-9，不重复。

---

示例输入输出 输入： 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"]]

---

解法 1：回溯法 思路 深度优先搜索： 使用 DFS 遍历整个棋盘，每次找到未填的空格，尝试填入 1-9。若当前数字导致冲突（不合法），回溯到上一步重新尝试。 填充判断： 判断当前数字是否能加入当前行、列、以及 3x3 小方格中，确保满足数独规则。 终止条件： 当所有空格填满时，返回 true。若在当前路径中所有数均无合法选择，则返回 false（触发回溯）。

---

代码模板 class Solution { public void solveSudoku(char[][] board) { backtrack(board); } private boolean backtrack(char[][] board) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') { for (char num = '1'; num <= '9'; num++) { if (isValid(board, i, j, num)) { board[i][j] = num; // 尝试填入数字 if (backtrack(board)) return true; board[i][j] = '.'; // 回溯 } } return false; // 如果 1~9 都不行，返回 false，触发回溯 } } } return true; // 如果没有剩下的空格，说明填满了 } private boolean isValid(char[][] board, int row, int col, char num) { for (int i = 0; i < 9; i++) { // 检查行和列是否出现重复 if (board[row][i] == num || board[i][col] == num) return false; // 检查 3x3 小方格是否出现重复 int boxRow = 3 * (row / 3) + i / 3; int boxCol = 3 * (col / 3) + i % 3; if (board[boxRow][boxCol] == num) return false; } return true; } }

---

复杂度分析 时间复杂度： 最坏情况下为 O(9^(n))，其中 n 是未填格子数。每个空格尝试填入 1-9 的数字。 空间复杂度： O(n)（递归调用栈的深度）。

---

适用场景 经典数独问题的首选解法，清晰易实现。回溯法逻辑直观，可以快速实现并 AC。

---

解法 2：回溯 + 剪枝（预处理加速） 思路

在基础回溯解法的基础上，添加剪枝优化，通过记录数字的使用情况，避免重复判断，加快搜索速度。

状态记录： 使用三个布尔数组分别记录某个数字是否已在当前 行、列 或 3x3 子盒子 中出现。例如，rows[i][num] 表示数字 num+1 是否出现在第 i 行。 选择联合撤销： 每次填一个数字时，更新状态记录；回溯时撤销状态，确保合法性。

---

代码模板 class Solution { private boolean[][] rows = new boolean[9][9]; private boolean[][] cols = new boolean[9][9]; private boolean[][] boxes = new boolean[9][9]; public void solveSudoku(char[][] board) { // 初始化状态 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] != '.') { int num = board[i][j] - '1'; rows[i][num] = true; cols[j][num] = true; boxes[boxIndex(i, j)][num] = true; } } } backtrack(board, 0, 0); } private boolean backtrack(char[][] board, int row, int col) { // 如果列越界，换到下一行 if (col == 9) { col = 0; row++; if (row == 9) return true; // 全部填完 } // 如果当前位置已填，跳过 if (board[row][col] != '.') { return backtrack(board, row, col + 1); } // 尝试填入数字 for (int num = 0; num < 9; num++) { if (!rows[row][num] && !cols[col][num] && !boxes[boxIndex(row, col)][num]) { board[row][col] = (char) ('1' + num); rows[row][num] = true; cols[col][num] = true; boxes[boxIndex(row, col)][num] = true; if (backtrack(board, row, col + 1)) return true; // 回溯撤销选择 board[row][col] = '.'; rows[row][num] = false; cols[col][num] = false; boxes[boxIndex(row, col)][num] = false; } } return false; } private int boxIndex(int row, int col) { return (row / 3) * 3 + col / 3; } }

---

复杂度分析 时间复杂度： 种类减少后，搜索复杂度为 O(9^n)，但剪枝优化显著降低实际运行时间。 空间复杂度： O(1)（记录数字使用情况固定为 9x9 布尔数组）。

---

适用场景 适用于案例比较复杂时（如接近空棋盘），高效减小搜索空间。真正需要性能优化的场景下，剪枝效果显著。

---

解法 3：位运算优化（进一步压缩空间） 思路

剪枝进一步优化，用整数的位运算代替布尔数组进行数字记录。

---

代码模板略

---

快速 AC 策略 回溯法（解法 1） 是首选： 逻辑清晰，易于实现。面试中推荐以此为基础解答，并补充优化思路。 回溯 + 剪枝（解法 2） 在性能要求高时选择： 提前记录状态，避免重复判断。 理解位运算优化的原理，在深度优化场景中进一步探索改进。

总结：经典回溯 + 剪枝思想可以轻松快速地应对数独问题，并在面试中充分展示对搜索问题的理解！