美文网首页
算法之数独填充

算法之数独填充

作者: android_hcf | 来源:发表于2020-06-06 11:56 被阅读0次

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


    数独.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;
        }
    }
    

    相关文章

      网友评论

          本文标题:算法之数独填充

          本文链接:https://www.haomeiwen.com/subject/nfhnzhtx.html