王海燕，黃 駿

(1.宿遷學(xué)院信息工程學(xué)院，江蘇 宿遷 223800； 2.南方科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，廣東 深圳 518055)

一種分?jǐn)?shù)維改進(jìn)的長(zhǎng)方棋盤覆蓋算法

王海燕1，黃 駿2

(1.宿遷學(xué)院信息工程學(xué)院，江蘇 宿遷 223800； 2.南方科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，廣東 深圳 518055)

基于含有一個(gè)特殊方格的ik×jk棋盤結(jié)構(gòu)，提出了一種改進(jìn)與推廣的長(zhǎng)方棋盤覆蓋算法。利用類似L型骨牌總是可以覆蓋其余不含特殊方格子棋盤的頂點(diǎn)交匯處這一特點(diǎn)，對(duì)不含特殊方格的子棋盤算法進(jìn)行改進(jìn)，采用直接+間接遞歸及分治策略思想，以i=j=2為例設(shè)計(jì)了4個(gè)模塊函數(shù)。該算法不僅避免了非特殊方格遞歸求解的盲目性，也減少了棋盤深層遞歸的層數(shù)。實(shí)驗(yàn)結(jié)果表明：與已有算法相比，改進(jìn)的算法具有更好的性能。更加便于任意形狀圖像加密過程中所需的行與列不相等的二維隨機(jī)密鑰的生成。

棋盤覆蓋；分治策略；直接遞歸；間接遞歸；圖像加密

0 引言

棋盤問題是一個(gè)經(jīng)典問題，早在1848年的時(shí)候，德國(guó)象棋大師馬克思就提出解決8個(gè)女皇的棋盤覆蓋難題的第一套方案，德國(guó)數(shù)學(xué)家高斯先生把8個(gè)女皇的棋盤覆蓋推廣到了n個(gè)女皇。到了1946年的時(shí)候，美國(guó)哲學(xué)家馬克思又提出了二缺格國(guó)際象棋棋盤的類似圍棋棋盤的雙格骨牌填充方法的難題，掀起了第二次棋盤覆蓋的研究熱潮，1973年的時(shí)候，這個(gè)難題被美國(guó)數(shù)學(xué)家Gomory一舉解決，到了20世紀(jì)80年代，基于四格骨牌的俄羅斯方塊的游戲由此產(chǎn)生，今天類似的算法已經(jīng)被廣泛應(yīng)用于數(shù)學(xué)領(lǐng)域[1-4]及計(jì)算機(jī)領(lǐng)域的文件加密[5]、圖像加密[6-7]等技術(shù)處理中。馮躍峰[8]在數(shù)學(xué)上對(duì)中外棋盤覆蓋問題進(jìn)行了系統(tǒng)的總結(jié)闡述，給出的棋盤定義：所謂m×n棋盤是指由m行n列方格構(gòu)成的m×n矩形，簡(jiǎn)稱棋盤，每個(gè)方格稱為棋盤的格，在一個(gè)ik×jk個(gè)方格組成的棋盤中，如有一個(gè)方格與其他方格不同，比如已經(jīng)被填上代表棋子的字母、數(shù)字、符號(hào)或顏色，則稱該方格為特殊方格；在計(jì)算機(jī)上解決棋盤覆蓋問題使用分治策略，分治策略思想是分而治之，把一個(gè)復(fù)雜的問題分成多個(gè)相同或相似的子問題，再把子問題繼續(xù)劃分為更小的子問題，直到可以簡(jiǎn)單求得最小問題，原問題的解即是子問題解的合并。采用該策略給出棋盤覆蓋的計(jì)算機(jī)實(shí)現(xiàn)方法[9]：用L型骨牌覆蓋給定的棋盤上除特殊方格以外的所有方格，但是該算法沒有考慮L型骨牌覆蓋棋盤的特殊性，致使算法性能下降。

本文提出了一種直接+間接遞歸及分治策略相結(jié)合的算法，可以改進(jìn)非特殊方格的棋盤算法性能。當(dāng)行數(shù)與列數(shù)不是2的倍數(shù)，又不相等的時(shí)候，我們利用分?jǐn)?shù)維自相似的概念，將類似L型骨牌打碎，填補(bǔ)到i行j列的子棋盤的頂點(diǎn)交匯處。在分形幾何中，分?jǐn)?shù)維D(即分形維數(shù))是一個(gè)描述一個(gè)分形對(duì)空間填充程度的統(tǒng)計(jì)量。分?jǐn)?shù)維的定義根據(jù)運(yùn)用場(chǎng)景的精細(xì)程度有幾個(gè)變種，主要的分?jǐn)?shù)維定義方法是豪斯多夫維數(shù)、計(jì)盒維數(shù)和分配維數(shù)等。在分形幾何中，計(jì)盒維數(shù)也稱為盒維數(shù)、閔可夫斯基維數(shù)，是一種測(cè)量距離空間，特別是豪斯多夫空間，比如歐氏空間中分形維數(shù)的常用計(jì)算方法。要計(jì)算分形的維數(shù)，可以想象把這個(gè)分形放在一個(gè)均勻分割的網(wǎng)格上，數(shù)一數(shù)最小需要幾個(gè)格子來覆蓋這個(gè)分形。通過對(duì)網(wǎng)格的逐步精化，查看所需覆蓋數(shù)目的變化，從而計(jì)算出計(jì)盒維數(shù)。換一個(gè)角度看，分形就好比是一個(gè)破碎的整形空間，在整形中看到的破碎骨牌，在分形中看到的可能就是一個(gè)完整的骨牌。它表征分形在通常的幾何變換下具有不變性，即標(biāo)度無關(guān)性。自相似性是從不同尺度的對(duì)稱出發(fā)，也就意味著遞歸。線性分形又稱為自相似分形。自相似原則和迭代生成原則是分形理論的重要原則。標(biāo)準(zhǔn)的自相似分形是數(shù)學(xué)上的抽象，迭代生成無限精細(xì)的結(jié)構(gòu)，如科契雪花曲線、謝爾賓斯基地毯等。

當(dāng)i=j=2時(shí)，棋盤類似象棋或圍棋棋盤；象棋棋盤的覆蓋問題游戲規(guī)則種類繁多，圍棋棋盤的覆蓋問題規(guī)則相對(duì)簡(jiǎn)單一點(diǎn)，但是排列組合遠(yuǎn)遠(yuǎn)超過象棋棋盤，谷歌的深度學(xué)習(xí)算法戰(zhàn)勝了韓國(guó)圍棋大師，說明了人工智能算法已經(jīng)在正方形的二維圖像處理上有了突破性的進(jìn)展。當(dāng)i=j=3時(shí)，棋盤類似中國(guó)古代的九宮圖。當(dāng)我們利用這類算法對(duì)二維圖像進(jìn)行加密的時(shí)候，會(huì)發(fā)現(xiàn)所有的圖像格式其實(shí)都不是像棋盤那樣的正方形，而是3∶2，4∶3或者16∶9等等的長(zhǎng)方形，因此有必要把算法推廣到像素的行與列不相等的情形，以便快速地處理實(shí)時(shí)的視頻電影信息等等。正方形是長(zhǎng)方形的特例，適合于正方形的算法不一定合適長(zhǎng)方形，相反適合于長(zhǎng)方形的算法不一定合適正方形，所以我們需要在正方形的基礎(chǔ)上對(duì)長(zhǎng)方形棋盤做了一些開拓性的初步研究。基本思路就是把大L骨牌橫向和(或)縱向打碎，適應(yīng)長(zhǎng)方形的形狀。

1 算法研究

采用分治策略可將棋盤劃分為如圖1所示的4個(gè)2(k-1)×2(k-1)個(gè)子棋盤，特殊方格必位于較小子棋盤之某個(gè)方格中。圖2所示為L(zhǎng)型骨牌的4種不同的存在形式，使其覆蓋不含特殊方格的3個(gè)子棋盤交匯處，如圖3所示。未被L型骨牌覆蓋的方格就成了含特殊方格的更小規(guī)模子棋盤。

圖1 2k×2k棋盤(k=3)

圖2 4種不同形態(tài)的L型骨牌

圖3 L型骨牌覆蓋非特殊方格的子棋盤交匯處

經(jīng)典的棋盤覆蓋算法是將規(guī)模2k×2k的棋盤劃分為4個(gè)子棋盤，進(jìn)而對(duì)任一個(gè)子棋盤覆蓋問題采用直接遞歸調(diào)用，而沒有考慮L型骨牌覆蓋棋盤時(shí)，總是覆蓋不含特殊方格的子棋盤交匯處的這一特點(diǎn)，改進(jìn)的算法充分考慮了這一特性。

為了敘述方便，把特殊方格分為兩類：一類是已知條件的特殊方格，該特殊方格是隨機(jī)放置，稱為Irregular方格棋盤，圖3所示的子棋盤4稱為Irregular方格棋盤；另一類是通過L型骨牌覆蓋而形成規(guī)則方格的子棋盤，稱為Regular方格棋盤，圖3所示的子棋盤1、子棋盤2、子棋盤3均為Regular方格棋盤。含有Irregular方格的子棋盤直接遞歸調(diào)用，而對(duì)于Regular方格的棋盤，則應(yīng)采用直接+間接遞歸并用的調(diào)用方式。

根據(jù)L型骨牌覆蓋子棋盤的位置，可將Regular方格棋盤分為4類情況：第1種情況，通過L型骨牌覆蓋的位置在子棋盤左上角，如圖4(a)所示，記作LTChessBoard棋盤；第2種情況，通過L型骨牌覆蓋的位置在子棋盤左下角，如圖4(b)所示，記作LBChessBoard棋盤；第3種情況，通過L型骨牌覆蓋的位置在子棋盤右上角，如圖4(c)所示，記作RTChessBoard棋盤；第4種情況，通過L型骨牌覆蓋的位置在子棋盤右下角，如圖4(d)所示，記作RBChessBoard棋盤。

圖4 4種Regular方格棋盤

2 各模塊算法設(shè)計(jì)

棋盤可以用一個(gè)二維數(shù)組表示board，二維數(shù)組大小2k×2k；用L型骨牌覆蓋含特殊方格的2k×2k棋盤，容易得出需要L型骨牌的個(gè)數(shù)為(4k-1)/3個(gè)，將所有L型骨牌從1開始編號(hào)，則問題可以轉(zhuǎn)化為用整形title變量值覆蓋棋盤方格。為了遞歸處理的過程使用同一個(gè)棋盤、同一個(gè)變量覆蓋，將二維數(shù)組和title變量設(shè)計(jì)為全局量。

2.1 主模塊算法設(shè)計(jì)

用dr，dc表示特殊方格的行標(biāo)和列標(biāo)，則特殊方格可以用board[dr][dc]表示。不同用戶或同一用戶輸入特殊方格的位置沒有具體要求，因此特殊方格的位置可以是2k×2k棋盤中的任一方格且無規(guī)律，因此主模塊首先調(diào)用的算法是Irregular棋盤算法。

2.2 Irregular棋盤算法設(shè)計(jì)

任一子棋盤可由左上角的位置(tr，tc)及棋盤面積s表示，初始的Irregular棋盤被遞歸劃分為4個(gè)子棋盤，分別是子棋盤1、子棋盤2、子棋盤3、子棋盤4，如圖1所示。

把含有用戶任意輸入的特殊方格棋盤采用直接遞歸的調(diào)用；其余子棋盤采用直接+間接遞歸調(diào)用，即根據(jù)L型骨牌覆蓋子棋盤的位置不同，調(diào)用對(duì)應(yīng)的算法。根據(jù)用戶輸入的特殊方格的位置，將Irregular棋盤算法也分為4種情況：第1種情況：用戶輸入的特殊方格位于子棋盤1中，子棋盤1采用直接遞歸調(diào)用算法，子棋盤2、3、4用L型骨牌覆蓋交匯處，并分別調(diào)用LBChessBoard、RTChessBoard、LTChessBoard棋盤算法；第2種情況：用戶輸入的特殊方格位于子棋盤2中，棋盤2采用直接遞歸調(diào)用算法，棋盤1、3、4用L型骨牌覆蓋交匯處，并分別調(diào)用RBChessBoard、RTChessBoard、LTChessBoard棋盤算法；第3種情況：用戶輸入的特殊方格位于子棋盤3中，棋盤3采用直接遞歸調(diào)用算法，棋盤1、2、4用L型骨牌覆蓋交匯處，并分別調(diào)用RBChessBoard、LBChessBoard、LTChessBoard棋盤算法；第4種情況：用戶輸入的特殊方格位于子棋盤4中，棋盤4采用直接遞歸調(diào)用算法，棋盤1、2、3用L型骨牌覆蓋交匯處，并分別調(diào)用RBChessBoard、LBChessBoard、RTChessBoard棋盤算法。

2.3 Regular棋盤算法設(shè)計(jì)

2.3.1 RBChessBoard棋盤

遞歸劃分RBChessBoard子棋盤為4個(gè)更小子棋盤，即劃分為子棋盤1-1、1-2、1-3、1-4 4個(gè)子棋盤，如圖5(a)所示。特殊方格一定在子棋盤1-4的左下角，故直接遞歸調(diào)用RBChessBoard棋盤算法，L型骨牌覆蓋子棋盤1-1、1-2、1-3。子棋盤1-1直接遞歸調(diào)用RBChessBoard棋盤算法，子棋盤1-2、1-3分別調(diào)用LBChessBoard、RTChessBoard棋盤算法。

2.3.2 LBChessBoard棋盤

遞歸劃分LBChessBoard子棋盤為4個(gè)更小子棋盤，即劃分為子棋盤2-1、2-2、2-3、2-4 4個(gè)子棋盤，如圖5(b)所示。特殊方格一定在子棋盤2-3的左下角，故直接遞歸調(diào)用LBChessBoard棋盤算法，L型骨牌覆蓋子棋盤2-1、2-2、2-3。子棋盤2-2直接遞歸調(diào)用LBChessBoard棋盤算法，子棋盤2-1、2-4分別調(diào)用RBChessBoard、LTChessBoard棋盤算法。

2.3.3 RTChessBoard棋盤

遞歸劃分RTChessBoard子棋盤為4個(gè)更小子棋盤，即劃分為子棋盤3-1、3-2、3-3、3-4 4個(gè)子棋盤，如圖5(c)。特殊方格一定在子棋盤3-2的右上角，故直接遞歸調(diào)用RTChessBoard算法，L型骨牌覆蓋子棋盤3-1、3-2、3-3。子棋盤3-3直接遞歸調(diào)用RTChessBoard棋盤算法，子棋盤3-1、3-4分別調(diào)用RBChessBoard、LTChessBoard棋盤算法。

2.3.4 LTChessBoard棋盤

遞歸劃分LTChessBoard子棋盤為4個(gè)更小子棋盤，即劃分為子棋盤4-1、4-2、4-3、4-4 4個(gè)子棋盤，如圖5(d)所示。特殊方格一定在子棋盤LT1-1的左上角，故直接遞歸調(diào)用LTChessBoard棋盤算法，L型骨牌覆蓋子棋盤4-1、4-2、4-3。子棋盤4-4直接遞歸調(diào)用LTChessBoard棋盤算法，子棋盤4-2、4-3分別調(diào)用LRBChessBoard、RTChessBoard棋盤算法。

圖5 4個(gè)子棋盤劃分為更小的棋盤

3 算法性能分析

為了分析改進(jìn)后的算法和傳統(tǒng)算法執(zhí)行時(shí)間的優(yōu)劣，表1給出傳統(tǒng)棋盤覆蓋算法的運(yùn)行時(shí)間復(fù)雜度和改進(jìn)后棋盤覆蓋算法運(yùn)行時(shí)間復(fù)雜度?？梢钥闯鰞深愃惴ㄔ趉=0與k>0時(shí)，算法時(shí)間復(fù)雜度趨于相等，但由于算法時(shí)間復(fù)雜度是一個(gè)漸近值，考察這兩類算法性能的優(yōu)劣是不足夠的。

表1 不同算法時(shí)間復(fù)雜度比較

對(duì)表1的每一項(xiàng)分析可知：

1)當(dāng)k=0時(shí)棋盤只有一個(gè)棋格，兩類算法沒有任何區(qū)別；

2)當(dāng)k>0時(shí)，考察算法的性能主要由3個(gè)部分組成：測(cè)試特殊方格、覆蓋子棋盤及覆蓋子棋盤需4次遞歸調(diào)用，其中覆蓋子棋盤與覆蓋子棋盤調(diào)用次數(shù)二者沒有區(qū)別。而傳統(tǒng)算法由于沒有考慮覆蓋子棋盤的特殊性，致使程序不斷在子棋盤中測(cè)試特殊方格，測(cè)試次數(shù)也隨著棋盤的不斷劃分而不斷的增大；改進(jìn)后的棋盤算法由于考慮了L型骨牌覆蓋的特殊性，因此在特殊方格測(cè)試上，只有初始狀態(tài)1次測(cè)試，通過L型骨牌覆蓋的子棋盤則無需再測(cè)試，因此測(cè)試特殊方格的次數(shù)不會(huì)隨著棋盤的不斷劃分而增大，測(cè)試次數(shù)見表2。

表2 不同算法測(cè)試特殊方格的次數(shù)對(duì)比

4 算法推廣與應(yīng)用

在一個(gè)ik×jk個(gè)方格組成的棋盤中，本算法依然可以利用類似L型骨牌覆蓋位置的特殊性，這個(gè)時(shí)候母棋盤是m=ik行與n=jk列，子棋盤有i×j個(gè)，利用分?jǐn)?shù)維的概念，我們把類似L型的大骨牌打碎成L型與O型(方形四格骨牌)或其他形狀的骨牌，然后覆蓋到子棋盤的每個(gè)頂點(diǎn)交叉的位置，把特殊方格安排在子棋盤的靠母棋盤重心均勻分布的子棋盤頂角上，進(jìn)而對(duì)有規(guī)律的子棋盤設(shè)計(jì)相應(yīng)的算法。

當(dāng)i=j=2時(shí)，我們用Xn表示第t次劃分子棋盤的總共覆蓋次數(shù)，則有以下的遞推公式：

Xt+1=Xt+(22-1)Xt，X0=1；

當(dāng)i=j不一定一樣大小時(shí)，覆蓋骨牌的種類就會(huì)多于一種，則有以下的遞推公式：

Xt+1=Xt+(i×j-1)Xt，X0=1。

圖6顯示了棋盤覆蓋算法用于圖像處理中。圖6的左面是原圖像，右面則是對(duì)原圖像加密后的圖像。

圖6 用棋盤覆蓋算法加密圖像效果

5 結(jié)語(yǔ)

與傳統(tǒng)的算法比較，分?jǐn)?shù)維改進(jìn)算法充分考慮了L型骨牌覆蓋棋盤的規(guī)律性，采用直接+間接遞歸及分治策略完成了長(zhǎng)方(包含正方形)棋盤所有方格的覆蓋，運(yùn)行效率得到了改善，運(yùn)行結(jié)果工整且對(duì)稱，便于快速生成二維圖像的加密秘鑰。

本文在闡述棋盤覆蓋問題的數(shù)學(xué)形式基礎(chǔ)上，找出了現(xiàn)有算法存在的不足，提出了改進(jìn)棋盤覆蓋算法的各模塊設(shè)計(jì)與實(shí)現(xiàn)方法，下一步工作重點(diǎn)是將改進(jìn)的算法用在實(shí)時(shí)圖像等技術(shù)領(lǐng)域。

[1] Mitchell A.A block decomposition algorithm for computing rook polynomials[EB/OL].(2017-07-28).http：//arxiv.org/PS_cache/math/pdf/0407/0407004.pdf.

[2] 郭燕莎，張大坤.棋盤多項(xiàng)式非遞歸生成算法的提出與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)與探索，2007，1(2)：200-206.

[3] 牛立新，王功明，李洪淇，等.棋陣多項(xiàng)式生成算法及其在禁位排列中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(10)：91-93.

[4] 吳文虎，王建德.組合數(shù)學(xué)的算法與程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，1998.

[5] xiaoge.基于棋盤覆蓋的文件加密方法[J/OL].[ 2013-09-11](2017-07-28).http：//www.jiamisoft.com/blog/6288-weiyunsuantuxiangjiamifangfa.html.

[6] 杜俊利，張景飛，黃心漢.基于視覺的象棋棋盤識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(34)：220-222.

[7] Stuart Bennett，Joan Lasenby.Chess-quick and robust detection of chess-board features[J].Computer Vision and Image Understanding，2014(18)：197-210.

[8] 馮躍峰.棋盤上的組合數(shù)學(xué)[M].上海：上海教育出版社，1998.

[9] 王曉東.計(jì)算算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社.2006

AFractionalImprovedDimensionalRectangularChessboardCoveringAlgorithm

WANG Hai-yan，et al.

(SchoolofComputerEngineering，SuqianCollege，SuqianJiangsu223800，China)

An improved and spread rectangular chessboard covering algorithm has been proposed based on a chessboard structure that included a special gridik×jk.By using the characteristics that the L domino always covers the intersection of sub-board without special grid，the algorithm to chessboard without special grid has been improved.Four modules functions are designed by adopting the combination idea of direct and indirect recursion and dividing-conquering strategy，takingi=j=2 as example.This algorithm can not only avoid the blindness of recursion solution to the sub-board without special grid，but also reduce the number of layers on recursion.The experimental results show that compared with the existing algorithms，this improved algorithm has better performance，which is more convenient for the generation of two-dimensional random keys that do not have the same row and column in the arbitrary shape image encryption process.

chessboard cover；divide and conquer strategy；directly recursive；indirect recursive；video encryption

10.3969/j.issn.1009-8984.2017.03.028

2017-08-02

江蘇省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201614160034H)宿遷學(xué)院教學(xué)改革研究項(xiàng)目(sqc2016jg10)

王海燕(1975-)，女(漢)，副教授，碩士 主要研究軟件工程，數(shù)據(jù)挖掘。

TP3

A

1009-8984(2017)03-0119-05