俄罗斯方块可以永无止境地玩下去吗？

大师在玩俄罗斯方块的时辰有没有想过这样一个问题：若是玩家足够牛B的话，是不是永远也不成能玩死？

换句话说，假设你是万恶的游戏机，你筹算害死你面前的玩家；你知道肆意时刻游戏的状况，并可以有针对性地给出一些较着不合适的方块，尽量迫使玩家面临最坏环境。

那么，你有没有一种算法能包管害死玩家，或者玩家无论若何都存在一种必胜策略呢？

注重，俄罗斯方块的游戏区域是一个宽为10，高为20的矩形，而且玩家可以预先看到下一个给出的方块是什么。在设计策略时，你必需考虑到这一点。

相信良多人有过这样的履历：玩俄罗斯方块时一开局就给你一个“S”型方块，让完美本家儿义者感应异常别扭；成果，第二个方块仍是这个“S”，第三个方块依旧是“S”，半斤八两令人解体。于是，我们起头猜测，若是游戏机给你无限个“S”形方块，玩家是不是就没有解了？谜底是否认的。如图1，从第10步起头，整个场合排场发生一个轮回；只要机械给的一向都是“S”方块，玩家可以不竭反复这几个步调，包管永远也死不了。

不外，这个轮回是在游戏场地清空了的环境下才发生的。有人会进一步想了，如果在玩着玩着，看着你场面地步欠好时俄然给你无限多个“S”方块呢？事实上，此时场合排场的轮回依然可能存在，如图2。在第5个“S”形方块落地后，轮回再次发生。

俄罗斯方块真的不成能玩死吗？1988年，John Brzustowski的一篇论文指出，俄罗斯方块游戏无解并非不成能。它给出了一种算法可以包管游戏机可以或许害死玩家，即使我们要求它必需提前标的目的玩家展示出下一个方块的外形。机关的关头在于，整个游戏的场合排场个数是有限的（2的200次方），若是玩家一向不死，在某一时刻必然会反复某一状况。我们把两次反复状况及其之间的游戏过程叫做一个“轮回”，这个轮回现实影响到的那些行就叫做“现实轮回区”。例如，图2就是一个轮回，这个轮回的“现实轮回区”是从第4行到第7行这四行。

我们把宽为10的游戏区域划分为5个宽为2的“通道”，从左至右用1到5标号。注重到图1和图2中的两个轮回都有一个配合点：每个“S”形方块最终都完全落在某个通道内。事实上，对于肆意一个只有“S”形方块的轮回，我们都有这个结论。也就是说，若是游戏机一向给你“S”形的方块，你却用它们弄出了一个轮回，那只有一种可能：所有“S”形方块的下落位置都没有跨越通道（就像图3中的紫色方块那样，而非绿色方块那样）。

为了证实这一点，我们对通道编号施归纳。令命题P(x)暗示，若是某个“S”形方块（或它的此中一部门）落在了通道x的左边，那它必然完全落在某个通道内。P(1)显然当作立：方块底子不成能占有通道1左边的某个格子，因为通道1左边啥都没有。下面我们申明，当P(n)为真时，P(n+1)也为真。

我们起首要证实一个引理：在轮回中的肆意时刻，通道n的现实轮回区内绝对不成能呈现形如“□■”的两个并排的格子。如图4.1，假设图中星号方块地点行是通道n的现实轮回区内位置最低的“□■”的布局。假如这一行被消失落了，又由归纳假设，不存在哪个“S”形方块跨越了该通道的左鸿沟，是以只有一种可能：某个“S”形方块从左侧面挤了进来（如图4.2）。但这样一来，我们又发生了一个更低的“□■”，矛盾。这就是说，星号方块地点行一向没被消去。但这也是不成能的，因为现实轮回区内是一个新陈代谢、以旧换新的更替过程，每一行最后都是会被消弭的。

接下来，考虑命题P(n+1)。要想让“S”形方块占有通道n的格子，只有图5这四种环境。可是，因为我们之前证实了通道n中不克不及存在“□■”，是以在这个“S”形方块落下之前，星号方块都是已经有了的了。注重到，每一个“S”形方块的下落都致使“■□”形布局的削减，但第一种景象除外——它消弭了一个“■□”形布局，但在其上方带来了一个新的，使得“■□”形布局个数连结不变。没有哪种景象可以或许增添“■□”的个数。可是，通道n的“■□”形布局个数应该是恒心猿意马的，因为它在一个轮回区里。是以，只有第一种环境才可以或许被接管。

是以，仅含有“S”形方块的轮回只有一种环境——“S”形方块在各个通道内重叠，填满并消弭若干行后回到初始状况。现实轮回区内的每个通道都是一个模样：底下是0个或多个“■■”，顶部一个“■□”。注重，最右侧那个通道的最顶端是一个“■□”，右边这个空白一辈子也不成能用“Z”形方块填上。也就是说，在一个只含“S”形方块的轮回区内，必然会有某一行，它的最右侧是一个“■□”，它包管了该行不克不及仅用“Z”形方块消失落。如图6所示，箭头所指的行无法单用“Z”形方块消弭，因为星号位置不成能用“Z”形方块填充。

下面我们给出游戏机害死人的算法：

1. 不竭给出“S”形方块并显示下一个方块也为“S”，直到呈现一个轮回；

2. 给一个“S”形方块并显示下一个方块为“Z”；

3. 不竭给出“Z”形方块并显示下一个方块也为“Z”，直到呈现一个轮回；

4. 给一个“Z”形方块并显示下一个方块为“S”；

5. 跳回1并反复执行。

这样的话，玩家为什么会无解呢？由上面的结论，在第1步后，游戏区域中呈现了一个不克不及用“Z”消弭的行。即使再给你一个“S”形方块，这一点仍然无法拯救，因为填充星号空格的独一路子就是插一个“S”进去，但这当即又发生了一个“Z”永远放不进去的空位。然后，玩家就拿到了一大堆“Z”，最终必然会发生另一个轮回，且这个轮回区在适才那个无法消去的行之上（轮回区不成能包含一个不克不及消弭的行，因为正如前面所说，一个现实轮回区的所有行最终都是会被消失落的，这样才可能轮回）。这个轮回区的最左边那个通道将会发生一个“□■”布局，是“S”所不克不及消去的。于是，游戏机又给出一大堆的“S”，最终使得两种无法消去的行瓜代呈现，直至Game Over。

有两点值得注重。一、固然我们这里假设游戏机是有本家儿不雅能动性的，但事实上呢，即使方块是随机出的，若是你足够不利的话，这个特别的方块序列可能刚好就让你一个不错地碰上了；固然这种怪事的发生概率极低，但理论上说仍然是可能的，是以俄罗斯方块毕竟不是玩不死的，总有一个时辰会Game Over。二、这个结论可以直接扩展参加地为肆意宽度的俄罗斯方块游戏。就地地宽为偶数时，上述证实同样有用；就地地宽为奇数时，无限多个方形方块就可以直接干失落玩家。