該題目為：給定如下所示的數(shù)獨，編寫出算法填充數(shù)獨空白部分，假設該數(shù)獨只有唯一解。

數(shù)獨.png

最近做到該數(shù)獨題，個人認為有必要記錄一下。

要面對的問題

當首次看到這道題時，很多人的第一反應應該就是頭皮發(fā)麻吧。
要往空白處填充數(shù)據(jù)，那這種情況實在是太多了，只要數(shù)獨沒填充完，只要填充的過程中符合數(shù)獨邏輯，均可往里填充。既然如此，我們該如何入手？

數(shù)獨的規(guī)則

• 數(shù)獨的每行數(shù)字必須均唯一
• 數(shù)獨的每列數(shù)字必須均唯一
• 當前坐標所在子宮格的數(shù)必須均唯一

分析問題

既然是在數(shù)獨填充的過程中，當前空白所在的行，列，子宮格的數(shù)都必須唯一，我們要做的就是：

1. 當前空白可填充數(shù)字應該包含哪些？
   可以從0到9的全量集合減去當前行，列，子宮格包含的數(shù)得出。將結果存放在臨時的備選集合當中。

2. 如何填充數(shù)獨？
   循環(huán)遍歷當前備選集合，填充到當前空白當中，然后通過深搜處理下一個空白。

3. 如果在填充過程中，要填充的某個空白無解了，下一步該如何處理？
   這其實就要用到深搜的回溯功能了。如果在深搜填充過程中出現(xiàn)了無解，則回溯，再選擇下一個備選值，直到后邊的空白都為有解即可。
   我的解題如下：

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則標志該數(shù)獨有解
                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]已用備選數(shù)為%d，共有備選數(shù)：%s", i, j, array[i][j], list.toString()));
                        // 深搜當前選用的備選值是否可用
                        if (sudoku(array)) {
                            return true;
                        }
                    }
                    // 當前深搜無解回溯，改回當前值
                    array[i][j] = 0;
                    return false;
                }
            }
        }
        return true;
    }

    // 數(shù)獨遍歷
    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;
    }
}