Java利用深度搜索解決數(shù)獨(dú)游戲詳解
一、問題描述
數(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)文章
Java中JFrame實(shí)現(xiàn)無邊框無標(biāo)題方法
這篇文章主要介紹了Java中JFrame實(shí)現(xiàn)無邊框無標(biāo)題方法,本文直接給出代碼實(shí)例,需要的朋友可以參考下2015-05-05java Spring Boot 配置redis pom文件操作
這篇文章主要介紹了java Spring Boot 配置redis pom文件操作,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-07-07Spring?Boot?3.1中整合Spring?Security和Keycloak的方法
本文介紹在最新的SpringBoot3.1版本之下,如何將Keycloak和Spring?Security一起跑起來,文中結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧2023-06-06Springboot內(nèi)置Tomcat配置參數(shù)調(diào)優(yōu)方式
這篇文章主要介紹了Springboot內(nèi)置Tomcat配置參數(shù)調(diào)優(yōu)方式,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-06-06解讀Spring接口方法加@Transactional失效的原因
這篇文章主要介紹了Spring接口方法加@Transactional失效的原因解讀,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-03-03