算法之数独填充

该题目为：给定如下所示的数独，编写出算法填充数独空白部分，假设该数独只有唯一解。

数独.png

最近做到该数独题，个人认为有必要记录一下。

要面对的问题

当首次看到这道题时，很多人的第一反应应该就是头皮发麻吧。
要往空白处填充数据，那这种情况实在是太多了，只要数独没填充完，只要填充的过程中符合数独逻辑，均可往里填充。既然如此，我们该如何入手？

数独的规则

• 数独的每行数字必须均唯一
• 数独的每列数字必须均唯一
• 当前坐标所在子宫格的数必须均唯一

分析问题

既然是在数独填充的过程中，当前空白所在的行，列，子宫格的数都必须唯一，我们要做的就是：

1. 当前空白可填充数字应该包含哪些？
   可以从0到9的全量集合减去当前行，列，子宫格包含的数得出。将结果存放在临时的备选集合当中。

2. 如何填充数独？
   循环遍历当前备选集合，填充到当前空白当中，然后通过深搜处理下一个空白。

3. 如果在填充过程中，要填充的某个空白无解了，下一步该如何处理？
   这其实就要用到深搜的回溯功能了。如果在深搜填充过程中出现了无解，则回溯，再选择下一个备选值，直到后边的空白都为有解即可。
   我的解题如下：

public class JavaTest {
    public static void main(String[] args) {
        Integer[][] array = {
                {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}
        };
        sudoku(array);

        System.out.println("\n最终结果：");
        forEachsudoku(array);
    }

    private static boolean sudoku(Integer[][] array) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // array[i][j]均>0则标志该数独有解
                if (array[i][j] == 0) {
                    ArrayList<Integer> list = getFullList();
                    // 排除行上已存在的值
                    for (int k = 0; k < 9; k++) {
                        if (array[i][k] != 0) {
                            list.remove(array[i][k]);
                        }
                    }

                    // 排除当前列上已存在的值
                    for (int k = 0; k < 9; k++) {
                        if (array[k][j] != 0) {
                            list.remove(array[k][j]);
                        }
                    }

                    // 排除当前子九宫格上已存在的值
                    int row = i / 3;
                    int column = j / 3;
                    for (int k1 = 3 * row; k1 < 3 * row + 3; k1++) {
                        for (int k2 = 3 * column; k2 < 3 * column + 3; k2++) {
                            if (array[k1][k2] != 0) {
                                list.remove(array[k1][k2]);
                            }
                        }
                    }

                    // 排除完毕后，无可用备选值了，则表明无解
                    if (list.isEmpty()) {
                        System.out.println(String.format("[%d,%d]无可备选值，无解情况为：", i, j));
                        forEachsudoku(array);
                        return false;
                    }

                    for (int k = 0; k < list.size(); k++) {
                        array[i][j] = list.get(k);
                        System.out.println(String.format("[%d,%d]已用备选数为%d，共有备选数：%s", i, j, array[i][j], list.toString()));
                        // 深搜当前选用的备选值是否可用
                        if (sudoku(array)) {
                            return true;
                        }
                    }
                    // 当前深搜无解回溯，改回当前值
                    array[i][j] = 0;
                    return false;
                }
            }
        }
        return true;
    }

    // 数独遍历
    private static void forEachsudoku(Integer[][] arr) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    // 返回默认0到9全量值的集合
    private static ArrayList<Integer> getFullList() {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            list.add(i);
        }
        return list;
    }
}