目录
一、问题描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
二、解题思路
- 逐格填充：使用回溯算法遍历每一个空格，对于每一个空格，依次尝试填入数字 1 到 9，直到找到一个符合数独规则的数字。
- 规则检查：对于每一个填入的数字，检查当前数字是否在该行、该列或者该 3x3 宫格中已经存在。
- 递归回溯：如果某个空格能够被填入一个有效数字，就递归地处理下一个空格。如果某个空格无法填入任何有效数字，就回溯到上一个空格，撤销上一步的选择并尝试其他数字。
三、代码
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
// 遍历整个数独
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
// 如果当前是空格（即 '.'），尝试填数字
if (board[row][col] == '.') {
// 尝试填入数字 '1' 到 '9'
for (char num = '1'; num <= '9'; num++) {
// 检查当前数字是否可以填入
if (isValid(board, row, col, num)) {
board[row][col] = num; // 做出选择
// 继续填下一个格子
if (solve(board)) {
return true; // 如果能成功填完，返回 true
}
// 如果填入 num 之后无法继续解数独，回溯
board[row][col] = '.'; // 撤销选择
}
}
// 如果所有数字都不合适，返回 false，触发回溯
return false;
}
}
}
// 如果所有格子都填完了，返回 true
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) {
return false;
}
}
// 检查当前列是否有重复
for (int i = 0; i < 9; i++) {
if (board[i][col] == num) {
return false;
}
}
// 检查当前 3x3 宫格是否有重复
int boxRowStart = (row / 3) * 3;
int boxColStart = (col / 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[boxRowStart + i][boxColStart + j] == num) {
return false;
}
}
}
return true; // 如果没有冲突，返回 true
}
}
四、复杂度分析
- 时间复杂度：最坏情况下的时间复杂度接近 O(981)O(9^{81})O(981)（每个格子都要尝试 9 种数字）。但是由于回溯的剪枝特性，实际运行时间远远小于这个上限。
- 空间复杂度：由于递归调用的深度最大为 81，空间复杂度为 O(81)=O(1)O(81) = O(1)O(81)=O(1)