黃皓

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

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

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2014）22-5340-05

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

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

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

2 解法

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

3 程序結構

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

3.1 二維數(shù)組Table

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

3.2 函數(shù)InputTable

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

3.3 函數(shù)Ok

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

3.4 函數(shù)main

主函數(shù)的功能主要完成窮舉與回溯等工作。試探時采用的是暴力窮舉數(shù)字1-9而非候選數(shù)的方式。因為如果采用候選數(shù)方式，則需要事先對Sp中每一個空格掃描出候選數(shù)，用相應的數(shù)據(jù)結構來儲存，這樣要增加數(shù)據(jù)結構；然后在試探時依次從該數(shù)據(jù)結構中取出候選數(shù)，這同樣需要時間開銷，而邏輯結構和程序也會變得復雜。

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

4 源程序

6 結束語

數(shù)獨這種游戲?qū)τ阱憻捜说倪壿嬎伎寄芰κ谴笥旭砸娴?，在使用計算機來解決數(shù)獨問題的算法中，實踐證明，該文提出的是一種數(shù)據(jù)結構簡單、算法邏輯清晰、程序簡潔明了、運行高速有效的解決方法。

參考文獻：

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

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

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

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

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

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

[7] 姜華林.數(shù)獨問題高效算法的研究與實現(xiàn)[J]計算機光盤軟件與應用，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/.