基于排除法填充模型的數(shù)獨求解算法

吳 濤

(西安航空學院 理學院，陜西 西安710077)

引言

九宮格數(shù)獨，是一種源自18世紀末的瑞士，后在美國發(fā)展、并在日本得以發(fā)揚光大的數(shù)字謎題[1]。數(shù)獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數(shù)字和解題條件，利用邏輯和推理，在其他的空格上填入1-9這九個數(shù)字。使1-9每個數(shù)字在每一行、每一列和每一宮中都只出現(xiàn)一次。這種游戲全面考驗做題者的觀察能力和推理能力，雖然玩法簡單，但數(shù)字排列方式卻千變?nèi)f化[2]，所以不少教育者認為數(shù)獨是訓練頭腦的絕佳方式。但是目前使用的數(shù)獨解算器[3-5]，以試探性的遍歷算法進行填充，耗時過長。通過建立排除填充法的數(shù)學模型，并在此基礎(chǔ)上提出一種新型的填充數(shù)獨游戲的算法[6]，通過Matlab編程[7]，在計算機上得以實現(xiàn)。

1 建立數(shù)學模型

1.1 數(shù)獨游戲簡介

如圖1所示，數(shù)獨盤面是九個宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數(shù)字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數(shù)字。使1-9每個數(shù)字在每一行、每一列和每一宮中都只出現(xiàn)一次。

圖1 數(shù)獨

1.2 排除法填充模型

1.2.1 行填充模型

將九宮格數(shù)獨看做是一個9*9的矩陣，那么就可用aij(1<=i<=9,1<=j<=9)表示數(shù)獨第i行，第j列格子里的數(shù)字。設(shè)ai1,ai2,…,aim(1<=m<9)是數(shù)獨中第i行已經(jīng)填充好的m個數(shù)字。

首先，去掉1-9這九個數(shù)中的ai1,ai2,…aim,剩下的數(shù)ai(m+1),ai(m+2),…，ai9就是要填充在第i行剩下的9-m個空白格子里的數(shù)。假設(shè)aik(m+1<=k<=9)填充在第i行第j(1<=j<=9-m)個空白格子里，如果第i行第j個空白格子所處的列位置以及它所對應(yīng)的宮位置中，任何一個格子里的數(shù)字與aik都不相同，那么稱aik適合填充在第i行第j個空白格子里，否則，稱aik不適合填充在第i行第j個空白格子里。

行模型是這樣一種填充原則：如果第i行有且僅有一個空白格子適合填aik(m+1<=k<=9)，那么aik一定填充在該位置，否則，aik不填充。

1.2.2 列填充模型

將九宮格數(shù)獨看做是一個9*9的矩陣，那么就可用aij(1<=i<=9,1<=j<=9)表示數(shù)獨第i行，第j列格子里的數(shù)字。設(shè)a1j,a2j,…,amj(1<=m<9)是數(shù)獨中第j列已經(jīng)填充好的m個數(shù)字。

首先，去掉1-9這九個數(shù)中的a1j，a2j，…，amj，剩下的數(shù)a(m+1)j，a(m+2)j，…，a9j就是要填充在第j列剩下的9-m個空白格子里的數(shù)。假設(shè)akj(m+1<=k<=9)填充在第j列第n(1<=n<=9-m)個空白格子里，如果第j列第n個空白格子所處的行位置以及它所對應(yīng)的宮位置中，任何一個格子里的數(shù)字與akj(m+1<=k<=9)都不相同,那么稱akj(m+1<=k<=9)適合填充在第j列第n個空白格子里, 否則稱akj不適合填充在第j列第n個空白格子里。

列模型是這樣一種填充原則：如果第j列有且僅有一個空白格子適合填akj(m+1<=k<=9)，那么akj(m+1<=k<=9)一定填充在該位置，否則，akj(m+1<=k<=9)不填充。

1.2.3 宮填充模型

數(shù)獨盤面有九個宮，每一宮又分為九個小格。任何一個宮所處的位置可用第i(1<=i<=3)行第j(1<=j<=3)列表示。第k(1<=k<=9)個宮的位置在第i行，第j列，其中k,i,j滿足：k=3(i-1)+j。設(shè)ak1,ak2,…,akm(1<=m<9)是數(shù)獨中第k個宮已經(jīng)填充好的m個數(shù)字。

首先，去掉1-9這九個數(shù)中的ak1,ak2,…,akm(1<=m<=9), 剩下的數(shù)ak(m+1)，ak(m+2)，…，ak9就是要填充在第k個宮中的剩下的9-m個空白格子里的數(shù)。假設(shè)akj(m+1<=k<=9)填充在第k個宮中第L行第n列的一個空白格子， (1<=L<=3，1<=n<=3， L，n與數(shù)獨本身的行與列區(qū)別)，如果第3*(i-1)+L行與第3*(j-1)+n列任何一個格子里的數(shù)字都與akj(m+1<=k<=9)不相同，那么稱akj(m+1<=k<=9)適合填充在第k個宮中第L行第n列的一個空白格子里 (1<=L<=3，1<=n<=3， L，n與數(shù)獨本身的行與列區(qū)別)。

宮填充模型是這樣一種填充原則：如果第k個宮有且僅有一個空白格子適合填akj(m+1<=k<=9)，那么akj(m+1<=k<=9)一定填充在該位置，否則，akj(m+1<=k<=9)不填充。

2 算法描述與實例測試

2.1 算法描述

2.1.1 行填充算法描述

(1)初始化i=1；

(2)對第i行進行填充，填充原則依據(jù)行填充模型；

(3)如果第(2)步中有數(shù)字填充在第i行，從第(2)步開始，否則，從第(4)步開始；

(4)對i自增1，即i=i+1;

(5)如果i<=9，從第(2)步開始，如果i>9，行填充結(jié)束。

2.1.2 列填充算法描述

(1)初始化j=1；

(2)對第j列進行填充，填充原則依據(jù)列填充模型；

(3)如果第(2)步中有數(shù)字填充在第j列，從第(2)步開始，否則，從第(4)步開始；

(4)對j自增1，即j=j+1;

(5)如果j<=9，從第(2)步開始，如果j>9，列填充結(jié)束。

2.1.3 宮填充算法描述

(1)初始化k=1；

(2)對第k個宮進行填充，填充原則依據(jù)宮填充模型；

(3)如果第(2)步中有數(shù)字填充在第k個宮，從第(2)步開始，否則，從第(4)步開始；

(4)對k自增1，即k=k+1;

(5)如果k<=9，從第(2)步開始，如果k>9，宮填充結(jié)束。

2.1.4 主程序算法描述

Matlab語言以矩陣作為基本變量，鑒于這種特點，將數(shù)獨游戲看作9*9的矩陣，作為變量存儲，數(shù)獨中沒有填充的數(shù)字用0代替。

(1)初始化變量nineGrid，變量nineGrid是數(shù)獨游戲的矩陣表示；

(2)對矩陣nineGrid分別按行填充算法，列填充算法以及宮填充算法，進行填充；

(3)如果矩陣nineGrid中有0元素，從第(2)步開始，否則，填充結(jié)束，輸出填充結(jié)果。

2.2 實例測試

圖2 測試的數(shù)獨

對上面的數(shù)獨游戲進行計算機填充實驗，使用Matlab編寫程序的M文件有：FillForm.m，GridFill.m， Initianization.m，judgeGridWhFill.m，judgeLineRowWhFill.m，LineFill.m，RowFill.m， searchZeros.m。

各個M文件的作用：

(1)文件FillForm.m是主程序；

(2)文件GridFill.m用來填充數(shù)獨里九個宮里的數(shù)字；

(3)文件LineFill.m用來填充數(shù)獨九行中的數(shù)字；

(4)文件RowFill.m用來填充數(shù)獨九列中的數(shù)字；

(5)文件judgeGridWhFill.m判斷宮是否能夠填充數(shù)字，它會在GridFill.m文件中被調(diào)用；

(6)文件judgeLineRowWhFill.m判斷行或列是否能夠填充數(shù)字，它會在LineFill.m文件和RowFill.m文件中被調(diào)用；

(7)文件searchZeros.m用來尋找數(shù)獨中空格個數(shù)；

(8)Initianization.m文件初始化給出的數(shù)獨。

運行主程序FillForm.m文件，填充結(jié)果如下：

圖3 填充后的數(shù)獨

可以看出，這種算法填充數(shù)獨的結(jié)果很好。通過比較發(fā)現(xiàn)，該算法比數(shù)獨解算器中使用的遍歷填充算法的效率更高，速度更快。

3 結(jié)語

通過建立排除法填充數(shù)獨的數(shù)學模型，在此基礎(chǔ)上，找到利用計算機實現(xiàn)填充數(shù)獨游戲的一種算法。該算法的優(yōu)點是填充效率高，速度快，不足的地方是該算法不能保證所有的數(shù)獨都能進行填充，這主要是由數(shù)獨本身的結(jié)構(gòu)造成的。因此，如何找到一種數(shù)學模型，使得該模型下給出的算法能夠填充任何結(jié)構(gòu)的數(shù)獨，這是本文算法需要改進的一個方向。

[1] Anniezhm.九宮格數(shù)獨[DB/OL].[2013-11-12].http://baike.baidu.com/view/961.htm.

[2] 王瓊，鄒晟.數(shù)獨問題的求解、評價與生成算法的研究[J].南京師范大學學報：工程技術(shù)版，2010，10(1)：76-79.

[3] 李昊.基于圖搜索策略的數(shù)獨問題算法與實現(xiàn)[J].通化師范學院學報，2009，30(10)：43-45.

[4] 肖華勇，田錚，馬雷.數(shù)獨基于規(guī)則的逐步枚舉算法設(shè)計[J].計算機工程與設(shè)計，2010，31(5):1035-1037.

[5] Gustavo Santos-Garcia. Miguel Palomino.Solving Sudoku Puzzles with Rewriting Rules[J].Electronic Notes in Theoretical Computer Science (ENTCS)，2007，176(4)：79-93.

[6] 約翰森堡，謝菲爾.大學算法教程 [M]. 方存正，曹旻，華明，譯.北京:清華大學出版社，2007：13-15，31.

[7] 張志涌,楊祖櫻.MATLABA教程R2010a[M].北京：北京航空航天大學出版社，2010：37-41.