數獨問題在C 語言中的模擬算法

楊曉華

（商丘醫學高等專科學校現代教育技術中心，河南商丘，476100）

0 引言

數獨的名字來源于日語Sudoku，可以理解為“獨立的數字 ”。它起源于18 世紀末的瑞士，是一種很有挑戰性的數學智力拼圖游戲。數獨的玩法邏輯簡單，數字排列方式千變萬化。不少教育者認為數獨是鍛煉腦筋的好方法。數獨游戲成功的原因除了它的趣味性和挑戰性之外，更重要的原因其實是因為它很容易上手。數獨游戲的規則是：在一個9×9 的大正方形中，預先填入一些數字 ，要求游戲者按照規則填完其它的空格，如下圖所示，規則如下：

(1)每個空格內所填的數字只限于1—9 之間；

(2)每個數字在每一行中只能出現一次；

(3)每個數字在每一列中只能出現一次；

(4)每個數字在每一區內(3×3 的小九宮)只能出現一次。

2 數獨解題思路

數獨游戲上手簡單，但是隨著難度的加大將會充滿挑戰。數獨的解題方法多種多樣，歸納起來主要有三種方法：唯一法、排除法和回溯法。

2.1 唯一法

以上面的圖示為例說明用C 語言模擬數獨問題的人工解題思路。此題的

數據結構如下 ：

#define N 9

int a[N][N]=｛{0，0，0，0，0，0，9，0，0)，{0，0，0，4，0，6，0，0，0)，{0，5，9，0，0，8，0，0，0)，

{0，4，0，8，0，1，3，9，0)，{3，0，1，7，0，9，4，0，0)，(7，9，0，3，0，0，6，0，5)，

{8，1，0，9，2，3，0，0，0｝，{0，2，0，6，0，0，0，0，9}，{0，3，4，5，8，0，0，0，2}}：

其是 N 的值為9，0 代表空格 。a 是一個二維數組，存放數獨的 9×9 九宮格， 下標從 0 開始，如第一行第 7 列的9 表示為 a。按照人為的解題思路來考慮，首先要找到的是哪一個空格只有唯一解，由本題可見，a 只能填入 7，a 只能填入 8，a[5][4]只能填入 4。

for(i=O；i＜9；i++)

a 只能填入7，因為其行、列或區中已經有了除 7 以外其它 1 ～9 中的8 個數據。人可以一眼看出象這樣的唯一解，但計算機不行，必須用相應的程序來實現此功能。首先需要查看一下與它同列的有哪些數據 (5，9，2)不能填，再查看一下與它同行的有哪些數據 (4，8，1，3，9)不能填，與它同一個區的有哪些數據 (3，9，4，6，5)不能填，不能填的數據放到b 數組，查找b 數組相應位置中能填的數據個數，如果個數為 1 的話，就說明該位置只能填入 7 這一個數據。

唯一法還可以擴展 ，例如，我們可以觀察a，在前3 行構成的3 個區中，第0 行和第2 行都出現相同的數據9，而且9 出現在三行的0 區和2 區中，那么9 在第1 行1 區中也應該出，第1 行1 區中總共三個數據，其中a 和a 已經存在，則肯定是a 為9，或者說a不存在，因為在第3列中已經有了數字 9(a)，那么a也不可能是9，同樣也只能在a 填入9，可以用如下程序段實現該過程:

2.2 排除法

經常見到某行、某列或某區的兩個數字出現候選數相同的情況，那么在該行、該列或該區的其它空格的候選數就可以刪除相同的數據，因為不可能再填入該數據。例如 ，某個區中有三個空格，其中的兩個空格能填入的數字只能是1 或 2，那么第三個空格就不能再填入 l、2 中的任一個數了，當每三個空格將1、2這兩個可選數據去掉之后，可能就剩下唯一的一個可選數據 。

2.3 回溯法

在一些復雜題目當中，使用了唯一法和排除法之后，仍然無法做下去，這時只好采用回溯法。首先選一個候選數最少的空格，比如說它只能填入的數據是2 和5，但不知道選2 和5 中的哪一個。先選擇其中的較小數據2 把它填入，這一數據填對的概率為50%，然后往下判定其他的空格，結果發現最終無法解題即出現沖突現象，那么前面的假設就是錯誤的，重新選擇5 來填入，再繼續往下解題。回溯法需要用到棧或者圖搜索的策略。

3 結語

經過試驗，本程序可以解決許多數獨題目。這個程序的實現，完全是用計算機模擬人工進行數獨問題的解決辦法，表明用計算機模擬人工智能雖然有一定的難度，但是編制特定的算法完成搜索過程是完全可能實現的。

[1] 程曦,肖華勇,吳林波.數獨求解的候選數優化算法設計[J].科學技術與工程,2011,26:6409-6412.

[2] 吳濤.基于排除法填充模型的數獨求解算法[J].西安航空學院學報,2014,03:77-80.

[3] 胡遠望.用C 語言模擬數獨的人工解題思路[J].電腦編程技巧與維護,2009,05:14-16.

[4] 孟慶鈴.數獨問題人工解法的程序實現[J].甘肅科技,2006,09:150-151.

[5] 張宗科.在AutoCAD 中編程實現Sudokupuzzle 的求解及生成[J].電腦編程技巧與維護,2008,17:16-18+21.

[6] 李盤榮.“數獨”游戲的算法研究與實現[J].電腦知識與技術,2008,26:1715-1717.