六边形棋盘游戏组合最大得分计算优化方案问询

我正在做一款棋盘游戏的得分计算功能，问题可简化为以下规则：

• 六边形网格，部分tile被填充，部分未填充
• 直线填充tile按长度计分：{1:2, 2:5, 3:9, 4:13}，长度≥5无得分
• 长直线可拆分计分（如长度6计为4+2，总分18）
• 每个填充tile仅可计入一条直线
• 所有填充tile相互连通
• 最终得分为所有tile组合中的最大得分

示例说明 #

不同字母代表计入同一组的tile，空白tile未填充，下方标注各组得分与总分：

- 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

补充：游戏还有不限制直线的通用规则，也欢迎相关思路。

我已经琢磨很久了，发现问题难度远超预期，找不到有效降低计算复杂度的切入点：

• 单一直线的最大得分可以用贪心算法求得，但对全局最优帮助有限
• 目前想到的一个优化是：若当前已找到的最大得分高于某组合的理论最大值，则跳过该组合

原本以为贪心策略能全局适用，但存在反例：

- 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格直线加剩余部分的得分（27），低于选3组3格加1格的得分（29）。

目前我只能实现暴力算法：枚举所有4格直线组合（N选4的二项式系数），递归处理剩余tile；无4格时处理3格，直到1格（得分为数量×2），取所有组合的最大值。但tile数量较多时速度极慢，甚至会栈溢出。

请问有没有更高效的实现方案？

内容的提问来源于stack exchange，提问作者MrCelestis