另外一道经典的递归与回溯问题。

数独

背景：

标准数独使用9×9的方格，被划分为9个3×3的宫（称为“粗线宫”）。
‌数字填充‌: 需根据已知数字，推理出剩余空格数字，范围限定1-9，且满足：
‌行唯一‌: 每行包含1-9不重复
‌列唯一‌: 每列包含1-9不重复
‌宫唯一‌: 每个3×3宫内包含1-9不重复
‌解的唯一性‌: 合格题目仅有一个解。

一个经典的递归问题，

解题思路：

规则：每行1-9，每列1-9，每个正方格1-9不重复。

第一步：

数据规则，创建一个9×9的数组，将已知的数字标注，未知的数字用0代替

确认退出条件：

当整个数组不存在0时，即判定为退出条件

递归条件：判断一个格子 复核放置标准，放置该数字，同时递归调用，寻找下一个为0的格子

参考代码如下：

public class Sudoku {

    public static void main(String[] args) {


        int[][] board = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 3, 0, 8, 5},
                {0, 0, 1, 0, 2, 0, 0, 0, 0},

                {0, 0, 0, 5, 0, 7, 0, 0, 0},
                {0, 0, 4, 0, 0, 0, 1, 0, 0},
                {0, 9, 0, 0, 0, 0, 0, 0, 0},

                {5, 0, 0, 0, 0, 0, 0, 7, 3},
                {0, 0, 2, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 4, 0, 0, 0, 9}
        };


        new Sudoku().solution(board);
    }

    //递归调用方法
    public void solution(int[][] board) {
        if (exit(board)) {//达成退出条件:打印结果，返回
            print(board);
            return;
        }
        //递归条件：遍历格子中所有为0的格子
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 0) {//值为0，需要填补的值
                    //从1-9中挑选一个数字进行测试
                    for (int k = 1; k <= 9; k++) {
                        //测试这个数字是否能放置到该位置
                        if (isValid(board, i, j, k)) {//有效！
                            //放置这个数字！
                            board[i][j] = k; 
                            //递归调用，寻找下一个需要填入的位置：值为0的格子
                            solution(board);
                            //回溯时，将这个格子重新调整为0
                            board[i][j] = 0;//恢复参数
                        }
                    }
                    //1-9都不能解决问题,不能继续填写了，直接返回，向前回溯
                    return;
                }

            }
        }

    }

    /**
     * 解决方案
     *
     * @param board 面板
     */
    public boolean isValid(int[][] board, int row, int col, int num) {
        //每一行的元素不能重复
        for (int i = 0; i < board.length; i++) {
            if (board[row][i] == num) return false;
        }
        //每一列的元素不能重复
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == num) return false;
        }
        //每个正方形不能重复
        return isBoxValid(board, row, col, num);
    }
    //判断正方形格子里数值没有重复
    public boolean isBoxValid(int[][] board, int row, int col, int num) {
        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;
    }


    /**
     * 退出条件，当面板中没有0的时候退出
     *
     * @param board 面板
     * @return 是否退出
     */
    public boolean exit(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
    //打印结果
    public void print(int[][] board) {

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                System.out.print(" " + board[i][j] + " ");
            }
            System.out.println("");
        }

        System.out.println("==============================");
    }


}