计算六角形瓷砖组合的最大分数（棋盘游戏）

Question

作为一种爱好，我尝试实现棋盘游戏的得分计算。问题可以简化为以下简化形式：

• 有一个六角网格：有些瓷砖已填充，其他则未填充
• 分数是根据直线填充的图块数量给出的（按长度分数：{1:2, 2:5, 3:9, 4:13}，请注意，长度 5+ 没有分数）
• 线可能是相邻的（例如，如果你有一条长度为 6 的线，它仍然算作长度为 4 + 2 的线，总共 18 分）
• 填充的图块只能计数一次（只能属于一个已计数的行）
• 我们可以假设所有填充的图块都已连接
• 所得分数是填充图块所有可能组合的最高分数

示例（不同颜色代表一组数在一起的图块，上面是总分；白色图块未填充）：

  - A -
 - A B -
- A - B
 A C C B
A=13, B=9, C=5, total=27

  - A -
 - A B -
- A - B
 C C C B
A=B=C=9, total=27

  - A -
 - A C -
- A - B
 A D B E
A=13, B=5, C=D=E=2, total=24

附注该游戏还有一个更通用的规则，不限制填充的瓷砖形成一条直线。也许也有一些想法。

我想了很久，结果发现比我最初想象的要难。基本上我无法提出任何可以显着降低计算复杂性的假设。

一个明显的简化是，如果我们要计算一条直线的分数，贪心算法将始终给出它的最大分数（尽可能多地取4，然后取3，依此类推）。但在一般情况下并没有多大帮助。

另一个简单的改进是，如果当前最大产量大于组合的理论最大值，则根本不计算特定组合。

人们可能会认为贪婪路径总是可行的，但在某些情况下它不起作用，例如：

  - A B C
 - A B C
- - B -
 D B E -
A=5, B=13, C=5, D=E=2, total=27

  - A A A
 - B B B
- - D -
 C C C -
A=B=C=9, D=2, total=29

在这里挑选 4 块有余数的行将比挑选 3x3+1 获得更少的分数。

所以我最终只能使用强力算法，它在大型图块组上运行得非常慢，有时甚至会出现堆栈溢出。 IE。对于 N 个图块，枚举形成一条线的 4 个图块的所有组合（N 选择 4 = 二项式 = n!/(k!*(n-k)!)），对于每个图块，递归地对余数执行相同操作。如果没有 4，则选择 3，依此类推，直到达到 1，这会产生 NumberOfOnes*2 分数。选择所有组合中的最大值。

有更简单的方法吗？

Answer 1

想象一下，您正在按从上到下、从左到右的顺序考虑每个单元格，并决定如何对其进行计数。它要么没什么新意，要么是一排指向右侧、左下或右下的一定长度的行。它不能指向其他方向，因为那样的话就早就决定了。

在任何时候，您只能影响当前行和接下来 3 行中的单元格，并且您永远不必再次查看上面的行。这 4 行中已经“使用”的单元格模式以及当前的累积分数代表了您的完整状态。

并非所有已用单元格的模式都是可能的，因为第 2-4 行中的任何已用单元格都需要通过一条线连接到顶行中的单元格。配置可以表示为每个顶行单元的左下长度和右下长度的组合。每个顶行单元格有 17 种可行的组合。

解决问题的合理方法是从左上到右下进行。您将维护一个数组，该数组为当前 4 行中已用单元格的每种可能配置提供可达到的最佳分数。对于每个单元格，您必须在 O(possible_configurations) 时间内根据前一个单元格计算新数组。

要存储这些配置数组之一，您需要 17 个^row_length 插槽。这使得该算法适用于行长度高达 6 或 7 的情况。