數獨問題求解算法的研究與實現

李祥琴

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

數獨問題求解算法的研究與實現

李祥琴

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

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

數獨；初盤；候選數；回溯法

1 引言

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

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

2 數獨的求解方法

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

數獨中的數字千變萬化，解法也隨之靈活各樣，主要有摒除法、余數法、隱含唯一數法、數對法和回溯法[2-4]。

（1）摒除法

在每行、每列以及小九宮中，每個數字只能出現一次，若某一行已經出現了一個數字8，該行其它方格候選數就不能填數字8。

（2）余數法

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

（3）隱含唯一數法

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

（4）數對法

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

（5）回溯法

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

3 計算機編程實現

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

表1 數獨初盤

3.1 數據結構和算法設計

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

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

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

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

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

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

（5）Main主函數，調用suduArray類中定義的函數進行求解。

3.2 結果測試

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

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

4 結束語

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

表2 實驗結果

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

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

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

[4] 吳濤．基于排除法填充模型的數獨求解算法[J]．西安航空學院學報，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-），女，湖北荊門人，碩士，講師，研究方向為數據庫技術、數據挖掘、軟件工程。