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

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

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

一、問(wèn)題描述

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

二、輸入和輸出

1.輸入

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

2.輸出

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

三、輸入和輸出樣例

1.輸入樣例

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

2.輸出樣例

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

四、分析

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

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

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

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

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

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

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

五、算法設(shè)計(jì)

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

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

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

4.如果 map[i][j] 未填數(shù)字，則計(jì)算當(dāng)前位置（i,j）所屬的子網(wǎng)格 k=3((i-1)/3)+(j-1)/3+1。枚舉數(shù)字 1~9 填空，如果當(dāng)前行、當(dāng)前列、當(dāng)前子網(wǎng)均未填寫(xiě)數(shù)字，則填寫(xiě)該數(shù)字并標(biāo)記該數(shù)字已出現(xiàn)。如果判斷列 j =9，則說(shuō)明處理到當(dāng)前行的最后一列，繼續(xù)下一行第 1 列的搜索，即 dfs(i+1,1)，否則在當(dāng)前行的下一列搜索，即 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] 標(biāo)記在第 i 行中數(shù)字 x 是否已出現(xiàn)
    boolean row[][] = new boolean[10][10];
    // col[j][y] 標(biāo)記在第 j 列中數(shù)字 y 是否已出現(xiàn)
    boolean col[][] = new boolean[10][10];
    // grid[k][z] 標(biāo)記在第 k 個(gè) 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;
    }
}