自定义棋子的最大总价值

IBM Ponder This #066 · 2003 年 10 月

本题由 Norbert Sepp、Kalman Sallai 和 Gyozo Nagy 提议，与 2003 年 8 月的棋子问题有关。

用一个 15×15 的“攻击矩阵”定义一种新棋子：把棋子放在中心，矩阵中的 1 表示它会攻击对应相对位置，0 表示不会。下面是传统车的矩阵：

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 R 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

在 8×8 棋盘上判断攻击时，把矩阵中心对准棋子所在格，查看目标格的对应值。因此攻击能力只依赖相对位移，不依赖绝对位置。225 个矩阵元素中中心无关紧要，其余可任选 0 或 1，因而共有 2^224 种棋子。

若某类棋子最多能在 8×8 棋盘上放下 k 个且互不攻击，就给每个该类棋子赋值 1/k。你的目标是定义多种棋子并混合摆放，使所有棋子互不攻击，总价值尽可能大。

例如，棋子 F 的矩阵为：

0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 F 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1

它攻击右侧任意列，以及本列上方的所有位置，所以两枚 F 无法共存，每枚价值为 1。类似地定义 G：

1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 G 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

G 的价值也为 1。如下摆放含一枚 F、一枚 G 和六个车，总价值为 2.75=6/8+1+1：

G 0 0 0 0 0 0 0
0 R 0 0 0 0 0 0
0 0 R 0 0 0 0 0
0 0 0 R 0 0 0 0
0 0 0 0 R 0 0 0
0 0 0 0 0 R 0 0
0 0 0 0 0 0 R 0
0 0 0 0 0 0 0 F

可把空格记作 0，把价值为 1/k 的棋子记作整数 k，将上述棋盘简写为：

1 0 0 0 0 0 0 0
0 8 0 0 0 0 0 0
0 0 8 0 0 0 0 0
0 0 0 8 0 0 0 0
0 0 0 0 8 0 0 0
0 0 0 0 0 8 0 0
0 0 0 0 0 0 8 0
0 0 0 0 0 0 0 1

任务：构造总价值超过 20 的棋子集合及摆放。按这种格式给出总价值与 8×8 整数数组即可；原题要求投稿不附攻击矩阵或附件。官方会记录超过 20 的构造，并跟踪最高总价值。

解答

认真尝试后再打开

待补充。

IBM Ponder This #066 · 2003 年 10 月 ​

IBM Ponder This #066 · 2003 年 10 月