JAVA 递归 + 回溯 实现数独

递归:

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

回溯:

回溯法主要采用试错的思想，它在试错的过程中，如果不能得到一个正确的答案，它可能回退至上一步，甚至重头开始计算。

建议参考:八皇后问题

上代码:

1.给定一个存在唯一解的有效数独

    public static int[][] boards = {{5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9}};

2.实现递归

public static void main(String[] args) {
    //解法:递归回溯
    //数独原型
    System.out.println("求:");
    for (int[] board : boards) {
        System.out.println(Arrays.toString(board));
    }
    //实现递归
    //从第一行第一列执行
    calculation(0, 0);
    System.out.println("解:");
    for (int[] board : boards) {
        System.out.println(Arrays.toString(board));
    }
}

    
    public static boolean calculation(int x, int y) {
        //所有行执行完毕退出
        if (x  == totalRow) {
            return true;
        }

        //校验x-y轴对应数据是否为待填写
        if (0 == boards[x][y]) {
            for (int i = 1; i <= totalNum; i++) {
                //校验当前值是否可填入当前x-y轴
                if (check(x, y, i)) {
                    //设置x-y轴对应值
                    boards[x][y] = i;
                    //执行下一次递归
                    boolean isOk = nextCalculation(x, y);
                    if (isOk) {
                        //True:成功
                        return true;
                    } else {
                        //False:失败
                        //下一单元格执行失败,将历史填写的值置0。
                        boards[x][y] = 0;
                    }
                }
            }
        } else {
            return nextCalculation(x, y);
        }
        return false;
    }

 3.实现下一次递归校验

    
    public static boolean nextCalculation(int x, int y) {
        return y + 1 == totalColumn ? calculation(x + 1, 0) : calculation(x, y + 1);
    }

4.校验数值是否能填入对应单元格 

    
    public static boolean check(int x, int y, int num) {
        //校验X轴
        for (int i = 0; i < totalNum; i++) {
            if (boards[x][i] == num) {
                return false;
            }
        }

        //校验Y轴
        for (int i = 0; i < totalNum; i++) {
            if (boards[i][y] == num) {
                return false;
            }
        }

        //校验当前矩阵
        for (int i = 3 * (x / 3); i < 3 * (x / 3) + 3; i++) {
            for (int j = 3 * (y / 3); j < 3 * (y / 3) + 3; j++) {
                if(boards[i][j] == num){
                    return false;
                }
            }
        }

        return true;
    }

5.结果

 创作不易，不喜勿喷，望指点！