摘要：“百變方塊”是一款深受大眾喜愛的益智游戲，而求解“百變方塊”是精確覆蓋的一種典型應(yīng)用案例。為求解“百變方塊”解集，該文深入研究了“百變方塊”的數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)了一種非回溯的有效算法，并用C#語言實(shí)現(xiàn)了該算法。

關(guān)鍵詞：百變方塊;精確覆蓋;回溯算法;非回溯算法

中圖分類號：TP302? ? ? ? ?文獻(xiàn)標(biāo)識碼：A? ? ? ? 文章編號：1009-3044（2018）35-0061-02

Abstract： Asa popular puzzle game， the solution of "Puzzle Squares " is a typical application case of Exactcover. In order to solve the solution set of " Puzzle Squares "， this paper deeply studies the data structure of " Puzzle Squares " and designs a non-backtracking effective algorithm， which is implemented in C# programming language.

Key words：Puzzle Squares;Exactcover; backtracking algorithm; non-backtracking algorithm

1 背景

“精確覆蓋”是指在一個(gè)全集X中若干子集的集合為S，求S的子集S*，滿足X的每一個(gè)元素在S*中恰好出現(xiàn)一次。在計(jì)算機(jī)科學(xué)中，“精確覆蓋”問題是指找出滿足要求的一種覆蓋，或證明其不存在[1]?！鞍僮兎綁K”是一款基于“精確覆蓋”問題的益智游戲，研究表明該問題一般可用回溯算法[2]求解。該游戲在6*6的單元表格中進(jìn)行，6*6的單元表格中有8個(gè)單元表格為某種預(yù)定圖形，如“上”字圖形（圖1），另外有8個(gè)拼塊（也稱“骨牌”）（圖2），要用8個(gè)拼塊覆蓋圖1中所有空格，每個(gè)拼塊用且只用1次。

該文要對“百變方塊”游戲進(jìn)行深入研究后用C#語言設(shè)計(jì)一種自動(dòng)求解算法，要求該算法有效且正確。

2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)可讓算法更加高效[3]。主要的數(shù)據(jù)結(jié)構(gòu)是8個(gè)整型數(shù)組，其中3個(gè)一維數(shù)組，5個(gè)二維數(shù)組：

1） int[] picPlace = new int[8]，拼塊放置標(biāo)識（最終位置索引），分為：Z形、T形、2W*2W形、L形、短L形、1W*2W形、1W*4W形、1W*3W形，初始值為-1;

2） int[] picStyleNo = new int[8]，下標(biāo)表示拼塊大類（如Z形為0），值表示相應(yīng)大類的形態(tài)編號，標(biāo)識當(dāng)前所用形態(tài)編號，（如T形有4種，其形態(tài)編號為0、1、2、3）;

3） int[，] computeArr = new int[6， 6]，該數(shù)組是自動(dòng)求解時(shí)是否可放拼塊的標(biāo)識，-1表示不可放，0表示可放，1表示已放;

4） int[，] picPointState = new int[27， 4]，在“百變方塊”中要使用的8個(gè)拼塊共有27種形態(tài)，每種形態(tài)用4個(gè)單元格表示其對應(yīng)點(diǎn)索引的相對增量，如Z形為0、1、7、8時(shí)表示若第0點(diǎn)在某個(gè)位置，則其他三點(diǎn)相應(yīng)增量為1、7、8;

5） int[，] picType = new int[8， 8]，拼塊對應(yīng)形態(tài)數(shù)組，每種拼塊最多有8種形態(tài)，最少有1種形態(tài)，其值對應(yīng)picPointState的索引;

6） int[，]picPointLocation = new int[8， 8]，標(biāo)識某種形態(tài)拼塊的放置位置，行下標(biāo)表示拼塊大類（如Z形為0），列下標(biāo)表示拼塊相應(yīng)大類的形態(tài)編號，值表示所放置的索引位置（行*6+列）;

7） int[] picPlaceStyle = new int[8]，答案數(shù)組，拼塊大類放置的對應(yīng)形態(tài)編號，和picPlace聯(lián)合使用，下標(biāo)表示拼塊大類（如Z形為0），值表示所放置的對應(yīng)形態(tài)編號picPointState;

8） int[，] picPlaceRecord = new int[8， 8]，用于標(biāo)識某拼塊某形態(tài)編號是否成功放置過。

3 算法設(shè)計(jì)

3.1 算法功能描述

把8個(gè)拼塊全部放置到空白表格中，每個(gè)拼塊用且只用1次同時(shí)使得空白表格完全覆蓋。

3.2 算法設(shè)計(jì)步驟

“百變方塊”自動(dòng)求解算法步驟如下：

1） i、j皆取值0;

2） 嘗試放置第i個(gè)拼塊的第j種形態(tài);

3） 放置成功執(zhí)行4），否則跳轉(zhuǎn)5）;

4） i為最后1個(gè)拼塊，跳轉(zhuǎn)9），否則i加1、j=0跳轉(zhuǎn)2）;

5） j為當(dāng)前拼塊的最后一形態(tài)則執(zhí)行6），否則j加1后執(zhí)行2）;

6） 若i為0跳轉(zhuǎn)8），若i不為0但沒有位置可放置執(zhí)行7），否則跳轉(zhuǎn)8）;

7） i減1、j=0改變其他位置嘗試;

8） 還有嘗試位置跳轉(zhuǎn)2），否則跳轉(zhuǎn)10）;

9） 保存解后改變嘗試位置，跳轉(zhuǎn)1）;

10） 退出。

3.3 算法核心代碼

“百變方塊”自動(dòng)求解算法源碼（C#）如下：

public string NonBackTrackAll（）{

while （iNo> -1） {

pFlag = 0;k = picStyleNo[iNo];

for （; k < 8; k++）{

if （rtFlag == 1）

if （iNo + 2 < 8） {

for （i = 0; i < 8; i++） picPointLocation[iNo + 2， i] = 0;

picStyleNo[iNo + 2] = 0; //此處取0表示k從0開始

}

if （picType[iNo， k] == -1） pFlag = 0; break; //跳出循環(huán)

i = picPointLocation[iNo， k] / 6; iTmp = i;

for （; i < 6; i++）{

j = picPointLocation[iNo， k] % 6;

if （rtFlag == 1）if （picPlaceRecord[iNo， k] ！= -1） j++;

if （i ！= iTmp）j = 0;

for （; j < 6; j++）{

iPSNo = picType[iNo， k];

if （CheckPointsIfCanPlace（iPSNo， i， j）） {

if （CheckPointsIfAway（iPSNo， i， j）） {

FlagPointsPlace（iPSNo， i， j）;

if （CheckIsolatedPoints（iPSNo， i， j） ！= -1）

CancelFlagPointsPlace（iPSNo， i， j）;

else{

picStyleNo[iNo] = k;

picPlaceStyle[iNo] = iPSNo;

picPointLocation[iNo， k] = i * 6 + j;

picPlace[iNo] = i * 6 + j;pFlag = 1;

picPlaceRecord[iNo， k] = i * 6 + j;

picTotal++;

if （picTotal == 8） {

string str1 = "";string str2 = "";

int t0;

for （t0 = 0; t0 < 8; t0++）{

str1 += picPlaceStyle[t0].ToString（） + "，";

str2 += picPlace[t0].ToString（） + "，";

}

gameAnswerData.Add（str1 + "-" + str2）;

str += str1 + "-" + str2 + "＼r＼n";

picTotal—;

CancelFlagPointsPlace（iPSNo， i， j）;

picPlace[iNo] = -1; pFlag = 0;

}

k = 8;i = 6;break;

} } }}}}

if （pFlag == 1） {

if （iNo + 1 < 8） {

for （i = 0; i < 8; i++）picPointLocation[iNo + 1， i] = 0;

picStyleNo[iNo + 1] = 0;

}

rtFlag = 0;iNo++;

}

else{

if （iNo> 0） {iPSNo = picType[iNo - 1， picStyleNo[iNo - 1]];

row = picPlace[iNo - 1] / 6; col = picPlace[iNo - 1] % 6;

CancelFlagPointsPlace（iPSNo， row， col）;

picPlace[iNo - 1] = 0; picTotal—; }

rtFlag = 1; iNo—;

}} return str; }

4 實(shí)例測試

利用該文算法進(jìn)行實(shí)例自動(dòng)求解應(yīng)用舉例如圖3：

由此可見，該算法是有效的;通過檢驗(yàn)該算法所給答案也是正確的。

參考文獻(xiàn)：

[1] 精確覆蓋問題[EB/OL].https：//baike.baidu.com/item/精確覆蓋問題/15668873.

[2] 姜華林.數(shù)獨(dú)問題高效算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2013，6（12）：82-83.

[3] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].2版.北京：清華大學(xué)出版社，2011.

[通聯(lián)編輯：謝媛媛]