晶胞构造求解五子连珠问题

Crystal Cell Structure for Solving the Pentagram Problem

摘要: 五子连珠问题由五子棋抽象而来，类比晶体学中晶体的成核与生长过程，运用回溯法求出所有最佳晶胞，基于棋盘空间分解与不同维度晶胞的生长，得出最少放置数的求解公式，给出数学证明，同时快速给出所有最优放置，具有运算速度快、结果全面的优点。

Abstract: The five-sub-alignment problem comes from the abstraction of gobang. Analogize the nucleation and growth process of crystals in crystallography. The backtracking method is used to find all the best cells. Based on the spatial decomposition of the chessboard and the growth of cells in different dimensions, the formula for solving the minimum number of placements is obtained. At the same time, give all the optimal places quickly, which has the advantages of fast calculation speed and comprehensive results.

1. 引言

五子连珠问题是基于五子抽象棋演变而来 [1]，规则为在一个棋盘上放置最少的黑子，使得其余方格均放置白子时不能五子连珠，连珠规则同五子棋。晶胞是构成晶体最基本的几何单元，保留了整个晶格的所有特征，能完整反映晶体内部的化学结构特征的最小单元 [2]。

五子连珠问题首先出现在年全国高中数学联赛，目前的研究主要可以分为两类。第一类偏向于对问题的分析研究：丁龙云在“五子棋”到“马步跳”中首先运用了马步跳法 [3] 的规律进行解的构造，类似于H.D. Shapiro在广义拉丁方在环面上中构造正则解 [4] 的一种方法，随后方泓堃 [5] 在避免五子连珠的分析与建模中给出了一种马步跳法则，结合分割法建立了避免五子连珠的模型，从规律的角度描述问题，但分割法使用有待改进；贺子鹏等在五子连珠问题最少取法的探讨中研究了五子循环体 [6]，论证了可以运用循环体的性质对网格平面进行叠加处理；院旺在消除五子连珠情况的策略研究中从算法设计角度运用了分治法 [7] 很好地得出了最少放置数，至此分割法得到了改进，但没有从理论的角度研究本问题，结果缺乏论证。另一类偏向普适性的算法：许友军 [8] 在棋盘设计五子连珠求解中通过逻辑推理，运用回溯法和0-1规划求解此类问题；吴亚东等在基于0-1规划 [9] 的五连珠问题求解中运用了0-1规划解决了五子连珠问题，同时提出了有效晶胞 [1] 生长模型，利用发现的一种特殊的规律进行求解，此类方法易于理解，但求解复杂度过高，难以应对本问题中稍大棋盘的求解。

本文结合以上两类方法并对放置方法进行了研究，首先类比化学领域在空间点阵选取得到晶胞的方法，借鉴吴亚东发现的有效晶胞定义最佳晶胞，将最佳晶胞等价到模n皇后问题 [10] 并探寻其本质特征，从而初步构建了最佳晶胞的理论体系，并运用回溯法求出所有5阶最佳晶胞；再对于晶胞生长策略运用分割法，将棋盘划分为不同维度的生长区和可变生长区，按照最优性合成原理，找到所有区域最优解，据此合成本问题的最优解，然后根据可变生长区求出可变矩阵，最后将方法求解表述为一个公式，可直接求出所需最少放置数，并通过反证法证明了公式的正确性；最后通过可变矩阵放置数要求，通过在最佳晶胞内的搜索，逆推求出所有可能的最优放置。此模型避免了第两类方法的缺点，在理论上又高于第一类方法，优势在于理论性强、计算速度快、拓展性强和结果全面，对于后续研究做了很好的铺垫。

2. 最佳晶胞的寻找

吴亚东在基于0-1规划的五连珠问题求解中已经给出了有效晶胞的模型，并运用0-1规划发现了一种有效晶胞，给出了一维和二维晶胞的模型，本文将有效晶胞称为最佳晶胞。

2.1. 最佳晶胞的定义

2.1.1. 最佳晶胞的构造原则

在五子连珠问题的研究中，有很多学者运用了一些好的方法，在总结前人的基础上给出最佳晶胞构造的三点原则：

1) 最优原则：每5个位置有且仅有一个黑子，根据抽屉原理(鸽笼原理) 5 × 5的棋盘至少需要5个黑子，最佳晶胞取最少。

2) 生长原则：除晶胞内不能连珠外，晶胞沿任意方向生长也满足不连珠要求，棋盘上表示为晶胞的对角线不能n连珠，如图1、图2所示：

Figure 1. A condition to be satisfied for optimal cell growth

图1. 最佳晶胞生长时需满足的一个条件

Figure 2. Transformation of conditions

图2. 条件的转化

3) 循环体原则：最佳晶胞是一个循环体 [6]，如图3所示：

Figure 3. Optimal cell spatial folding [1]

图3. 最佳晶胞的空间折叠 [1]

2.1.2. 最佳晶胞的代数定义 [11]

以二维最佳晶胞为例，记整数集合 $A=\left\{1,2,\cdots ,N\right\}$。A的笛卡尔乘积记为B，即 $B=A\times A=\langle \left(1,1\right),\left(1,2\right),\cdots ,\left(1,N-1\right),\left(N,1\right),\left(N,2\right),\cdots ,\left(N,1\right),\cdots ,\left(N,N\right)\rangle$。从集合B中选择N个元素组成集合C，若C的笛卡尔乘积C × C中的每一个元素(I_k, J_k)，(I_g, J_g)，能满足以下的所有条件：

1) I_k ≠ I_g {不在同一列上}；

2) J_k ≠ J_g {不在同一行上}；

3) I_k + J_k ≠ I_g + J_g ± N {不在同一对角线及互补对角线上}；

4) I_k − J_k ≠ I_g − J_g ± N {不在同一对角线及互补对角线上}。

2.1.3. 最佳晶胞与模N皇后问题的等价性

二维棋盘下，对于任意5 × 5的区域，横、竖、主对角线、副对角线及其互补对角线共4 × 5个条件需满足，一个棋子最多能满足4个条件，故不存在某个条件未被满足也不存在某两个个黑子重叠满足同一个条件，可以说明最佳晶胞每行、列和互补对角线有且仅有一个黑子。

Le，Li and Wang在文章也证明到：如果n ≥ 4且n ≥ k ≥ 1，那么对于n × n的棋盘，我们能够放置kn个皇后在棋盘上，使每一行有k个皇后，每列有k个皇后，每条对角线上最多有k个皇后 [12]。即将连珠问题转化为不冲突问题，n阶最佳晶胞等价为模n皇后问题。

2.2. 最佳晶胞的寻找与分类

存在性定理(Pólya)：当n × n的模n皇后有解当且仅当gcd(n, 6) = 1 [10]。

基于现有对n皇后问题的研究，由gcd(5, 6) = 1知五阶最佳晶胞存在，要找到所有最佳晶胞应借助回溯法 [13]，得出所有的2维5阶共十种，按行由左到右分别编号1~10，见图4。

Figure 4. Ten best cell types for n = 5

图4. n = 5的十种最佳晶胞

2.3. 最佳晶胞的分类

借鉴基础解 [11] 在求解n皇后问题的运用，将一个最佳晶胞通过循环体变换、旋转变换 [11]、对称变换 [11] 和纸面内外变换得到的晶胞归为一类，由于此处十种晶胞的一种只需经过循环体的行变换和上下对称变换即可得到所有晶胞，故只定义以下两种变换H₁，S₁作为基础变换 [11]，同时取一种最佳晶胞作为代表晶胞，用于求解放置。

1) 循环体变换

运用循环体原则，将最佳晶胞第一列变换到最后一列记作H₁，对应有H₂、H₃、H₄、H₅，则H_k (k = 1~5)对于一个放置(x, y)产生的新放置坐标为 $\left(\left(x+k\right)\mathrm{mod}5,y\right)$，实际上 $H_k=H_1^k$，为表示形象依然使用H_k。

2) 对称变换 [11]

最佳晶胞沿某条直线对称依然能保持原有性质，变换S₁ (上下对称)，新坐标为 $\left(x,\left(9-y\right)\mathrm{mod}5\right)$。

最后将此处10种归为一类。如图4所展示10的种最佳晶胞，第一行的五种第一行与第五行相接为结果相同，上下两行为对称关系，本文取第1种为这类晶胞的一个代表元，可以表示为表1所示的变换运算：

Table 1. Optimal cell transformation operation

表1. 最佳晶胞变换运算

3. 最佳晶胞求解五子连珠问题

求解五子连珠普遍的方法是回溯法与0-1规划，但这两种方法求解复杂度高，对于棋盘空间较大时无法有效求解，且0-1规划每次只能给出一种放置，但运用最佳晶胞与棋盘分割能够有效克服以上不足。

3.1. 分割法运用 [3] [8]

对于N × M大小棋盘下，根据N，M模5的结果： $\{\begin{array}{l}a=\left[\frac{N}{5}\right]\hfill \\ b=\left[\frac{M}{5}\right]\hfill \\ a_1=N\%5\hfill \\ b_1=M\%5\hfill \end{array}$，将棋盘分割为三大块：

$\{\begin{array}{l}a\times bA区\left(二维晶胞生长区\right)\hfill \\ a\times b_1+a_1\times bB区\left(一维晶胞生长区\right)\hfill \\ a_1\times b_{1}C区\left(可变生长区\right)\hfill \end{array}$

其中：A区可看作ab个二维最优晶胞，需放置黑子5ab。

B区有a₁b + b₁a个一维晶胞，需黑子a₁b + b₁a。

C区为可挑选生长，可以通过A区最佳晶胞的变换选择生长出二维晶胞的任意部分，如图5、图6展示的选取不同晶胞进行生长所带来C区结果的差异。

3.2. 可变矩阵求解

运用不同最佳晶胞进行生长不一定能得出最优解，但可以在最佳晶胞中搜索求出对1 × 2的C区最少需0个黑棋，得最优解为8，故综上求出0~4 × 0~4的最优解，得出C区生长i行j列所需最少棋子的可变矩阵：

Figure 5. Example of a 6 × 7 chessboard division

图5. 6 × 7棋盘分割法示例

Figure 6. The other one grows better

图6. 另一种更优生长

$A\left(i,j\right)=\left(\begin{array}{ccccc}0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 0& 1& 1& 2\\ 0& 0& 1& 2& 3\end{array}\right)$

3.3. 得出计算公式

根据A、B、C区三个区都达到最优，合成本问题的最优放置，可得出此类N × M棋盘五子连珠问题公式：

$X=5ab+a_{1}b+b_{1}a+A\left(a_1,b_2\right)$

可以检验可变矩阵满足 [8]：

$A\left(i,j\right)=\left[\frac{i\times j}{5}\right]$

将计算公式简化为：

$X=\left[\frac{M\times N}{5}\right]$

公理：若一个优化问题的最小值为x，则增加约束后的新的约束问题的最小值 $y\ge x$

证明1：五子连珠问题最少放置数 $X\left(M,N,5\right)=\left[\frac{M\times N}{5}\right]$

首先默认公式不考虑 $M\le 4或N\le 4$ 的情况，这是容易求解的，在考虑 $5\le M\le 9且5\le N\le 9$ 时，通过0-1规划的分支定界法逐个检验公式的正确性，下面对 $M=5p+m且N=5q+n\left(p,q\in I;m,n\in \left\{5,6,7,8,9\right\}\right)$ 证明该公式在 $10\ge M且10\ge N$ 的正确性，剩余一类情况可参照证明。

已知 $X\left(m,n,5\right)$ 是正确的，如图7所示可以将区域划分为两块，区域一为右下角 $m\times n$ 大小的已证明区域，对于我们的晶胞构造方法，只需将区域二铺满 $pn+qm+pq$ 个同类型晶胞，得出我们计算的最优解为 $X\left(m,n,5\right)=\left[\frac{m\times n}{5}\right]+5\left(pn+qm+pq\right)=\left[\frac{M\times N}{5}\right]$，则可以得出 $X\left(M,N,5\right)\le \left[\frac{M\times N}{5}\right]$ ；若按行将区域二分成 $5pn+5qm+5pq$ 个 $1\times 5$ 的晶胞(棋盘)，则可知每个区域至少需要放置1个棋子，可得区域二至少需要 $5pn+5qm+25pq$ 个棋子，又区域一至少需要 $\left[\frac{m\times n}{5}\right]$，则两区域合并前的最小值之和 $X_1\ge \left[\frac{m\times n}{5}\right]+5pn+5qm+5pq=\left[\frac{M\times N}{5}\right]$，对于合并前后的最小值X₁与X₂，由于合并后的问题相对合并前的问题增加了合并时边界上的约束，则由公理可知 $X_2\ge X_1$，则可知原问题 $X\left(M,N,5\right)\ge \left[\frac{M\times N}{5}\right]$，故只能取等号，得证。

Figure 7. Recursive proof diagram and a constraint diagram added after merging

图7. 递推证明图及合并后增加的一个约束示意

3.4. 逆推所有放置方法

1) 求出一种解

可变矩阵得出3 × 2时的可变生长区最少放置数为1，可变生长区为最佳晶胞的一部分，可以是由(2, 2)到(4, 3)，如图8所示。

根据可变生长区的起始位置(x, y)、可变生长区大小i × j和代表最佳晶胞，则只需将代表晶胞进行一个循环变换，逆推出A生长区的最佳晶胞，确定一种最优放置，如图9所示。

Figure 8. A selection of variable growth zones

图8. 一种可变生长区的挑选

Figure 9. An optimal placement of a variable growth zone

图9. 一种可变生长区产生的一种最优放置

2) 变换给出所有放置

可变生长区是最佳晶胞内连续的一部分，在最佳晶胞中仅运用同一方向的循环体性质寻找出所有能够满足最少放置数的i × j的连续矩形情况，对于3 × 2的可变生长区有4种放置为1的情况，再根据对称变换可得共8种最优放置，见图10。

Figure 10. 8 optimal placements of 13 × 17

图10. 13 × 17的8种最优放置

证明2：给出的最优放置方法是完备的

任取棋盘上一个5 × 5的区域，若仅考虑行和列的约束，此处最少需放置5个黑子，而若此区域放置多于5，则整体无法达到最优(证明参照证明1)，则此区域只能放置五个黑子，且每行每列均有一个，如此根据等价性则此区域必为一个MNQP的解，则可以推出其它区域也均为MNQP的相同解，故给出的放置方法是完备的。

3.5. 晶胞生长模型表述

上面可以看出，最佳晶胞在求解五子连珠问题上表现出的优越性，此处对模型做一个总结，表述如下图11：

Figure 11. Model usage process

图11. 模型使用流程

模型检验与总结

当棋盘空间较小时可以运用0-1规划与回溯法进行计算与结果检验，以下给出本模型计算部分结果如表2所示：

Table 2. Model calculation results are presented

表2. 模型计算结果展示

五子连珠问题对于不同大小棋盘的求解看似有所区别，实际是一种循环往复，最佳晶胞模型借助晶体学概念和部分模N皇后问题结论，很好地描述了这种循环的内在逻辑，比较全面地解决了此问题，计算速度远超0-1规划与回溯法，且能够快速给出所有放置。

对于多子连珠和一般化为d维空间下的n连珠问题，借鉴现有模N皇后的结论，运用此模型有效求解部分此类问题，能有效克服高维度、大棋盘和多连珠所产生的复杂度是后面研究的重点。

NOTES

^*通讯作者。