基于二部圖匹配的數(shù)獨(dú)求解程序

張贊波

摘要：數(shù)獨(dú)游戲是一個(gè)具有組合數(shù)學(xué)背景的智力游戲。在本文中，我們?cè)O(shè)計(jì)一個(gè)基于圖論的數(shù)獨(dú)求解程序。我們將數(shù)獨(dú)的狀態(tài)對(duì)應(yīng)為二部圖，數(shù)獨(dú)的求解對(duì)應(yīng)為二部圖的匹配求解。運(yùn)用二部圖的匹配理論和算法解決數(shù)獨(dú)問題。從網(wǎng)絡(luò)上搜集的一些數(shù)獨(dú)題目作為算法的試驗(yàn)數(shù)據(jù)。對(duì)于一些初始狀態(tài)中含有比較多的數(shù)字的題目，我們的程序能夠解答出最終答案。

關(guān)鍵詞：匹配 二部圖 數(shù)獨(dú)

中圖分類號(hào)：TP3-0 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）07-0046-02

Abstract：Sudoku is a combination of mathematical background of the intelligence game. In this paper， we design a Sudoku solver based on graph theory. We will state for the two corresponding Sudoku Sudoku for solving the corresponding graph， matching to solve the two plans. Using the matching theory and algorithm of the two plans to solve Sudoku problem. Some Sudoku collected from the network as the experimental data of the algorithm. For some of the initial state of the problem contains a number of numbers， our program can answer the final answer.

Key Words：matching two figure Sudoku

1 背景和基本定義

數(shù)獨(dú)游戲是一個(gè)具有組合數(shù)學(xué)背景的智力游戲。一個(gè)數(shù)獨(dú)題目在一個(gè)9 9的方陣上設(shè)計(jì)和解答。該方陣被劃分成9個(gè)3 3的稱為盒子（box）的小方陣，如圖1中粗線所示。方陣的每一個(gè)格子恰好可以填入1到9的某一個(gè)數(shù)字。在游戲的最開始，一部分方格已經(jīng)填上了數(shù)字，如圖1。游戲的目標(biāo)是把方陣余下的每一個(gè)格子也填上數(shù)字，使得每行，每列和每個(gè)盒子的9個(gè)格子中都恰含有數(shù)字1到9。

我們對(duì)方陣的格子如圖2進(jìn)行編號(hào)。首先我們對(duì)方陣的行和列進(jìn)行編號(hào)。方陣的行，自上而下編號(hào)為第1行至第9行。方陣的列，自左到右為編號(hào)第1到第9列。然后我們對(duì)格子進(jìn)行編號(hào)。位于第r行第c列的格子編號(hào)為 （r， c），1 ≤ r， c ≤ 9。由于空間所限，在圖2中我們將格子的編號(hào) （r， c） 簡寫成rc。

在本文中，我們運(yùn)用二部圖的匹配理論來求解數(shù)獨(dú)題目。下面先給出我們將用到的一些圖論的基本概念。一個(gè)圖G=（V， E） 包含一個(gè)頂點(diǎn)集合V和一個(gè)邊集E，E是V的元素的二元組集合。一條邊e所包含的兩個(gè)頂點(diǎn)元素稱為e的端點(diǎn)。我們討論的圖都是簡單的，也就是不存在一條邊，它的兩個(gè)端點(diǎn)相同；同時(shí)，兩個(gè)端點(diǎn)之間最多只有一條邊。一個(gè)圖稱為二部圖，如果它的頂點(diǎn)集合可以分成兩個(gè)子集U和W，使得它的每一條邊的兩個(gè)端點(diǎn)都分別落在U和W中?；蛘邠Q句話說，在U和W內(nèi)部沒有邊。我們把這樣的二部圖記為G=（U， W）。若|U|=|W|，則稱此二部圖為平衡二部圖。若U中的每個(gè)點(diǎn)都與W中的每個(gè)點(diǎn)相鄰，稱此二部圖為完全二部圖。如果一個(gè)圖中的兩條邊具有公共的端點(diǎn)，則稱它們相鄰。一條邊的兩個(gè)端點(diǎn)也稱為相鄰的。與一個(gè)頂點(diǎn)相鄰的所有頂點(diǎn)的集合稱為它的鄰居。匹配是指圖的一個(gè)兩兩不相鄰的邊集。我們稱一條邊覆蓋它的端點(diǎn)。如果一個(gè)匹配中的邊覆蓋了圖的所有頂點(diǎn)，則稱此匹配為完美匹配。顯然，具有完美匹配的二部圖必須是平衡二部圖。

一條邊和它的端點(diǎn)稱為互相關(guān)聯(lián)。一個(gè)頂點(diǎn)關(guān)聯(lián)的邊的條數(shù)，或等價(jià)地它的鄰居的個(gè)數(shù)，稱為它的度數(shù)。取圖G的頂點(diǎn)集合V的一個(gè)子集V1，構(gòu)造一個(gè)圖G1=（V1， E1），其中E1是G中所有兩個(gè)端點(diǎn)都落在V1中的邊的集合，圖G1稱為頂點(diǎn)子集合V1的導(dǎo)出子圖。

2 基于匹配理論的數(shù)獨(dú)求解

我們定義一個(gè)動(dòng)態(tài)的二部圖G=（U， W），其中U={（1， 1）， （1， 2）， …， （9， 9）}是數(shù)獨(dú)方陣中格子的集合，而W={1， 2， 3， 4， 5， 6， 7， 8， 9}是格子中可以填入的數(shù)字的集合。在一個(gè)數(shù)獨(dú)題的最終解中，所有81個(gè)格子中的數(shù)字都已經(jīng)確定。如果數(shù)字d W填入方格（r， c） U中，那么我們?cè)贕中連結(jié)d與（r， c）。這樣共產(chǎn)生81條邊。U中的每一個(gè)頂點(diǎn)恰發(fā)出一條邊到W集合中填在頂點(diǎn)對(duì)應(yīng)的方格中的數(shù)字。從而U中頂點(diǎn)的度數(shù)全部為1。而W中每一個(gè)數(shù)字在方陣中恰出現(xiàn)9次，因此W中代表每一個(gè)數(shù)字的頂點(diǎn)的度數(shù)全部為9。

取所有位于方陣第r（1 ≤ r ≤ 9）行的格子所組成的U的子集，該子集與W的并集構(gòu)成G的一個(gè)頂點(diǎn)集，記該頂點(diǎn)集的導(dǎo)出子圖為Rr。對(duì)于方陣的第c（1 ≤ c ≤ 9）列，我們類似定義該列的格子與W的并集在G中的導(dǎo)出子圖Cc。而對(duì)于方陣的第b（1 ≤ b ≤ 9）個(gè)盒子，我們也類似定義盒子中的格子與W的并集在G中的導(dǎo)出子圖Bb。稱上述27個(gè)子圖為完美子圖。如圖3與圖4所示。對(duì)一個(gè)數(shù)獨(dú)題的最終解而言，每行，每列和每個(gè)盒子恰含有數(shù)字1到9，意味著G的完美子圖的邊集恰好構(gòu)成該子圖本身的一個(gè)完美匹配。

在G的初始狀態(tài)，我們連結(jié)所有的頂點(diǎn)（r， c） U與頂點(diǎn)d W，使得G成為一個(gè)完全二部圖。在我們解決數(shù)獨(dú)方陣的推理過程中，我們不斷通過現(xiàn)已填入的數(shù)字，排除其他方格中可能填入的數(shù)字。以此為根據(jù)，我們可以刪除G的邊：如果在某一步，我們排除了方格（r， c） U中填入數(shù)字d W的可能，則刪除掉（r， c）與d之間的邊。這樣圖G的邊的狀態(tài)便記錄了我們推理的中間結(jié)果。反之，我們可以從圖G的完美子圖根據(jù)匹配理論進(jìn)行推導(dǎo)，從而排除某些方格中填上某個(gè)數(shù)的可能。當(dāng)G最終剩余81條邊，U中的每一個(gè)頂點(diǎn)的度數(shù)為1，W中的每一個(gè)頂點(diǎn)的度數(shù)為9時(shí)，我們就得到了數(shù)獨(dú)問題的最終解。

我們從G為完全圖的狀態(tài)開始。當(dāng)給定一個(gè)數(shù)獨(dú)題目的初始狀態(tài)，即一個(gè)填入了部分?jǐn)?shù)字的9 9的方陣，我們可以根據(jù)該狀態(tài)對(duì)G進(jìn)行刪邊的操作。假設(shè)方格（r， c）中已經(jīng)填上了數(shù)字d，其中d W，則我們可以去掉所有與（r， c）相關(guān)聯(lián)的邊，僅保留（r， c）與d之間的邊。此外，注意到（r， c）包含于3個(gè)完美子圖Rr，Cc和Bb，其中b = [r/3]*27+（r mod 3）*3+[c/3]*9+（c mod 3），我們可以去掉子圖Rr，Cc和Bb中除了（r， c）以外其它格子與d之間的邊。對(duì)每一個(gè)已經(jīng)填上數(shù)字的方格（r， c）完成了上述刪除操作以后，我們就用圖G表示出數(shù)獨(dú)題目的初始狀態(tài)。

在以圖的匹配建模以后，我們最終的目標(biāo)是使得圖G剩下81條邊，而每個(gè)完美子圖的邊集恰剩下一個(gè)完美匹配。因此，解數(shù)獨(dú)題的過程，就是不斷根據(jù)現(xiàn)有的邊進(jìn)行推理，刪去當(dāng)前圖G的某一個(gè)完美子圖中所有的不可能包含于任何完美匹配的邊。我們把一個(gè)圖中不含于任何完美匹配的邊稱為禁止邊。因?yàn)橐粭l邊包含于3個(gè)完美子圖，當(dāng)我們?cè)谝粋€(gè)完美子圖中刪去禁止邊，便會(huì)使得其它完美子圖的邊減少。因此，我們又可以在受影響的完美子圖中重新尋找禁止邊，將其刪去。數(shù)獨(dú)題目求解的過程，就是不斷的在完美子圖中刪去禁止邊，一直到確定所有方格中的數(shù)字。

為了進(jìn)一步說明求圖的匹配與求解數(shù)獨(dú)題的邏輯推理的關(guān)系，我們以圖5的數(shù)獨(dú)局部狀態(tài)為例。在圖5中，由于（1， 2）和（3， 5）都為3，我們可以推知在B3之中，數(shù)字3必然位于第二行，即三個(gè)格子（2， 7），（2， 8）或（2， 9）之一（圖中以“*”號(hào)標(biāo)注）。因此其它的六個(gè)格子（1， 7），（1， 8），（1， 9），（3， 7），（3， 8）和（3， 9）與3相連的邊應(yīng)該刪去，而（2， 7），（2， 8）和（2， 9）則繼續(xù)有邊發(fā)向3。從圖G中看，我們的上述推理可以由匹配理論來完成，在R1中（1， 2）和3相鄰，從而可以刪除掉3與其它格子相連的邊。因此3和（1， 7），（1， 8），（1， 9）之間沒有邊相連。同理在R3中（3， 5）和3相鄰，從而可以刪除掉3與其它格子相連的邊。因此3和（3， 7），（3， 8），（3， 9）之間沒有邊相連。上述刪除掉的邊也屬于子圖B3，因此在B3中3只能和（2， 7），（2， 8）和（2， 9）相鄰。

3 算法的實(shí)現(xiàn)

圖G有27個(gè)完美子圖。在某一狀態(tài)，必定能夠從一個(gè)完美子圖中找到一些禁止邊，并將它們?nèi)サ?。由于去掉了一個(gè)完美子圖的一些禁止邊以后，影響了其他完美子圖的結(jié)構(gòu)，因而會(huì)在其他完美子圖中產(chǎn)生新的禁止邊，從而又可以在其他完美子圖中進(jìn)一步尋找新產(chǎn)生的禁止邊。因此，我們算法的思路，就是循環(huán)地對(duì)圖G的27個(gè)完美子圖進(jìn)行考察，刪掉它們的禁止邊。直到圖G剩下81條邊為止。

要求出一個(gè)二部圖的禁止邊，可以使用現(xiàn)有的算法，目前速度最快的算法（O（VE））可參見參考文獻(xiàn)[1]。但是，我們處理的僅僅是一個(gè)18個(gè)點(diǎn)的平衡二部圖，因此可以直接使用所謂蠻力（brute force）算法。Brute force算法對(duì)每一條邊執(zhí)行以下操作：從圖中刪掉該邊及其兩個(gè)端點(diǎn)，驗(yàn)證余下的子圖是否有完美匹配，從而判斷該邊是否禁止邊。而判斷二部圖是否有完美匹配則采用經(jīng)典的匈牙利算法[2]。求二部圖所有禁止邊的集合的算法流程圖見算法1。求解數(shù)獨(dú)的主算法見算法2。

算法1：求二部圖G的禁止邊的集合。

輸入：二部圖G。

輸出：圖G的禁止邊的集合。

1對(duì)于每一條邊e E，執(zhí)行如下操作2至4。

2從G中刪除e和e的端點(diǎn)。得到圖G-e。

3調(diào)用匈牙利算法判斷G-e是否有完美匹配。

4如果G-e沒有完美匹配，則標(biāo)記e為G的禁止邊。

5輸出所有標(biāo)記為禁止邊的邊e。

算法2：求解數(shù)獨(dú)

輸入：一個(gè)數(shù)獨(dú)游戲的初始狀態(tài)。

輸出：該數(shù)獨(dú)游戲的最終解。

1構(gòu)建完全二部圖G。

2根據(jù)數(shù)獨(dú)游戲的初始狀態(tài)，刪除G的禁止邊，使得G對(duì)應(yīng)于數(shù)獨(dú)游戲的初始狀態(tài)。

3重復(fù)以下步驟4至6，直到G的邊數(shù)等于81。

4對(duì)于c=1到9，調(diào)用算法1求解完美子圖Cc的禁止邊的集合，將其從Cc中刪除。

5對(duì)于r=1到9，調(diào)用算法1求解完美子圖Rr的禁止邊的集合，將其從Rr中刪除。

6對(duì)于b=1到9，調(diào)用算法1求解完美子圖Bb的禁止邊的集合，將其從Bb中刪除。

4 試驗(yàn)和進(jìn)一步工作

我們使用從網(wǎng)絡(luò)上搜集的一些數(shù)獨(dú)題目作為算法的試驗(yàn)數(shù)據(jù)。對(duì)于一些初始狀態(tài)中含有比較多的數(shù)字（超過25個(gè)數(shù)字）的題目，我們的程序能夠解答出最終答案。但是對(duì)于一些比較困難的數(shù)獨(dú)題目，如西澳大學(xué)Gordon Royle教授收集的具有最小初始狀態(tài)（17個(gè)數(shù)字）的數(shù)獨(dú)題集，我們的程序不能求解出最終答案。因此，我們還需要進(jìn)一步探討對(duì)算法的改進(jìn)。

在文獻(xiàn)[3]中，作者在研究匹配覆蓋圖的過程中，定義了一個(gè)具有完美匹配的圖中的邊關(guān)于完美匹配的依賴關(guān)系（簡稱為邊的依賴關(guān)系）。對(duì)于兩條邊e和f，我們稱e依賴于f，如果每一個(gè)含有e的完美匹配一定含有f。我們認(rèn)為，如果在算法中加入求解每一個(gè)完美子圖的邊依賴關(guān)系，并根據(jù)邊依賴關(guān)系作進(jìn)一步推理，將很有可能提高我們的程序的求解能力，甚至有可能徹底解決所有的數(shù)獨(dú)問題實(shí)例。我們擬于下一步工作中根據(jù)這個(gè)思路對(duì)算法作進(jìn)一步改進(jìn)。

參考文獻(xiàn)

[1]Y.Li，& D.Lou.A new algorithm for determinating 1-extendable graphs： design and implementation. In IMECS，2327-2332，2007.3.

[2]L. Lovász， & M. D. Plummer，M.D.Matching theory （Vol. 367）. American Mathematical Soc.， 2009.

[3]de Carvalho， M. H.，Lucchesi，C.L.，& Murty，U.S. （2002）. On a conjecture of lovász concerning bricks：I.the characteristic of a matching covered graph. Journal of Combinatorial Theory， Series B， 85（1）94-136.