问有预定义皇后的N号女王

EN

是。

N-皇后完成的复杂性 DOI https://doi.org/10.1613/jair.5512 伊恩·彭特 克里斯托弗·杰斐逊 彼得·南丁格尔 文摘 N皇后问题是将n个国际象棋皇后放在n个棋盘上，这样就不会有两个皇后在同一排、列或对角线上。女皇完成问题是一个变体，可以追溯到1850年，其中一些皇后已经被安置，如果可能的话，解决者被要求放置其余的。我们证明了n-皇后完成是NP-完全和#P-完全.其推论是，任何非攻击的皇后安排都可以作为一个更大的n-皇后问题的解决方案的一部分。我们引入了n-Queens完成的随机实例的生成，以及与之密切相关的阻塞n-皇后和排除对角的问题。我们描述了这些问题的三个求解者，并对随机生成的实例的硬度进行了实证分析。对于阻塞的n-皇后问题和被排除的对角线问题，我们证明了与硬实例相关联的相变的存在，就像在其他NP-完全问题中所看到的那样，但是n-Queens完成的自然生成器并没有产生一致的硬实例。这项工作的意义在于，n-Queens问题已经被广泛用作人工智能中的一个基准，但由于决策问题的简单复杂性，关于它的结论常常是有争议的。我们的结果给出了理论上和经验上都很难的替代基准，但是为n-Queens设计的解决技术需要最小或不改变。