李祥琴

（荊楚理工學(xué)院計算機工程學(xué)院，湖北荊門448000）

數(shù)獨問題求解算法的研究與實現(xiàn)

李祥琴

（荊楚理工學(xué)院計算機工程學(xué)院，湖北荊門448000）

數(shù)獨是當(dāng)前流行的一種填字游戲。本文介紹了幾種常用的數(shù)獨求解方法，并通過具體實例，探討了數(shù)獨問題的求解方案，最后使用C#語言編程實現(xiàn)。結(jié)果證明，該方案運行效率高，結(jié)果易于理解。

數(shù)獨；初盤；候選數(shù)；回溯法

1 引言

數(shù)獨（Sudoku）是一種運用紙、筆進行演算的邏輯智力游戲，起源于瑞士數(shù)學(xué)家歐拉等人研究的拉丁方陣（Latin Square），目前風(fēng)靡全球。隨著數(shù)獨愛好者日益增多，數(shù)獨也出現(xiàn)了許多變形，比如迷你數(shù)獨、對角線數(shù)獨，其規(guī)則種類數(shù)不勝數(shù)。

數(shù)獨由方格、行、列、宮等元素組成，是將一個較大的正方形均分成9行9列，形成81個方格，也稱九宮格，每個方格都是一個小正方形，水平方向的三橫行與垂直方向的三縱列相交之處有9個方格，構(gòu)成一個小九宮，稱為宮。數(shù)獨的游戲規(guī)則是：在方格中填入1到9的數(shù)字，并滿足每一行只能填充1～9的數(shù)字，且不能重復(fù)；每一列只能填充1～9的數(shù)字，且不能重復(fù)；在每3×3的方格中填充1～9的數(shù)字，且不能重復(fù)。

2 數(shù)獨的求解方法

數(shù)獨在游戲開始時的狀態(tài)稱為初盤，包括數(shù)字和空格，游戲結(jié)束時的狀態(tài)稱為終盤，只包含數(shù)字[1]。每個數(shù)獨初盤可得到一個或多個終盤，由于數(shù)獨中的數(shù)字排列有各種組合，因而每個數(shù)獨終盤又可以演變出無數(shù)個數(shù)獨初盤。

數(shù)獨中的數(shù)字千變?nèi)f化，解法也隨之靈活各樣，主要有摒除法、余數(shù)法、隱含唯一數(shù)法、數(shù)對法和回溯法[2-4]。

（1）摒除法

在每行、每列以及小九宮中，每個數(shù)字只能出現(xiàn)一次，若某一行已經(jīng)出現(xiàn)了一個數(shù)字8，該行其它方格候選數(shù)就不能填數(shù)字8。

（2）余數(shù)法

如果按行、列以及小九宮數(shù)字不可重復(fù)的規(guī)則依次給出候選數(shù)，若出現(xiàn)某個方格只含有一個候選數(shù)，那么這個方格必然填這個數(shù)字。比如，某一方格受其它20格的影響，假如這20格里面已經(jīng)出現(xiàn)了1～5、7～9這8個數(shù)字，那么沒有出現(xiàn)的唯一數(shù)字就是6。

（3）隱含唯一數(shù)法

如果按行、列以及小九宮數(shù)字不可重復(fù)的規(guī)則依次給出候選數(shù)，若在某一行、某一列或某個小九宮中有一個候選數(shù)只出現(xiàn)在某一個方格里，而其它方格都沒有這個候選數(shù)，那么這個方格必然填這個數(shù)字。

（4）數(shù)對法

如果出現(xiàn)某一行、某一列或某個小九宮中有兩個方格只使用了兩個候選數(shù)，那么這兩個方格必然會是這兩個數(shù)字。

（5）回溯法

在一些復(fù)雜的問題中，若使用摒除法、余數(shù)法、數(shù)對法后仍然無法繼續(xù)下去，這時可以采用回溯法。比如某個方格只有兩個候選數(shù)1和8，但不知道選擇候選數(shù)1還是8?？上冗x擇其中一個候選數(shù)填入，然后往下判定其它的空格，若出現(xiàn)沖突現(xiàn)象，則代表前面的假設(shè)是錯誤的，可選擇另一個候選數(shù)填入，再往下逐步求解。

3 計算機編程實現(xiàn)

下面以Visual Studio 2010為集成環(huán)境，通過C#語言編程求解數(shù)獨問題。數(shù)獨初盤如表1所示。

表1 數(shù)獨初盤

3.1 數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計

定義一個類suduArray，其中創(chuàng)建函數(shù)inputarray()、outputarray()、isRepeat(int i,int j)和dfs(int count)，在Program類中執(zhí)行main函數(shù)。

（1）數(shù)組array和函數(shù)inputarray()，用于鍵盤輸入數(shù)據(jù)并存放于數(shù)組。

（2）函數(shù)outputarray()，用于輸出結(jié)果。

（3）函數(shù)isRepeat(int i,int j)，用于判斷行、列以及小九宮是否有重復(fù)的數(shù)字。

（4）函數(shù)dfs(int count)，對數(shù)獨九宮格使用回溯法進行檢索。

判斷是否已到達最后一個方格，若是則返回；若不是，則判斷當(dāng)前方格是否需要填數(shù)字，如果不需要填，則跳到下一個方格，如果需要填，則對當(dāng)前方格嘗試所有解。若有解則繼續(xù)下一個，無解則回溯。

（5）Main主函數(shù)，調(diào)用suduArray類中定義的函數(shù)進行求解。

3.2 結(jié)果測試

本實驗是在win7操作系統(tǒng)下，利用Microsoft Visual Studio 2010軟件集成開發(fā)工具編程實現(xiàn)。在Visual C#中創(chuàng)建一個控制臺應(yīng)用程序，運行時通過鍵盤輸入表1所示的初始值，最后得到5組數(shù)據(jù)，結(jié)果如表2所示。從結(jié)果可以看出此數(shù)獨初盤的終盤數(shù)量有5個。

測試過程中，為了計算出得到終盤所耗費的時間，在主函數(shù)中建立了一個Stopwatch類的對象watch1，通過調(diào)用該對象的Start函數(shù)、Stop函數(shù)和ElapsedMilliseconds屬性，可得到求解九宮格的時間。由于計算機運算速度快，通過編程解決這類數(shù)獨問題時，一般可在幾秒或更短的時間內(nèi)得到結(jié)果。

4 結(jié)束語

數(shù)獨的游戲規(guī)則簡單，它具有較強的趣味性和挑戰(zhàn)性，能增進和鍛煉人的推理和邏輯思維能力，但隨著難度的增大，帶來的挑戰(zhàn)也越強。相對于人手求解法，使用計算機求解的研究更具有現(xiàn)實意義。本文探討了解決數(shù)獨問題的各種方法，并通過計算機編程進行求解，最后得出實驗結(jié)果，可以看出本方案對解決這類數(shù)獨問題是非常有效的。

表2 實驗結(jié)果

[1] 曲海平，岳峻，王飛．?dāng)?shù)獨問題的生成與求解算法的研究[J]．科技通報，2017，33(6)：14-17．

[2] 黃皓．?dāng)?shù)獨問題的一種簡單解法[J]．電腦知識與技術(shù)，2014，10(22)：5340-5344．

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

[4] 吳濤．基于排除法填充模型的數(shù)獨求解算法[J]．西安航空學(xué)院學(xué)報，2014，32(3)：77-79．

The Study and Implementation of the Algorithm of Sudoku Problem

Li Xiangqin
（Jingchu University of Technology,Jingmen 448000,Hubei）

Sudoku is a kind of popular crossword puzzle.This paper introduces several commonly used methods of solving Sudoku problem.The solution of Sudoku problem is discussed through concrete examples.Finally,it is realized by C#language.The result shows that the scheme is running with high efficiency,and is easy to understand.

Sudoku;original layout;candidate numbers;backtrack

TP312

A

1008-6609(2017)09-0077-03

李祥琴（1979-），女，湖北荊門人，碩士，講師，研究方向為數(shù)據(jù)庫技術(shù)、數(shù)據(jù)挖掘、軟件工程。