遍历列举俄罗斯方块的所有形状

以前玩俄罗斯方块的时候，就想过一个问题，为什么俄罗斯方块就这7种形状，还有没有别的形状？自己也在纸上画过，比划来比划去，确实就这几种形状。

继续思考一下，那假如是3个块组合的形状，有几种有效组合形式？

这个似乎不是太难，在纸上比划几下，应该能得出结果。

但是，如果是5个块组合起来，又有多少种有效的组合形式？

这就比较麻烦了，排列组合的可能性大增，不那么容易比划清楚。

从程序员的角度，这其实是一个遍历穷举的过程，所以有了这一篇文章。

首先也不搞太复杂的，先从3个块的组合开始尝试。

3个块的组合，考虑所有可能性，就是在3x3的一个区域里面，任意取点。然后添加一些限制条件，例如：

1，区域内点位不重复； 2，每个点都至少需要有一个相邻点； 3，平移不重复； 4，旋转不重复；

这4个条件是否充足了？

反正我开始时就是这么想的，认为充足了。当然，到后面遇到了问题，才又添加了一个限制条件。

为了能方便的判断结果是否正确，将有效结果展示出来，是有必要的。

需要界面展示，这里选择了使用QT，毕竟有可移植性，在windows下开发，以后要移植到linux下也可以。

看一下，基本的布局界面是这样的：

左上角，是那个画出方块组合形状的区域。在遍历过程中，遇到有效的方块组合，就在下面区域中以一半的宽高比例画出来。

这里由于涉及到了方块组合的不同大小的展示，以及还有平移动作，就需要考虑方块的点坐标，不能存储实际的宽高值（例如：0,20,40），而是更抽象的基础比例（例如：0,1,2）。

下面是简要介绍实现过程，具体实现可从文末的下载地址去获取。

先定义方块的类：

class Block

{

public:

QPoint leftUp;//左上角的坐标

int width;//宽度

int height;//高度

QColor penColor;//铅笔的颜色

QColor brushColor;//画刷的颜色

}

再定义一个方块组合的类：

class BlockGroup

{

public:

BlockGroup(int num);

int blockNum;//方块的数目

Block block[BLOCK_NUM];//方块的数组

int flagValid;//有效标志

};

穷举遍历的主要过程如下：

int pos[5];

int pointTotal=pow(curBlock.blockNum,2);//一个点可以选择的位置

int tryNum = pow(pointTotal,curBlock.blockNum);//每一个点，都有这么多种可能的位置，总的可能点位选择

while(tickNum

for(int i=0;i

//将一个大数，分解为几个部分，每部分给一个方块使用，用作坐标赋值

int pointLevel=pow(pointTotal,curBlock.blockNum-1-i);

pos[i]=(tickNum/pointLevel)%pointTotal;

}

//计算，寻找有效的方块组合

for(int j=0;j

curBlock.block[j].leftUp.setX((x+pos[j]/curBlock.blockNum)*w);

curBlock.block[j].leftUp.setY((y+pos[j]%curBlock.blockNum)*h);

curBlock.block[j].width = w;

curBlock.block[j].height = h;

curBlock.block[j].penColor = Qt::black;

curBlock.block[j].brushColor = Qt::yellow;

}

if(checkPosValid(&curBlock)!=1){//内部有点位重复，此种组合无效，跳过

tickNum+=1;

continue;

}

if(checkAdjacent(&curBlock)!=1){//检测每点都有相邻点，若不是，跳过

tickNum+=1;

continue;

}

if(checkConnectivity(&curBlock)!=1){//检测组块内部的连通性，若不是，跳过

tickNum+=1;

continue;

}

//规范坐标

adjustCoordinates(&curBlock);

int flagRepeat=0;

for(auto it=blockGroupList.begin();it!=blockGroupList.end();it++){

if(checkTranslationRepeatability(&(*it),&curBlock)){//发现是平移重复的

flagRepeat=1;

break;

}

if(checkRotaltionalRepeatability(&(*it),&curBlock)){//发现是旋转重复的

flagRepeat=1;

break;

}

}

if(flagRepeat==1){

tickNum+=1;

continue;

}

//新的有效方块组合，存入结果链表中

blockGroupList.push_back(curBlock);

//写文件

writeBlockInfo(&curBlock);

//设置标志，通知画出

flagFlush=1;

update();

break;

}

下面逐个展示循环里面调用的方法。

检查方块组合中的点位是否重复：

//检测块内点位是否有效（不能重复）

int BlockDialog::checkPosValid(BlockGroup *blockInfo){

for(int k=0;kblockNum-1;k++){

for(int i=k+1;iblockNum;i++){

if(blockInfo->block[k].leftUp==blockInfo->block[i].leftUp){

return 0;

}

}

}

return 1;

}

检查不是孤立点位：

//检测两点是否相邻

int BlockDialog::checkNearPoint(QPoint *point1,QPoint *point2,int w,int h){

QPoint pointRight=QPoint(w,0);

QPoint pointDown=QPoint(0,h);

if(*point1+pointRight == *point2){//右邻

return 1;

}

if(*point1 == *point2+pointRight){//左邻

return 1;

}

if(*point1+pointDown == *point2){//下邻

return 1;

}

if(*point1 == *point2+pointDown){//上邻

return 1;

}

return 0;//不相邻

}

//检测有相邻块

int BlockDialog::checkAdjacent(BlockGroup *blockInfo){

int isNearNum=0;

for(int i=0;iblockNum;i++){

isNearNum=0;

for(int k=0;kblockNum;k++){

if(k!=i){

if(1==checkNearPoint(&blockInfo->block[k].leftUp, &blockInfo->block[i].leftUp,

blockInfo->block[i].width,blockInfo->block[i].height)){

isNearNum++;

}

}

}

if(isNearNum==0){//没有相邻点

return 0;

}

}

return 1;

}

已经检查过不是孤立点了，为什么还要检查点的连通性（checkConnectivity）？

这就是前面说过的那个添加的限制条件。为什么呢？

前面列举了4个限制条件，在应用到3个方块组合时没有遇到问题，但是在穷举4个方块的组合的时候就遇到了问题，例如下面这种方块组合，竟然是满足条件的：

然而，这并不是我期望的形状，我希望所有方块都是相连通的。没有孤立方块，这个条件没有包含所有方块连通的要求，所以，还需要增加一个限制条件：

5，要保证所有方块是连通起来的。

如下代码是检测方法：

//检测块内连通性

int BlockDialog::checkConnectivity(BlockGroup *blockInfo){

int isNearNum=0;

//将块组各点位信息赋值到节点中

Node *nodeArray=new Node[blockInfo->blockNum];

for(int i=0;iblockNum;i++){

nodeArray[i].point = blockInfo->block[i].leftUp;

}

//设置相邻节点

for(int i=0;iblockNum;i++){

for(int j=0;jblockNum;j++){

if(i!=j){

setNearNode(&nodeArray[i],&nodeArray[j]);

}

}

}

//从节点0开始，进行遍历

DepthFirstSearch(&nodeArray[0]);

//检查是否有未遍历到的结点

for(int i=0;iblockNum;i++){

if(1==nodeArray[i].isChecked){

isNearNum++;

} else {

break;//有未走到的点，即组块有未连通部分

}

}

delete[] nodeArray;

if(isNearNum==blockInfo->blockNum){//完成遍历，即方块组是连通的

return 1;

}

return 0;

}

这里调用了一个函数 DepthFirstSearch() ，是深度优先搜索算法。

这里涉及到图的连通性，参考这个链接，讲得比较清楚： https://blog.csdn.net/weixin_44122303/article/details/122924246

//深度优先搜索--遍历相邻节点

void DepthFirstSearch(Node *node){

if(node==NULL){

return;

}

//递归调用，注意避免无限循环！

if(node->isChecked==1){//已经检查过的，不要再进行检查了，避免无限循环！

return;

}

//设置检查标志

node->isChecked=1;

//递归调用，检查相邻点

DepthFirstSearch(node->up);

DepthFirstSearch(node->down);

DepthFirstSearch(node->left);

DepthFirstSearch(node->right);

return ;

}

这里还有一个规范坐标的函数 adjustCoordinates(&curBlock); 为什么需要它？

也是在遇到问题之后才知道的。

在平移比较方块组合是否是重复的情况时，发现明明是一样的形状，却判断为不重复。

细细分析之后，发现是顺序不同，例如如下情况：

（0,1,2）与（0,2,1）

都是3个直线相邻的方块，但是由于顺序不同，直接按逐点比较的话，属于不同的组合。所以，添加一个规范点位顺序的方法：

//规范坐标

//1，左上平移;

//2，按顺序存放：从左上角开始，先第一排，从左往右；然后第二排

int BlockDialog::adjustCoordinates(BlockGroup *blockInfo){

//定位左上角方块的坐标

QPoint leftTopPoint1(0,0);

QPoint leftTopPoint2=getLeftTopBoundary(blockInfo);

//1，对整个方块组进行平移

int leftShift = leftTopPoint2.x()-leftTopPoint1.x();

int upShift = leftTopPoint2.y()-leftTopPoint1.y();

QPoint pointShift(leftShift,upShift);

Block blockTmp=Block();

list listBlock={};

for(int i=0;iblockNum;i++){

blockTmp.leftUp=blockInfo->block[i].leftUp-pointShift;

blockTmp.penColor=blockInfo->block[i].penColor;//进行块组的赋值，注意不能遗漏颜色属性

blockTmp.brushColor=blockInfo->block[i].brushColor;

listBlock.push_back(blockTmp);

}

//2，排序 -- 按什么顺序排列的？

//重载Block的比较操作符： 顺序定义：从左上角开始，先第一排，从左往右；然后第二排

listBlock.sort();

int blockPos=0;

for(auto it=listBlock.begin();it!=listBlock.end();it++){

blockInfo->block[blockPos]=*it;

blockPos++;

}

return 0;

}

这里的排序方法，依赖的是比较操作，先比较点位的纵坐标y，再比较横坐标x：

bool operator<(const Block& block1) const

{

if(this->leftUp.y()

return true;

} else if(this->leftUp.y()==block1.leftUp.y()){

if(this->leftUp.x()

return true;

}

}

return false;

}

再就是平移重复检测：

//检测平移重复性

int BlockDialog::checkTranslationRepeatability(BlockGroup *blockInfo1,BlockGroup *blockInfo2)

{

//逐点进行坐标比较

for(int i=0;iblockNum;i++){

if(blockInfo1->block[i].leftUp!=blockInfo2->block[i].leftUp){//坐标不同

return 0;

}

}

return 1;//重复

}

最后是旋转重复检查，比平移重复检测复杂一点的是，有3次旋转（90度、180度、270度）。还有一点是旋转后的坐标如何确定，好在我在坐标系上比划了一下，旋转90度，就是（x,y） -> (y,-x)，还是比较简单的：

//将方块组进行顺时针旋转90度

int BlockDialog::RotateBlockGroup(BlockGroup *blockInfo){

//1，对整个方块组进行顺时针旋转90度

Block blockTmp=Block();

list listBlock={};

for(int i=0;iblockNum;i++){

//旋转90度，就是（x,y） -> (y,-x)

blockTmp.leftUp.setX(blockInfo->block[i].leftUp.y());

blockTmp.leftUp.setY(0-blockInfo->block[i].leftUp.x());

blockTmp.penColor=blockInfo->block[i].penColor;//进行块组的赋值，注意不能遗漏颜色属性

blockTmp.brushColor=blockInfo->block[i].brushColor;

listBlock.push_back(blockTmp);

}

//2，排序 -- 按什么顺序排列的？

//重载Block的比较操作符： 顺序定义：从左上角开始，先第一排，从左往右；然后第二排

listBlock.sort();

//重新赋值

int blockPos=0;

for(auto it=listBlock.begin();it!=listBlock.end();it++){

blockInfo->block[blockPos]=*it;

blockPos++;

}

adjustCoordinates(blockInfo);//调整坐标，避免有负值坐标出现

return 0;

}

//检测旋转重复性

int BlockDialog::checkRotaltionalRepeatability(BlockGroup *blockInfo1,BlockGroup *blockInfo2)

{

for(int i=0;i<3;i++){//每次旋转90度，检查3次，加之前的一次平移检查，即完成了360度的检查

//1，对方块组旋转90度，就是（x,y） -> (y,-x)

RotateBlockGroup(blockInfo2);

//2，先进行平移检测

if(1==checkTranslationRepeatability(blockInfo1,blockInfo2)){

return 1;

}

}

return 0;

}

至此，就实现了循环遍历所有方块组合的主体功能。 然后，将相关信息写入文件即可。

完整的代码可在如下链接地址获取：

遍历列举俄罗斯方块的所有形状，基于qt实现的源码

修改代码中方块组合中方块的个数：

#define BLOCK_NUM 5 //4 //3 方块组内包含的方块个数

可以遍历获取不同个方块的组合类型。

最后，展示一下遍历后获得的3/4/5个方块组合的结果：