回溯算法之数独解法详细解读(附带Java代码解读)
回溯算法解数独的步骤
-
逐步填充空白格子:从网格的第一个空白位置开始,尝试填入数字 1 到 9。每次填入数字时,需要检查该数字是否满足数独的约束条件,即是否在当前行、列和 3×3 的宫格中已经存在。
-
递归处理下一个空白格子:如果当前数字合法,递归处理下一个空白位置。否则,尝试下一个可能的数字。如果所有数字都不合法,则回溯到前一个格子,重新尝试其他的数字。
-
找到解后停止:如果网格中的所有空白位置都被合法地填充,则找到了一个完整的解。算法停止,并输出结果。
-
回溯:如果当前格子填入的数字导致后续填入无法合法完成,则返回到上一个填入的格子,尝试其他可能的数字。这个过程会一直递归,直到找到解或发现没有解。
回溯算法的具体步骤
- 空格搜索:找到一个空格位置。
- 尝试填数:对于每个空格位置,依次尝试填入 1 到 9 中的一个数字。
- 合法性检查:每次填入数字后,检查这个数字是否在当前行、当前列和当前 3×3 小宫格中已经存在。如果已经存在,说明该数字不合法,尝试下一个数字。
- 递归下一个位置:如果当前数字合法,递归处理下一个空格。
- 回溯:如果所有数字都无法填入当前空格,回溯到上一个空格,重新尝试其他数字。
数独回溯算法的 Java 实现
public class SudokuSolver {
// 主方法,解决数独问题
public void solveSudoku(char[][] board) {
backtrack(board); // 开始回溯求解
}
// 回溯算法:递归求解数独
private boolean backtrack(char[][] board) {
// 遍历每个空格,依次填入数字
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
// 跳过已填入数字的格子
if (board[row][col] != '.') {
continue;
}
// 尝试填入 1 到 9
for (char num = '1'; num <= '9'; num++) {
// 检查 num 是否可以放入 board[row][col]
if (!isValid(board, row, col, num)) {
continue; // 不合法,尝试下一个数字
}
// 如果合法,先放置数字
board[row][col] = num;
// 递归处理下一个空格
if (backtrack(board)) {
return true; // 找到解
}
// 回溯:如果当前数字导致后续不合法,则撤回
board[row][col] = '.';
}
// 如果 1 到 9 都无法放入当前空格,则返回 false,进行回溯
return false;
}
}
return true; // 所有空格都已合法填入
}
// 检查数字 num 放在 board[row][col] 是否合法
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 startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[startRow + i][startCol + j] == num) {
return false;
}
}
}
return true; // 如果通过所有检查,则数字合法
}
// 主程序入口,测试数独求解
public static void main(String[] args) {
SudokuSolver solver = new SudokuSolver();
char[][] 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'}
};
solver.solveSudoku(board); // 解决数独问题
// 输出解
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
代码详细解读
-
主方法
solveSudoku
- 调用
backtrack
方法开始回溯求解数独。
- 调用
-
回溯方法
backtrack
- 遍历整个 9×9 棋盘,寻找空白格子(表示为
'.'
)。 - 对每个空白格子,依次尝试数字 1 到 9。
- 如果某个数字可以合法地放入当前格子,则递归求解下一个空白格子。
- 如果找到一个有效解,则直接返回
true
,表示成功求解数独。 - 如果数字 1 到 9 都无法放入当前空格,则回溯,返回
false
。
- 遍历整个 9×9 棋盘,寻找空白格子(表示为
-
合法性检查方法
isValid
- 检查当前数字是否已经存在于当前行。
- 检查当前数字是否已经存在于当前列。
- 检查当前数字是否已经存在于当前 3×3 小宫格。
- 如果通过所有检查,则该数字可以合法地放入当前格子。
-
回溯与递归
- 回溯算法在当前数字无法填入时,撤回之前的操作(将格子重新设为
'.'
),并尝试其他数字。 - 当整个棋盘填满后,递归结束,程序输出解。
- 回溯算法在当前数字无法填入时,撤回之前的操作(将格子重新设为
示例数独解法的输出
使用上面的数独棋盘,经过算法求解,输出的结果将是:
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 到 9 的所有数字,因此时间复杂度接近 O(9^m),其中 m 是空格的数量。在实际情况中,由于合法性检查的优化,回溯算法的性能会有所提升。
优化建议
虽然回溯算法解决数独问题相对直观,但在实际应用中,可以结合以下优化策略:
- 单元优化:在每次尝试填入一个数字时,提前记录每一行、每一列、每一个 3×3 小宫格中已出现的数字,减少每次合法性检查的重复计算。
- 启发式搜索:选择空白格子时,优先处理候选数字较少的格子,以减少无效尝试的次数。
总结
回溯算法通过尝试每个可能的数字并递归解决数独问题,虽然在最坏情况下可能会进行大量的尝试,但其思路清晰且易于实现,是解决数独问题的经典方法之一。
原文地址:https://blog.csdn.net/m0_61840987/article/details/142757996
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!