一个困扰数学家150多年的国际象棋问题终于被破解了。
n皇后问题最初是一个更简单的难题，由国际象棋作曲家 Max Bezzel 在 1848 年的德国国际象棋报纸 Schachzeitung 中首次提出。它询问八个敌对皇后——它们是棋盘上最强大的棋子，能够水平、垂直和对角移动任意数量的方格——有多少种方式可以放置在一个标准的 64 方格棋盘上，而没有任何皇后攻击另一个棋子。
仅仅两年后，答案就揭晓了，有 92 种配置可以让 8 位皇后远离彼此的喉咙，除了 12 种解决方案之外，所有解决方案都是简单的旋转和彼此的反射。但是在 1869 年，数学家 Franz Nauck 提出了一个更令人困惑的问题：与其在标准的 8×8 棋盘上配置 8 个皇后，不如在 1000×1000 棋盘上配置 1000 个皇后呢？一百万，甚至十亿呢？
曾经是一个相对简单的谜题现在变成了一个更深层次的数学问题——需要发现一个通用规则，即在 n×n 棋盘上放置任意数量（表示为“n”）皇后的方法的数量.
现在，哈佛大学数学科学与应用中心的数学家迈克尔·西姆金（Michael Simkin）提出了一个几乎确定的答案。
在一个巨大的 n×n 棋盘上，大约有 (0.143n)^n 种方式来放置 n 个皇后，这样没有一个皇后可以互相攻击。这意味着在百万乘以百万的棋盘上，100 万个皇后可以排列成的无威胁配置的数量大约是 1，然后是 500 万个零。
Simkin 花了将近 5 年的时间才找到这个方程的近似值。数学家通常通过寻找方法将问题分解成更易于管理的块来解决问题。但是因为靠近棋盘中心的皇后可以攻击比边缘的皇后更多的方格，所以 n-皇后问题是高度不对称的——因此，顽固地抵制简化。
与苏黎世瑞士联邦理工学院的数学家 Zur Luria 合作，Simkin 最初通过考虑更对称的“环形”问题来简化任务，其中边缘正方形环绕电路板形成甜甜圈形状. 例如，这种安排使皇后可以在左上角消失并在右下角重新出现。这也意味着无论他们放在哪里，每个女王都可以攻击与其对手相同数量的方格。
通过使用环形板作为第一个近似值，两位数学家接下来将一种称为“随机贪心算法”的策略应用于该问题。他们随机放置了一个皇后，将它攻击的所有方格都挡住了；然后下一个皇后将被选中坐在剩余的位置上，其攻击方格依次被封锁。这对搭档继续在多种配置上进行此操作，直到他们在环形板上的 n 个皇后的配置数量上找到一个粗略的下限（或可能的最低数量）。
但他们的估计远非完美。棋盘的环绕性使他们无法在某些配置中找到最后几个皇后位置。在放弃了几年的问题后，两人又回到了这个问题上，并提出了将他们的算法调整到常规棋盘的想法，这比环形棋盘为最终的皇后提供了更多的隐藏点。通过将随机贪心算法应用于标准的非环形板，这对算法在一定程度上提高了这个下限估计的准确性。
但他们的答案并不像他们希望的那样明确——随机贪心算法在对称问题上效果最好，每个棋盘格都提供与其他棋盘格相同的攻击优势。对于标准棋盘来说，情况并非如此，边缘方格的攻击能力远低于中心方格。
为了解决这个问题，Simkin 意识到他需要调整算法。由于标准棋盘上的大多数可行配置在棋盘边缘（它们攻击的棋格较少）比在棋盘中心有更多的皇后，因此 Simkin 通过对棋格加权来改进随机贪心算法。他的算法不是随机分配皇后，而是优先将皇后放置在可以分支到最多可能配置的位置。这使 Simkin 能够专注于每个棋盘部分的皇后数量，并找到有效配置数量的公式，从而进一步提高下限猜测的准确性。
“如果你告诉我，‘我希望你把你的皇后以这样那样的方式放在棋盘上’，那么我将能够分析算法并告诉你有多少解决方案符合这个约束， ” 西姆金 在 一份声明中 说. “在形式上，它将问题简化为优化问题。”
但是找到一个数字的下界仍然会留下一个无限大的数字集。为了真正找到解决方案，Simkin 需要找到一个上限。为了解决这个问题的后半部分，他转向了一种称为“熵法”的策略，该策略涉及在新皇后被放置在棋盘上后记录未受到攻击的方格数。使用这种方法，他产生了一个最大界公式，该公式给出了一个几乎与他的下界数字完全匹配的数字；Simkin 得出的结论是，他实际上已经接近完全确定了这个公式。
未来的工作可能会尝试将这两个界限更加紧密地结合在一起，但 Simkin 比他之前的任何人都更接近，因此满足于将这一挑战留给其他人来征服。
“我认为我个人可能会暂时解决 n-queens 问题，”Simkin 说。“不是因为与它无关，而是因为我一直梦想着国际象棋，我已经准备好继续我的生活了。”
Simkin 在预印本数据库arXiv上发表了他尚未经过同行评审的作品。
