基于精确覆盖的应用算法研究

摘要：“百变方块”是一款深受大众喜爱的益智游戏，而求解“百变方块”是精确覆盖的一种典型应用案例。为求解“百变方块”解集，该文深入研究了“百变方块”的数据结构并设计了一种非回溯的有效算法，并用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.

[通联编辑：谢媛媛]