數(shù)獨(dú)問題的一種簡(jiǎn)單解法

黃皓

摘要：在計(jì)算機(jī)解決數(shù)獨(dú)問題的算法中，回溯法是非常有效的。這是一種數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、算法邏輯清晰、程序簡(jiǎn)潔明了、運(yùn)行高速有效的解題方法，并結(jié)合源程序與實(shí)例進(jìn)行說明和論述。

關(guān)鍵詞：數(shù)獨(dú)；算法；回溯；窮舉；lcc-win32

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）22-5340-05

數(shù)獨(dú)是一種邏輯填數(shù)游戲，它起源于瑞士數(shù)學(xué)家歐拉提出的拉丁方陣。20世紀(jì)70年代該游戲在美國(guó)興起，80年代中期開始在日本流行，“數(shù)獨(dú)”（sudoku）一詞就源自于日本，在本世紀(jì)初數(shù)獨(dú)游戲傳入我國(guó)，2005年起風(fēng)靡世界，其熱潮至今仍方興未艾，很多世界著名的報(bào)紙都有數(shù)獨(dú)智力題的連載，每年在世界各地都舉行各種各樣的數(shù)獨(dú)比賽，其中2013年世界數(shù)獨(dú)大賽在中國(guó)舉行。

1 數(shù)獨(dú)游戲規(guī)則

數(shù)獨(dú)是9*9的方陣，其中又可分為9個(gè)3*3的九宮格，如圖1所示。玩家在方陣中填入1-9之間的數(shù)字，保證每一行、每一列、每一個(gè)九宮中的數(shù)字都不相同，所以數(shù)獨(dú)又可以看作是有宮的9階拉丁方陣。通常，方陣事先給定一些數(shù)字，以便于玩家依據(jù)這些初始數(shù)字進(jìn)行填空，而初始數(shù)字的多寡與位置，亦一定程度上決定著題目的難易程度以及解是否能夠唯一。據(jù)推證，最少必須有17個(gè)初始數(shù)字方可保證題目具有唯一的解。有關(guān)數(shù)獨(dú)的詳細(xì)資料請(qǐng)看參考文獻(xiàn)[1]。

2 解法

數(shù)獨(dú)可以鍛煉人的腦力，玩家可以使用摒除法、余數(shù)法等方法來逐步求解。而對(duì)使用電腦來計(jì)算數(shù)獨(dú)題目的研究也有很多，常用算法有遞歸法、候選數(shù)回溯法、枚舉法、遺傳算法、方程求解、使用Dancing Link算法等。由于計(jì)算機(jī)運(yùn)算速度極快，對(duì)于此類有限集合的計(jì)算問題，我們可以簡(jiǎn)單地采用回溯窮舉的方法來解題，幾乎所有的數(shù)獨(dú)題目都可以迅速地得到結(jié)果。該文提出的就是這樣一種簡(jiǎn)潔高效的數(shù)獨(dú)解法，其解決一道數(shù)獨(dú)難題所花時(shí)間通常在ms級(jí)別。與其它回溯算法相比，本算法采用的數(shù)據(jù)結(jié)構(gòu)更為簡(jiǎn)單，邏輯更為清晰。

3 程序結(jié)構(gòu)

程序主體由1個(gè)全局二維數(shù)組和3個(gè)函數(shù)構(gòu)成。

3.1 二維數(shù)組Table

該數(shù)組為9*9的二維數(shù)組，用來存放數(shù)獨(dú)方陣每一個(gè)格子的數(shù)值。初始化時(shí)，它接收來自用戶輸入的提示數(shù)，試探填入數(shù)字時(shí)，它也是提供比較判斷的基礎(chǔ)，最后，如果題目有解，輸出其中的每一行、每一列的數(shù)字。

3.2 函數(shù)InputTable

該函數(shù)沒有輸入、輸出參數(shù)，其功能是輸出提示信息，并接受用戶輸入的數(shù)獨(dú)方陣，每一行的輸入類似于“..1.3..7.”的形式，其中“.”（也可以為0或空格）為待填空格，數(shù)字為提示數(shù)。每一行輸入完畢，就初始化二維數(shù)組Table對(duì)應(yīng)的行中元素，待填空格對(duì)應(yīng)的單元被初始化為0。如輸入其它的內(nèi)容或輸入不符合規(guī)則，則退出程序。

3.3 函數(shù)Ok

該函數(shù)有三個(gè)參數(shù)：參數(shù)m為試探填入的數(shù)字，x和y是待填空格在二維數(shù)組Table中的位置。函數(shù)的功能是檢測(cè)試探數(shù)是否符合數(shù)獨(dú)游戲的規(guī)則。如果在同一行、同一列和九宮中沒有與m相同的數(shù)字，則試探成功函數(shù)并返回1，否則失敗并返回0。關(guān)鍵點(diǎn)在于計(jì)算（x，y）對(duì)應(yīng)的九宮左上角在Table中的位置（x0，y0），然后循環(huán)比較即可。

3.4 函數(shù)main

主函數(shù)的功能主要完成窮舉與回溯等工作。試探時(shí)采用的是暴力窮舉數(shù)字1-9而非候選數(shù)的方式。因?yàn)槿绻捎煤蜻x數(shù)方式，則需要事先對(duì)Sp中每一個(gè)空格掃描出候選數(shù)，用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來儲(chǔ)存，這樣要增加數(shù)據(jù)結(jié)構(gòu)；然后在試探時(shí)依次從該數(shù)據(jù)結(jié)構(gòu)中取出候選數(shù)，這同樣需要時(shí)間開銷，而邏輯結(jié)構(gòu)和程序也會(huì)變得復(fù)雜。

函數(shù)首先對(duì)二維數(shù)組Table進(jìn)行掃描，記錄所有待填空格（即值為0的元素）在數(shù)組中的位置，保存在數(shù)組Sp中，這是一個(gè)2*81的數(shù)組。該數(shù)組是算法的關(guān)鍵，通過此數(shù)組我們就把一個(gè)圖的問題轉(zhuǎn)化為一個(gè)線性表的問題。然后是主循環(huán)，從Sp數(shù)組的起始元素開始進(jìn)行試探與回溯，當(dāng)處理完Sp中所有的空格，那么表示得到了問題的解，如果回溯完Sp的起始元素仍舊不行，則表示問題無解。算法描述如圖2所示。

4 源程序

6 結(jié)束語

數(shù)獨(dú)這種游戲?qū)τ阱憻捜说倪壿嬎伎寄芰κ谴笥旭砸娴模谑褂糜?jì)算機(jī)來解決數(shù)獨(dú)問題的算法中，實(shí)踐證明，該文提出的是一種數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、算法邏輯清晰、程序簡(jiǎn)潔明了、運(yùn)行高速有效的解決方法。

參考文獻(xiàn)：

[1] Frazer Jarvis.Sudoku enumeration problems[EB/OL].http：//www.afjarvis.staff.shef.ac.uk/sudoku/.

[2] 雷蕾，沈富可.關(guān)于數(shù)獨(dú)問題的算法的設(shè)計(jì)與實(shí)現(xiàn)[J]電腦知識(shí)與技術(shù)，2007（2）：481-523.

[3] 李盤榮.數(shù)獨(dú)游戲的算法研究與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2008，26（3）：1715-1717.

[4] 王瓊，鄒晟.數(shù)獨(dú)問題的求解、評(píng)價(jià)與生成算法的研究[J].南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版，2010，10（1）：76-79.

[5] 黎永達(dá)，鄧秀勤.基于改進(jìn)的遺傳算法的數(shù)獨(dú)謎題求解[J]計(jì)算機(jī)應(yīng)用與軟件，2011，28（3）：68-70.

[6] 肖華勇，程海礁，王月興.九宮數(shù)獨(dú)的方程求解算法研究[J]計(jì)算機(jī)應(yīng)用，2012，32（10）：2907-2910.

[7] 姜華林.數(shù)獨(dú)問題高效算法的研究與實(shí)現(xiàn)[J]計(jì)算機(jī)光盤軟件與應(yīng)用，2013（12）：82-83.

[8] Jacob Navia.LCC-Win： A free compiler system for Windows Operating Systems by Jacob Navia[EB/OL]. http：//www.cs.virginia.edu/～lcc-win32/.