趣题研究：六边形网格的数字填充

不久前，知乎上看到这个问题^[1]：

在网站(https://matmod.ch/lpl/HTML/honeycomb.html)看到一个填字谜题，简单来说就是，一个正六边形，周围包裹一层同样的六边形，这样形成7个六边形，记这个图形为order = 2，如果再在外面包一层，那就有19个六边形，也就是order=3的图形，以此类推。

以order = 3为例，我们需要把1～19这19个数字放进这19个六边形里，使得每个格子一个数字不重复，每个数字都仅用到一次。可以看到每个格子都有一些相邻的六边形（定义有共同边的两个六边形格子是相邻的），我们希望每个格子与它的相邻格子数字的差的绝对值的最小值尽可能地大，记为D，类似 max min 问题，该怎么求解。

仿照网站思路，我建模成混合整数线性规划，但是这个问题似乎很难求解，目前只解出Order = 4的时候D = 10（一直没有算到最优，但是好像没有提升了），order = 5的情况，解20min只能算到 D=13，但是似乎有比这个更好的解（网站中有说 order = 5的时候，存在D = 18的解）

(上图：这个游戏的目标就是尽可能是相邻两个数字的差尽可能大。上图中，相邻两个数字差的最小值是10，所以它是o=4，d=10的一个解)

这种问题有没有什么加速求解的方法？或者在数学上有什么证明？或者有无参考链接？

作为一个IT从业者，看到这个问题的第一反应就是想编程解决。可以想象，这个问题用数值解法是很慢的，我的第一感觉是把它转换成图论中的寻找子图问题。思路如下：

把棋盘的形状抽象如下的图（以o=3为例），图中一共有19个点：

这种情况下，如果想找d=7的布局，那可以把数字0到18都抽象为一个点，并且如果两个数字之间的差大于等于7，则连一条线，可以得到如下这样一张图：

问题就变为从上面这张图中，找出一个如同棋盘形状的子图。感觉上这种方法要比数值规划法效率高。

于是，我上Github研究了一下，测试了三种找子图的工具：

RI^[2]，VEQ^[3]和Glasgow Subgraph Solver^[4]。

测试后证明，对我的问题，Glasgow的效率最高。使用Glasgow Subgraph Solver，可以在一分钟中内找出o=4,d=10时的解：

以及秒出o=5, d=14的解：

并且可以在半小时内，算出o=5，d=15的解。这些已经超出了题主的结果，然而这些似乎是以上方法的极限了。

我委托了一位网友，用其算力计算解o=4，d=11的情况，然而两周过去仍未出结果。我自己在云服务上尝试求解了o=15，d=18的情况，都在几天后因为内存用尽，程序被杀死。诚然可以用更大的云服务器进行求解，但我也不想因为求解这个问题而破产。

于是我在思考，为什么2008年（来源：https://matmod.ch/lpl/HTML/honeycomb.html）时，就有人能找出o=5和d=18的解？一定是有某种好的方法。某天晚上，我突发奇想：

现在我在求解o=5和d=18的情况是，先产生一张大图，其中所有两个数字的差大于等于18时有连线，然后从这张大图中寻找子图。但是生成大图时，为什么不规定一个差的上限呢？

原因是：在o=5时，数字范围是0到60。可以想象，如果要使全盘任意两个数字之差的最小值是18，那么任意两个数字之差的最大值也不会太大。比如0和60就不应该挨在一起，这样太“浪费”了。如果我们规定一个数字差的上限，大图中的连线数会变少，搜索结果就会更快。

这种思路听上去有点天真，但是事实上非常有效！通过压缩大图中的数字差的上限和连线数量，我很快找出了o=4,d=11的解（秒出）：

也秒出了o=5，d=18的解：

然后，似乎也再也不能提高了。于是o从2到5，我们似乎得到了以下一组最优的d:

于是，我想到了OEIS^[5]，这个在线数列数据库。我搜索了一下，"1,5,11,18"，发现这个问题^[6]原来早已被解决!

这道题最早出现在2008年，法国的一次数学和逻辑游戏比赛（Championnat International de Jeux Mathématiques et Logiques）中，以下是该题的正式答案，内容翻译自此^[7]：

国际数学与逻辑游戏锦标赛

2008年个人四分之一决赛

问题18 - Abella的蜂巢

Abella正在研究由相同的正六边形蜂房组成并自身形成正六边形的蜂巢。蜂巢的阶数对应于一边上的蜂房数量。蜂房从1到蜂巢内蜂房总数进行编号。

对于3阶蜂巢(见附图示例),Abella发现可以安排蜂房编号,使任意两个相邻蜂房的编号差至少为5,但对于6阶蜂巢这是不可能的。

在5阶蜂巢中,两个相邻蜂房的最大可能最小差值是多少?

解题步骤

1. 让我们制定一个策略来填充任意阶数蜂巢的数字。
2. 然后让我们展示给定的例子符合这个策略。
3. 接着让我们填充5阶蜂巢。
4. 最后,让我们计算所需的最小差值。

最终我们将得到任意阶数n的蜂巢的最大最小差值 的公式。

这个问题处理的是排列在三角形而不是六边形中的数字。红色、蓝色和绿色点位置上的三个数字之间的差值不应小于最小差值:

如果我们再添加一个点(例如在下方,标记为O),它与蓝点和绿点的差值也必须至少为这个最小差值。

与红点的差值无关。我们也可以将其涂成红色:

让我们继续处理5阶蜂巢的所有三角形。每个额外的点的颜色不能与三角形其他两个角的颜色相同:

(彩色虚线不代表三角形,仅连接相同颜色的点。)

因此我们有21个红点、21个蓝点和19个绿点,总共61个点。让我们将1到61的数字分成三组。

为了最大化不同组之间数字的平均差值,我们将21个最小的数字放入红色组,21个最大的数字放入蓝色组,其余19个放入绿色组:

为什么只创建三个组而不是更多?我们拥有的组越多,每个组就越小,各个组的数字之间的平均距离就越小!

此外,最好将所有组中较小的数字作为一个整体保持在一起,较大的数字也是如此。比如说,从左到右,从上到下。

所以我们得到 - 以线性、平行的方式排列(但暂时不考虑蜂巢结构本身) - 以下图片:

其中最小差值(标记为D)是18。在蜂巢本身中,垂直列将被分割(例如沿上图中的虚线),并可能相互错开,产生更小的D(减少1)。每当我们在阶数n中将因子k增加1时,当n=3·k+2时,这种错开和减少1的情况就会发生。

让我们填充并检查三个组的所有3!=6种排列,看其最小D值。

上面的变体产生了18的最小差值(用V标记)。其他一些只产生17或更小的最小值。

稍微旋转最初呈现的蜂巢,我们发现完全相同的模式(左右两侧镜像;最小差值为5;组大小为6、7和6,总共19个蜂房):

现在让我们处理公式。

阶蜂巢的总蜂房数是 ,

最小组包含不超过 个蜂房,这也是最大可能的最小差值 :

考虑到 随 中的k线性减少,我们得到

修正项 是从离散阶数得出的,比如 ,我们已经发现 :

由此得出c=1。

这个 对 有效。

可以找到类似的公式用于 和 :

和

连同

我们可以写成

n的前几个值的表格:

更多值请参见OEIS序列A240438!

对于一个"完美"的OEIS序列,我们希望从n=1开始。上述公式给出Δ(1)=0,这个值可以用作单个蜂房蜂巢的定义(如0!=1)。但对于那些数学共识说"不行!"的人,我们从n=2开始这个序列。

以上就是我关于这个问题的历时几周的研究。虽然我没有作出什么新的发现，但是整个过程还是非常有收获的。特别是关于子图搜索工具的使用，我相信将来也会在其他问题中发挥作用。