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

创作时间:

作者:

@小白创作中心

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

引用

来源

https://developer.aliyun.com/article/1657138

数独作为一款经典的逻辑游戏，其目标是在一个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:
...