算法系列之回溯算法求解数独及所有可能解

有没有对数独感兴趣的朋友呢？数独作为一款经典的逻辑游戏，其目标是在一个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++) {// 如果当前元素所在九宫格有值，则返回falseif(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:
...