有没有对数独感兴趣的朋友呢？数独作为一款经典的逻辑游戏，其目标是在一个9x9的方格中填入数字1至9，确保每一行、每一列以及每一个3x3的子网格中都包含这些数字且不重复。尽管数独的规则看似简单，但编写一个能够自动求解数独的程序却是一项颇具挑战性的任务。本文将深入探讨如何运用回溯算法来实现数独的自动求解。
数独求解算法及步骤
我们使用一个二维数组来表示数独的表格，空位置填充0。
数独求解的核心算法是回溯算法。回溯算法是一种通过逐步构建解决方案并在遇到冲突时回退的算法。具体来说，我们尝试在空格中填入一个数字，然后递归地继续填充下一个空格。如果在某个步骤中发现无法继续填充，则回退到上一步并尝试其他数字。
- 算法步骤
寻找空格：我们循环数独的所有单元格，如果数组的值为0的话则此格未填写数字。
尝试填入数字：对于这个空格，尝试填入1到9中的一个数字。
检查数字的正确性：检查填入的数字是否与当前行、列和3x3子网格中的数字有重复。
递归求解：如果没有重复，则递归地继续填充下一个空格。
回溯：如果在某个步骤中发现无法继续填充，则回退到上一步并尝试其他数字。
Java代码实现
我们使用一个二维数组来表示数独，有一种只求解数独的方法及求解不是唯一解的所有可行解的方法。代码如下
/**
* 数独求解
*/
public class SudokuSolver {
/**
* 检查数独元素的正确性，及每行、每列、每九宫格的唯一性
*/
public static boolean checkValue(int[][] sudoku,int value,int row,int col){
//检验当前元素所在行
for (int i = 0; i < 9; i++) {
if(sudoku[row][i] == value){
return false;
}
}
//检验当前元素所在列
for (int i = 0; i < 9; i++) {
if(sudoku[i][col] == value){
return false;
}
}
//检验当前元素所在九宫格
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
// 如果当前元素所在九宫格有值，则返回false
if(sudoku[row/3*3+i][col/3*3+j] == value){
return false;
}
}
}
return true;
};
/**
* 回溯算法求解数独
*/
public static boolean solveSudokuSingleSec(int[][] sudoku) {
//递归回溯法求解数独,循环遍历81个元素，如果当前元素为0，则尝试1-9的值，如果符合要求，则递归求解，否则返回上一层继续尝试
for (int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++){
//如果当前元素为0，则尝试1-9的值，如果符合要求，则递归求解，否则返回上一层继续尝试
if(sudoku[i][j]== 0){
for (int k =1;k<=9;k++){
//如果符合要求，则递归求解，否则返回上一层继续尝试
if(checkValue(sudoku,k,i,j)){
sudoku[i][j] = k;
if(solveSudokuSingleSec(sudoku)){
return true;
}
// 回溯
sudoku[i][j] = 0;
}
}
// 无法继续填充，则回退到上一步并尝试其他数字。
return false;
}
}
}
// 找到一个解，则返回true,无需继续回溯
return true;
}
/**
*回溯算法求解数独的所有可能解
*/
public static void solveSudokuSec(int[][] sudoku, List<int[][]> result) {
// 递归回溯法求解数独,循环遍历81个元素，如果当前元素为0，则尝试1-9的值，如果符合要求，则递归求解，否则返回上一层继续尝试
for (int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++){
if(sudoku[i][j]== 0){
for (int k =1;k<=9;k++){
if(checkValue(sudoku,k,i,j)){
sudoku[i][j] = k;
// 递归求解
solveSudokuSec(sudoku,result);
// 回溯
sudoku[i][j] = 0;
}
}
// 无法继续填充，则回退到上一步并尝试其他数字。
return;
}
}
}
// 找到一个解，记录并添加到集合中
int[][] resultArray = new int[9][9];
for (int row = 0; row < 9; row++) {
System.arraycopy(sudoku[row], 0, resultArray[row], 0, 9);
}
result.add(resultArray);
}
public static void main(String[] args) {
int[][] initArraySingle = new int[][]{
{
8,0,0,0,0,0,0,0,0},
{
0,0,3,6,0,0,0,0,0},
{
0,7,0,0,9,0,2,0,0},
{
0,5,0,0,0,7,0,0,0},
{
0,0,0,0,4,5,7,0,0},
{
0,0,0,1,0,0,0,3,0},
{
0,0,1,0,0,0,0,6,8},
{
0,0,8,5,0,0,0,1,0},
{
0,9,0,0,0,0,4,0,0}
};
int[][] initArray = new int[][]{
{
8,0,0,0,0,0,0,0,0},
{
0,0,3,6,0,0,0,0,0},
{
0,7,0,0,9,0,2,0,0},
{
0,8,0,0,0,7,0,0,0},
{
0,0,0,0,4,5,7,0,0},
{
0,0,0,1,0,0,0,3,0},
{
0,0,1,0,0,0,0,6,8},
{
0,0,8,5,0,0,0,1,0},
{
0,9,0,0,0,0,4,0,0}
};
// 回溯算法求解数独
solveSudokuSingleSec(initArraySingle);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(initArraySingle[i][j]+" ");
}
System.out.println();
}
List<int[][]> result = new ArrayList<>();
// 回溯算法求解数独的所有可能解
solveSudokuSec(initArray,result);
System.out.println("共"+result.size()+"种解法");
for (int i = 0; i < result.size(); i++){
System.out.println("解法"+(i+1)+":");
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
System.out.print(initArraySingle[j][k]+" ");
}
System.out.println();
}
}
;
}
}
求解结果如下：
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
共295种解法
解法1:
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
解法2:
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
解法3:
...
总结
通过使用回溯算法，我们可以有效地求解数独问题。虽然回溯算法在最坏情况下的时间复杂度较高，但对于标准9x9的数独问题，它通常能够在合理的时间内找到解决方案。希望本文对你理解数独求解算法有所帮助，并激发你进一步探索算法的兴趣。
