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

黃皓

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

關(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ù)法等方法來(lái)逐步求解。而對(duì)使用電腦來(lái)計(jì)算數(shù)獨(dú)題目的研究也有很多，常用算法有遞歸法、候選數(shù)回溯法、枚舉法、遺傳算法、方程求解、使用Dancing Link算法等。……