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

以前玩俄罗斯方块的时候，就想过一个问题，为什么俄罗斯方块就这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<tryNum){//遍历所有的可能性for(int i=0;i<curBlock.blockNum;i++){//将一个大数，分解为几个部分，每部分给一个方块使用，用作坐标赋值int pointLevel=pow(pointTotal,curBlock.blockNum-1-i);pos[i]=(tickNum/pointLevel)%pointTotal;}//计算，寻找有效的方块组合for(int j=0;j<curBlock.blockNum;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;k<blockInfo->blockNum-1;k++){for(int i=k+1;i<blockInfo->blockNum;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;i<blockInfo->blockNum;i++){isNearNum=0;for(int k=0;k<blockInfo->blockNum;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;i<blockInfo->blockNum;i++){nodeArray[i].point = blockInfo->block[i].leftUp;}//设置相邻节点for(int i=0;i<blockInfo->blockNum;i++){for(int j=0;j<blockInfo->blockNum;j++){if(i!=j){setNearNode(&nodeArray[i],&nodeArray[j]);}}}//从节点0开始，进行遍历DepthFirstSearch(&nodeArray[0]);//检查是否有未遍历到的结点for(int i=0;i<blockInfo->blockNum;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<Block> listBlock={};for(int i=0;i<blockInfo->blockNum;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()<block1.leftUp.y()){return true;} else if(this->leftUp.y()==block1.leftUp.y()){if(this->leftUp.x()<block1.leftUp.x()){return true;}}return false;}

再就是平移重复检测：

//检测平移重复性
int BlockDialog::checkTranslationRepeatability(BlockGroup *blockInfo1,BlockGroup *blockInfo2)
{//逐点进行坐标比较for(int i=0;i<blockInfo2->blockNum;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<Block> listBlock={};for(int i=0;i<blockInfo->blockNum;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;
}

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

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

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

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

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