头条新闻

棋盘上不存在幻方骑士巡逻

作者：Eric W. Weisstein

2003年8月6日——经过 61.40 天的计算，一个有 150 年历史的未解决的问题终于得到了解答。这个问题涉及在一个空的编号为 8 x 8 的棋盘上，骑士可以走出的路径是否存在。

回顾一下，骑士可以走“L”形步法，即在一个方向上偏移一格，在垂直方向上偏移两格。现在让骑士在一个 n x n 的棋盘上移动，棋盘上的方格沿骑士的路径从 1 到 n² 编号，即初始方格标记为“1”，骑士触及的第二个方格标记为“2”，依此类推。如果这条路径恰好访问每个方格一次，则称为巡逻。上面的图表说明了 8 x 8 棋盘上的六种骑士巡逻。

骑士巡逻中产生的数字阵列还可以满足许多有趣的性质。特别是，考虑一个称为幻方（或有时称为“对角幻方”）的数字阵列，上面展示了一个。如果一个 n x n 的数字阵列（数字从 1 到 n²）中，每行、每列和对角线的数字之和都为一个相同的数字（称为该幻方的幻和），则称其为幻方。例如，在上图中，幻和为 15。如果一个方阵未能成为完全幻方，仅仅是因为其对角线未能求和为幻和（但其行和列求和为幻和），则称为半幻方。

毫不奇怪，如果骑士巡逻产生的数字排列形成幻方，则称为幻方巡逻；如果产生的数字排列是半幻方，则称为半幻方巡逻。长期以来，人们都知道，对于 n 为奇数的 n x n 棋盘，不可能存在幻方骑士巡逻。人们也知道，对于所有尺寸为 4k x 4k（k > 2）的棋盘，这种巡逻是可能的。然而，虽然在常见的 8 x 8 棋盘上已知存在许多半幻方骑士巡逻，包括上面所示的那些，但不知道在 8 x 8 棋盘上是否存在任何完全幻方巡逻。

这个长期存在的开放性问题现在已经通过对所有可能性的详尽计算机枚举得到了否定性的解决。用于计算的软件由 J. C. Meyrignac 编写，网站http://magictour.free.fr 由 Guenter Stertenbrink 建立，用于分发和收集所有可能巡逻的结果。经过 61.40 个 CPU 日（相当于以 1 GHz 运行 138.25 天的计算），该项目于 2003 年 8 月 5 日完成。结果是什么？除了获得了总共 140 种不同的半幻方骑士巡逻之外，计算首次证明了不可能存在 8 x 8 幻方骑士巡逻，从而最终解决了这个长期存在的开放性问题。