国际象棋爱好者知道这是一个指数级复杂的游戏。前三步将产生900多万个可能的董事会职位，而在双方进行前四步操作的可能方式有近3190亿个。这使得解决国际象棋问题变得难以想象。这也是这个游戏长期以来吸引计算机科学家的原因之一。即使是世界上最快的计算机也不可能在一场象棋游戏中运行10120个可能的排列，但是可以设计出算法来以更少的努力达到同样的结果吗？现在，苏格兰圣安德鲁斯大学的一个研究小组已经证明，在至少一个著名的国际象棋问题上，它是不可能的。如果他们的证据成立的话，这将使关于所谓的n皇后问题的长达170年的争论停止。另一方面，任何能证明他们错误的人都有资格获得周四宣布的100万美元的现金奖励，这可能是建立下一个微软公司的快速通道。皇后的问题92个n皇后区解决方案图片之一：维基百科n-皇后问题是在一个n×n的棋盘上放置n个棋后，这样就不会有两个棋后互相攻击，也就是说它们不共享同一行、同一列或同一对角线。想出一个解决问题的算法比听起来要困难得多。在一个标准的八乘八棋盘上，有44亿个八皇后的可能安排，但只有92个方案已经确定。随着董事会规模越来越大，问题变得越来越困难。圣安德鲁斯计算机科学家伊恩·根特教授和他的同事克里斯托弗·杰斐逊和彼得·南丁格尔实际上着手解决一种称为n皇后区完成的变体，它具有更大的商业意义。在这个版本中，已经有一个或多个皇后被放在棋盘上，而挑战是把其余的放进去。这个问题类似于一家商业包裹递送公司，例如，在优化一组配送中心周围的路线时可能会遇到的问题。最初的n-皇后问题是1848年提出的，从那时起就吸引了数学家和计算机科学家。它作为人工智能基准的价值一直是争论的焦点，这意味着一个能够在规模上求解n皇后的算法，从定义上讲，将是智能的。然而，从来没有人能大规模地解决这个问题，根特和他的同事们认为，不太可能有人会这样做。他们的论文发表在最新一期的《人工智能研究杂志》上，证明了n皇后完全性是"NP完全的"（NP代表"不确定性多项式"）。基本上，这意味着可以验证问题的解决方案，但不可能首先找出解决方案。开发一种求解n皇后完成的算法将在其他领域有广泛的应用。"如果你能很快解决一个（NP完成）问题，你就可以自动解决所有其他问题，"Gent在接受siliconagle采访时说。例如，美国职业棒球大联盟可以用它来优化一个赛季所有30支球队的赛程。航空公司可以为整个全球机队规划最省油的航线。大学可以用它来优化宿舍分配中的室友相容性。100万美元的解决方案这些潜在的应用是克莱数学研究所（Clay Mathematics Institute）将NP问题列入挑战清单的一个原因，该研究所为此提供了100万美元的解决方案。"[O] 该研究所在其网站上写道："计算机科学中的一个突出问题是确定是否存在问题，这些问题的答案可以迅速得到核实，但这些问题需要很长时间才能通过任何直接程序解决。"。根特对n皇后区的兴趣是由一位同事在2015年元旦在Facebook上发布的挑战引发的。"吸引我个人的是，它有着悠久的历史，很多人都在研究不同的解决方法。"。Google Scholar在其数据库中列出了6500多个对n-Queen的引用。研究人员在34页的论文中记录了许多公式，只有数学家才能理解他们创造的三个解算器的结果，要么找到一个解，要么确认没有解。如果他们的证据成立，从技术上讲，他们将有资格获得克莱学院奖，但根特没有屏住呼吸。"你必须让你的论文发表在一个有信誉的，同行评议的杂志上，然后等上两年，以防出现挑战。"。为什么一篇证明某件事不可能发生的论文有这么大的意义？基本上，这样研究人员就可以不再把头撞在墙上，而是专注于其他事情。""当你证明某件事是NP完全的时候，你通常会停止尝试去解决它，"Gent说你不是想用锤子敲碎它，而是把碎片敲碎。"这将有助于他们避免陷入像《银河系搭车指南》中虚构的深邃思考的超级计算机那样的永恒的斗争，它用了750万年的时间才给出了万物意义的答案。图片：皮克斯贝既然你来了…点击订阅我们的YouTube频道（见下文），显示您对我们使命的支持。我们的订户越多，YouTube就越会向你推荐相关的企业和新兴技术内容。谢谢！支持我们的使命：>>>>>立即订阅我们的YouTube频道。……我们还想告诉你我们的使命，以及你如何帮助我们完成它。SiliconANGLE Media Inc.的商业模式是基于内容的内在价值，而不是广告。与许多在线出版物不同的是，我们没有付费墙或横幅广告，因为我们想让我们的新闻保持开放，不受影响，也不需要追逐交通。那个新闻、报道和评论SiliconANGLE——以及现场报道，我们的硅谷工作室和cube环球巡演的视频团队提供的未经剪辑的视频需要大量的辛勤工作、时间和金钱。保持高质量需要赞助商的支持，他们与我们的无广告新闻内容的愿景一致。如果你喜欢这里的报道，视频采访和其他无广告内容，请花点时间看看我们的赞助商支持的视频内容样本，在推特上表达你的支持，然后继续回到SiliconANGLE。