Tetris难题的多项式时间解决方案

Question

这是一个基于俄罗斯方块的难题。在这个难题中，我们会得到下降的n个方块序列，我们的任务是在GameOver之前最大化得分。对于一般俄罗斯方块问题没有已知的多项式时间算法，但是在这个难题中只允许I型（直线型）方块，不能旋转。

以下是限制条件：

• 棋盘是W x H的矩形
• 我们得到接下来n个方块的序列
• 只有I型方块（水平或垂直）被允许
• 无法旋转方块
• 当行被填满时就会被清除
• 棋盘最初是空的
• 每行清除获得1分
• 当方块堆叠到游戏区域顶部时，游戏结束

找出可以获得的最高分数。

例子：

8 x 6的棋盘。下一个7个方块为[——,|,|,——,|,——,|]，其中'——'表示水平的I型方块，'|'表示垂直的I型方块。

在这种情况下，最大可能得分为3，使用以下策略（'.'表示空棋盘，'#'表示方块的一部分）。

Initially:
........
........
........
........
........
........
1st move:
........
........
........
........
........
####....
2nd Move:
........
........
.......#
.......#
.......#
####...#
3rd Move:
........
........
......##
......##
......##
####..##
4th Move:
........
........
......##
......##
####..##
####..##
5th Move:
........
........
.....###
.....###
####.###
####.###
6th Move:
........
........
.....###
####.###
####.###
####.###
7th Move:
........
........
....####
########
########
########  // bottom 3 rows are cleared so score is 3
final state:
........
........
........
........
........
....####

即使是我能想出的最好的算法，在保存当前棋盘顶层状态（即每列的高度）时，所需时间也是指数级别的。因此，由于对于每一列高度都有H种可能性，这个算法将需要O((H^W)*n)的时间。

是否可以使用动态规划或贪心算法在多项式时间内解决这个问题？

- xashru

---

这可能是你的作业吗？ - Gene

对我来说可能有点晚了：左侧叠加水平的I字形图案，右侧叠加垂直的I字形图案，可以在例子中得到三个清空的行，并开始使用贪婪启发式算法。 - greybeard

启发式方法可能会奏效，因为问题相对简单。您需要根据棋盘的大小设计一组规则（例如，如果非常宽，请将“ - - ”并排放置；如果不是，则将其堆叠在一起）。 - Joaquin Rocco

解决方案是否允许将棋子侧向引导到由于悬挂而从顶部无法访问的板孔中？例如，在具有棋子序列“||-|||”的5宽度板上，您必须使用“-”创建悬挂，然后将后面的“|”移动到其下方，如果要清除4行（而不是1或0）。 - Craig Gidney

你能展示一下你目前的指数时间算法吗？ - Ortomala Lokni

Answer 1

我猜测：

该棋盘是一个W x H的二进制矩阵。

俄罗斯方块的序列是一个长度为n的二进制字符串s，1代表竖着放，0代表横着放。

让我们尝试决策问题：给定任意棋盘和任意长度为n的俄罗斯方块序列s，是否存在获胜的移动序列？

在每一步中，你最多可以做W个选择：俄罗斯方块的位置。

为了检查对于给定的棋盘和俄罗斯方块序列是否存在获胜的移动序列，请使用以下算法检查CanWin(B(n)):

 CanWin(B(i)):
   if Filled(B(i)) return false
   if (i == n and not Filled(B(i))) return true
   choose position in 0..W-1
   B(i+1) = UpdateBoard(Bi, s(i+1), position)
   return CanWin(B(i+1))

通过检查顶行，您可以在O（W）内检查板是否填满。您可以通过在O（H）中检查碰撞来更新板。[需要考虑行抹除] 然后，您可以在O（nW（H）^ W）中决定是否存在获胜序列。

如果您记住了哪个猜测是最好的，并带有父指针，那么您就有了获胜策略。

现在算法是指数级的，但是您可以使用数据集对递归进行memoized，其大小最多为2 ^（W x H + 1）x W。

从现在开始，我不知道如何计算备忘录调用次数。

备注：

• 在这个版本中，你不能指导方块从顶部下落。

• 由于行消除可能会导致递归中出现循环。你可能需要将此规则从问题中移除。

• 文章Tetris is Hard, Even to Approximate的结论推测，只有一个水平/垂直方块的俄罗斯方块是多项式时间。

- Ortomala Lokni

Answer 2

我无法想象怎么能比指数时间复杂度更快地完成。一些想法：

游戏在以下任何情况下结束：已放置n个方块，或者已放置的方块超过失败级别。

可能有一种解决方案比指数时间更快。由于累积分数的唯一方法是清除行，而且每次清除多少行都只得1分，因此可能存在多种解决方案。如果放置了n个方块后棋盘上没有剩余方块，则不存在更高得分的解决方案（以较少的步数结束不会获得额外的奖励分）。在最好的情况下，可以在线性时间内找到解决方案（放置n个方块），最坏的情况是指数时间复杂度。

显然，我们可以采用技巧或模式来加速。例如，如果x个方块被证明可以清空棋盘，则如果x整除n，我们就有了一个解决方案。

- Emmett Casey