Java利用深度搜索解決數獨遊戲詳解

Posted on by

一、問題描述

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

二、輸入和輸出

1.輸入

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

2.輸出

對於每個測試用例，程序都應該與輸入數據相同的格式打印解決方案。空單元格必須按照規則填充。如果解決方案不是唯一，那麼程序可以打印其中任何一個。

三、輸入和輸出樣例

1.輸入樣例

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

2.輸出樣例

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

四、分析

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

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

用 3 個數組標記每行、每列、每個子網格已用的數字。

row[i][x]：用於標記第 i 行中的數字 x 是否出現。

row[j][y]：用於標記第 j 列中的數字 y 是否出現。

grid[k][z]：標記第 k 個 3*3 子網格中的數字 z 是否出現。

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

五、算法設計

1.預處理輸入數據。

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

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

4.如果 map[i][j] 未填數字，則計算當前位置（i,j）所屬的子網格 k=3((i-1)/3)+(j-1)/3+1。枚舉數字 1~9 填空，如果當前行、當前列、當前子網均未填寫數字，則填寫該數字並標記該數字已出現。如果判斷列 j =9，則說明處理到當前行的最後一列，繼續下一行第 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 行中數字 x 是否已出現
    boolean row[][] = new boolean[10][10];
    // col[j][y] 標記在第 j 列中數字 y 是否已出現
    boolean col[][] = new boolean[10][10];
    // grid[k][z] 標記在第 k 個 3*3 子格中數字z是否已出現
    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++) {//枚舉數字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) { //回溯，繼續枚舉
                        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;
    }
}

七、測試

到此這篇關於Java利用深度搜索解決數獨遊戲詳解的文章就介紹到這瞭,更多相關Java數獨遊戲內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：