Java利用深度搜索解決數(shù)獨游戲詳解

更新時間：2022年08月16日 10:59:25 作者：chengqiuming

數(shù)獨是一項非常簡單的任務。玩家需要根據(jù)9×9盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個粗線宮（3*3）內(nèi)的數(shù)字均含1-9，不重復。本文將利用Java編寫一個程序來解決給定的數(shù)獨任務，感興趣的可以動手嘗試一下

一、問題描述

數(shù)獨是一項非常簡單的任務。如下圖所示，一張 9 行 9 列的表被分成 9 個 3*3 的小方格。在一些單元格中寫上十進制數(shù)字 1~9，其他單元格為空。目標是用 1 ~9 的數(shù)字填充空單元格，每個單元格一個數(shù)字，這樣在每行、每列和每個被標記為 3*3 的子正方形內(nèi)，所有 1~9 的數(shù)字都會出現(xiàn)。編寫一個程序來解決給定的數(shù)獨任務。

二、輸入和輸出

1.輸入

對于每個測試用例，后面都跟 9 行，對于表的行。在每行上都給出 9 個十進制數(shù)字，對于這一行中的單元格。如果單元格為空，則用 0 表示。

2.輸出

對于每個測試用例，程序都應該與輸入數(shù)據(jù)相同的格式打印解決方案?？諉卧癖仨毎凑找?guī)則填充。如果解決方案不是唯一，那么程序可以打印其中任何一個。

三、輸入和輸出樣例

1.輸入樣例

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

2.輸出樣例

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

四、分析

該問題為數(shù)獨游戲，為典型的九空格問題，可以采用回溯法搜索。把一個 9 行 9 列的網(wǎng)格再細分為 9 個 3*3 的子網(wǎng)格，要求在每行、每列、每個子網(wǎng)格內(nèi)都使用一次 1~9 的一個數(shù)字，即在每行、每列、每個子網(wǎng)格內(nèi)都不允許出現(xiàn)相同的數(shù)字。

0 表示空白位置，其他均為已填入的數(shù)字。要求填完九空格并輸出（如果有多種結(jié)果，則只需出其中一種）。如果給定的九宮格無法按照要求填出來，則輸出原來所輸入的未填的九宮格。

用 3 個數(shù)組標記每行、每列、每個子網(wǎng)格已用的數(shù)字。

row[i][x]：用于標記第 i 行中的數(shù)字 x 是否出現(xiàn)。

row[j][y]：用于標記第 j 列中的數(shù)字 y 是否出現(xiàn)。

grid[k][z]：標記第 k 個 3*3 子網(wǎng)格中的數(shù)字 z 是否出現(xiàn)。

row 和 col 的標記比較好處理。行 i、列 j 對應的子網(wǎng)格編號 k=3((i-1)/3)+(j-1)/3+1,如下圖所示。

五、算法設計

1.預處理輸入數(shù)據(jù)。

2.從左上角（1,1）開始按行搜索，如果行 i=10，則說明找到答案，返回 1。

3.如果 map[i][j] 已填數(shù)字，則判斷如果列 j=9,則說明處理到當前行的最后一列，繼續(xù)下一行第 1 列的搜索，即 dfs(i+1,1)，否則在當前行的下一列搜索 dfs(i,j+1)。如果搜索成功，則返回1，否則返回 0。

4.如果 map[i][j] 未填數(shù)字，則計算當前位置（i,j）所屬的子網(wǎng)格 k=3((i-1)/3)+(j-1)/3+1。枚舉數(shù)字 1~9 填空，如果當前行、當前列、當前子網(wǎng)均未填寫數(shù)字，則填寫該數(shù)字并標記該數(shù)字已出現(xiàn)。如果判斷列 j =9，則說明處理到當前行的最后一列，繼續(xù)下一行第 1 列的搜索，即 dfs(i+1,1)，否則在當前行的下一列搜索，即 dfs(i,j+1)。如果搜索失敗，否則返回 1。

六、代碼

package com.platform.modules.alg.alglib.poj2676;
 
public class Poj2676 {
    public String output = "";
    int map[][] = new int[10][10];
    // row[i][x] 標記在第 i 行中數(shù)字 x 是否已出現(xiàn)
    boolean row[][] = new boolean[10][10];
    // col[j][y] 標記在第 j 列中數(shù)字 y 是否已出現(xiàn)
    boolean col[][] = new boolean[10][10];
    // grid[k][z] 標記在第 k 個 3*3 子格中數(shù)字z是否已出現(xiàn)
    boolean grid[][] = new boolean[10][10];
 
    boolean dfs(int i, int j) {
        if (i == 10)
            return true;
        boolean flag;
        if (map[i][j] > 0) {
            if (j == 9)
                flag = dfs(i + 1, 1);
            else
                flag = dfs(i, j + 1);
            return flag ? true : false;
        } else {
            int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;
            for (int x = 1; x <= 9; x++) {//枚舉數(shù)字1~9填空
                if (!row[i][x] && !col[j][x] && !grid[k][x]) {
                    map[i][j] = x;
                    row[i][x] = true;
                    col[j][x] = true;
                    grid[k][x] = true;
                    if (j == 9)
                        flag = dfs(i + 1, 1);
                    else
                        flag = dfs(i, j + 1);
                    if (!flag) { //回溯，繼續(xù)枚舉
                        map[i][j] = 0;
                        row[i][x] = false;
                        col[j][x] = false;
                        grid[k][x] = false;
                    } else
                        return true;
                }
            }
        }
        return false;
    }
 
    public String cal(String input) {
        String[] line = input.split("\n");
 
 
        char ch;
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                ch = line[i-1].charAt(j-1);
                map[i][j] = ch - '0';
                if (map[i][j] > 0) {
                    int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;
                    row[i][map[i][j]] = true;
                    col[j][map[i][j]] = true;
                    grid[k][map[i][j]] = true;
                }
            }
        }
 
        dfs(1, 1);
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++)
                output += map[i][j];
            output += "\n";
        }
        return output;
    }
}