最大化董事会得分

Question

棋盘是一个简单的 31 x 31 棋盘格。

• 每个方格上最多可以放置一个棋子（所以技术上最多可以放置 961 个棋子）
• 棋子授予 [16 - taxicab_distance_from_middle_square] 分（不能低于 0 分）
• 但是每块棋子失去其得分的 1/24 乘以以该棋子为中心的 5 x 5 正方形内的所有其他棋子
  • 所以完全包围的棋子完全没有分数
  • 被其他 12 个棋子包围的棋子恰好获得原始分数的一半
• 目标当然是找到得分最高的棋子排列方式

我试过运行一个程序，一次把一个棋子放在任何地方，会给出最高分，但由于每次放置都会影响其他棋子的分数，结果显然是不均匀的接近最优。

找到（或至少接近）得分最高的棋盘状态的最佳方法是什么？

Answer 1

好的解决方案似乎具有一种有趣的结构。这是一个值为 879.25 的解决方案：

0000000000000001000000000000000
0000000000000011100000000000000
0000000000000001000000000000000
0000000000001001001000000000000
0000000000011111111100000000000
0000000000001001001000000000000
0000000000000000000000000000000
0000000011111111111111100000000
0000000111111111111111110000000
0000000000000000000000000000000
0000000000000000000000000000000
0000111111111111111111111110000
0001111111111111111111111111000
0000000000000000000000000000000
0000000000000000000000000000000
1111111111111111111111111111111
0111111111111111111111111111110
0000000000000000000000000000000
0000000000000000000000000000000
0000111111111111111111111110000
0000011111111111111111111100000
0000000000000000000000000000000
0000000000000000000000000000000
0000000011111111111111100000000
0000000001111111111111000000000
0000000000000000000000000000000
0000000000001001001000000000000
0000000000001111111000000000000
0000000000000011000000000000000
0000000000000001000000000000000
0000000000000001000000000000000

我通过模拟退火找到了这个解，以及它的 7 次旋转和反射。

如果你 "guess" 中间的那一堆行如上，你会在所述一堆行的上方和下方得到可管理的小子问题。例如，您可以通过动态规划找到这些子问题的最优解。