欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2022年08月16日 10:59:25   作者:chengqiuming  
數(shù)獨(dú)是一項(xiàng)非常簡單的任務(wù)。玩家需要根據(jù)9×9盤面上的已知數(shù)字,推理出所有剩余空格的數(shù)字,并滿足每一行、每一列、每一個(gè)粗線宮(3*3)內(nèi)的數(shù)字均含1-9,不重復(fù)。本文將利用Java編寫一個(gè)程序來解決給定的數(shù)獨(dú)任務(wù),感興趣的可以動(dòng)手嘗試一下

一、問題描述

數(shù)獨(dú)是一項(xiàng)非常簡單的任務(wù)。如下圖所示,一張 9 行 9 列的表被分成 9 個(gè) 3*3 的小方格。在一些單元格中寫上十進(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)。編寫一個(gè)程序來解決給定的數(shù)獨(dú)任務(wù)。

二、輸入和輸出

1.輸入

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

2.輸出

對于每個(gè)測試用例,程序都應(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

四、分析

該問題為數(shù)獨(dú)游戲,為典型的九空格問題,可以采用回溯法搜索。把一個(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é)果,則只需出其中一種)。如果給定的九宮格無法按照要求填出來,則輸出原來所輸入的未填的九宮格。

用 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 對應(yīng)的子網(wǎng)格編號 k=3((i-1)/3)+(j-1)/3+1,如下圖所示。

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

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

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

3.如果 map[i][j] 已填數(shù)字,則判斷如果 列 j=9,則說明處理到當(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)均未填寫數(shù)字,則填寫該數(shù)字并標(biāo)記該數(shù)字已出現(xiàn)。如果判斷列 j =9,則說明處理到當(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;
    }
}

七、測試

到此這篇關(guān)于Java利用深度搜索解決數(shù)獨(dú)游戲詳解的文章就介紹到這了,更多相關(guān)Java數(shù)獨(dú)游戲內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評論