基于精確覆蓋的應用算法研究

摘要：“百變方塊”是一款深受大眾喜愛的益智游戲，而求解“百變方塊”是精確覆蓋的一種典型應用案例。為求解“百變方塊”解集，該文深入研究了“百變方塊”的數據結構并設計了一種非回溯的有效算法，并用C#語言實現了該算法。

關鍵詞：百變方塊;精確覆蓋;回溯算法;非回溯算法

中圖分類號：TP302? ? ? ? ?文獻標識碼：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 背景

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

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

2 數據結構設計

精心設計的數據結構可讓算法更加高效[3]。主要的數據結構是8個整型數組，其中3個一維數組，5個二維數組：

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

2） int[] picStyleNo = new int[8]，下標表示拼塊大類（如Z形為0），值表示相應大類的形態編號，標識當前所用形態編號，（如T形有4種，其形態編號為0、1、2、3）;

3） int[，] computeArr = new int[6， 6]，該數組是自動求解時是否可放拼塊的標識，-1表示不可放，0表示可放，1表示已放;

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

5） int[，] picType = new int[8， 8]，拼塊對應形態數組，每種拼塊最多有8種形態，最少有1種形態，其值對應picPointState的索引;

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

7） int[] picPlaceStyle = new int[8]，答案數組，拼塊大類放置的對應形態編號，和picPlace聯合使用，下標表示拼塊大類（如Z形為0），值表示所放置的對應形態編號picPointState;

8） int[，] picPlaceRecord = new int[8， 8]，用于標識某拼塊某形態編號是否成功放置過。

3 算法設計

3.1 算法功能描述

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

3.2 算法設計步驟

“百變方塊”自動求解算法步驟如下：

1） i、j皆取值0;

2） 嘗試放置第i個拼塊的第j種形態;

3） 放置成功執行4），否則跳轉5）;

4） i為最后1個拼塊，跳轉9），否則i加1、j=0跳轉2）;

5） j為當前拼塊的最后一形態則執行6），否則j加1后執行2）;

6） 若i為0跳轉8），若i不為0但沒有位置可放置執行7），否則跳轉8）;

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

8） 還有嘗試位置跳轉2），否則跳轉10）;

9） 保存解后改變嘗試位置，跳轉1）;

10） 退出。

3.3 算法核心代碼

“百變方塊”自動求解算法源碼（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; //跳出循環

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 實例測試

利用該文算法進行實例自動求解應用舉例如圖3：

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

參考文獻：

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

[2] 姜華林.數獨問題高效算法的研究與實現[J].計算機光盤軟件與應用，2013，6（12）：82-83.

[3] 嚴蔚敏，吳偉民.數據結構[M].2版.北京：清華大學出版社，2011.

[通聯編輯：謝媛媛]