俄罗斯方块拼图的多项式时间解决方案

Question

这是一个基于俄罗斯方块的谜题.在这个谜题中,我们将获得接下来将从顶部落下的n个片段的序列.我们的工作是在GameOver之前最大化得分.一般的俄罗斯方块没有多项式时间算法,但在这个难题中只允许I(直)四联体.虽然它不允许旋转它们.

所以这里是约束:

• 该板是W×H矩形
• 我们给出了下n个四联骨牌的序列
• 只允许我使用tetromino(水平或垂直)
• 不允许旋转
• 当行填满时,行会被清除
• 董事会最初是空的
• 每行清除1分.
• 当tetrominoes叠加到比赛场地的顶部时,游戏结束了.

找到可以获得的最高分数.

例:

8 x 6板.接下来的7个tetrominoes是[——,|,|,——,|,——,|]其中'——'表示水平我四氨基和|表示垂直我四氨基.

在这种情况下,最大可能得分是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:
........
........
........
........
........
....####

即使是我能想出的最好的算法也需要指数时间来保存当前电路板顶层的状态(即每列的高度).因此,该算法将花费O((H^W)*n)时间,因为对于每列,存在高度的H可能性.

可以使用动态编程或一些贪婪算法在多项式时间内解决这个问题吗？

Answer 1

我会尝试猜测：

棋盘是一个宽 x 高的二进制矩阵。

四格骨牌序列是长度为 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)内是否存在获胜序列。

如果您记住父指针的最佳猜测，那么您就有了获胜策略。

现在该算法是指数的，但您可以使用大小最多为 2^(W x H + 1) x W 的数据集来记忆递归。

从现在开始，我不知道如何计算记忆的呼叫数量。

评论：

• 在此版本中，您无法在从顶部坠落期间引导四格骨牌。

• 由于行擦除，递归中可能存在循环。您也许应该从您的问题中删除这条规则。

• 《俄罗斯方块很难，甚至难以近似》一文中的结论是，只有一个水平/垂直四格棋的俄罗斯方块是多项式时间。