M皇后问题-构造法原理.pdfVIP

M皇后问题-构造法原理

[原]E.J.Hoffman;J.C.Loessi;R.C.Moore

TheJohnsHopkinsUniversityAppliedPhysicsLaboratory（约翰霍普金斯大学应用物理实验室）

[译]EXP2017-12-29

1.前言

文本核心内容主要译自E.J.Hoffman、J.C.Loessi和R.C.Moore发表于Mathematics

Magazine《数学杂志》上的学术论文《ConstructionsfortheSolutionofthemQueensProblem》（已

被美国数学协会MathematicalAssociationofAmerica公开），具体期数为Vol.42,No.2(Mar.,

1969),pp.66-72。

该文献可从以下途径购买：

该文献的英文原文链接：~trolfe/QueenLasVegas/Hoffman.pdf

该文献的CSDN下载地址：

2.问题背景

M皇后问题：在M×M格的国际象棋上摆放M个皇后，使其不能互相攻击，即任意两个

皇后都不能处于同一行、同一列或同一斜线上。

根据场景，又有三种衍生问题：

①共有多少种摆法（即有多少种可行解）

②求出所有可行解

③求任意一个可行解

问题①属于禁位排列问题，目前是存在通项公式直接求解的。

问题②属于搜索问题，在网上也有多种解法，主流是回溯法（另有衍生的位运算变种算

法），但不管如何优化，回溯法都有一个致命的问题：M值不能过大（一般M=30已是极限）。

问题③属于问题②的子集，因此很多人的切入点依然是回溯法，也有启发式算法的解法：

如遗传算法、还有刘汝佳在《算法艺术与信息学竞赛》提出的启发式修补算法。启发式算法在

M10000左右都是可解的，但是因为启发式算法均存在随机性，收敛速度视不同的收敛因子而变

化（我看过某篇论文称启发式算法在M=10000时的耗时等价于回溯法M=30的耗时）。

但早在1969年，问题③的解就被E.J.Hoffman、J.C.Loessi和R.C.Moore找到了潜在的

数学规律，通过推导出数学公式，利用构造法使得该问题可在O(1)的时间复杂度得到解。

3.译者的话

①由于原文使用了“m皇后”进行描述，所以本文也使用“m皇后”进行描述。我这里就

不调整为大多数人习惯的“n皇后”了，避免某些数学公式参数混淆。

②原文写得有点艰涩，有些中间步骤是跳过了。我就加上自己的理解做了意译，并补上了

跳过的步骤和图示，但是核心的推导思路和步骤不会修改。

③原文首先给出了3个构造式（其实就是m皇后问题的通解式），然后以此为结论展开了

一系列的推导证明这3个构造式是正确的。但是这3个构造式真正是怎么得来，原作者并没有说，

估计是原作者做了大量的演绎、从m皇后的特解找到了潜在规则所总结出来的通解。

4.译文：m皇后问题的构造解法

4.1数学模型定义

m皇后问题最初是由Gauss（高斯）提出的，该问题描述如下：

是否有可能在一个m×m的国际棋盘上放置m个皇后使得她们无法互相攻击？（注：皇后是

国际象棋中的一种棋子，她可以对横、竖、斜三个方向的棋子发起攻击）

这是一个有趣的问题，我们可以将其约束到一个数学模型进行描述：

把棋盘定义为一个m×m的方格矩阵，那么对于任意方格可以使用有序对(i,j)以表示其行

列坐标，其中1im表示该方格的行编号，1jm表示该方格的列编号。

同时我们再为每个方格定义一组对角编号：

令自左上到右下方向为主对角线，对于主对角线上的方格(i,j)，显然有：

mjiMAJOR_CONSTANT——译者注：这个公式对后续推导起到重要作用

其中MAJOR_CONSTANT称之为主对角常数，显然有1MAJOR_CONSTANTm