n-皇后完成问题-线性解算法

埃里格里格

前言

在开始研究之初，我想对敖德萨的两位出色程序员表示感谢，他们是Andrei Kiper（洛基卡（Lohica））和Timur Giorgadze（Luxoft），以对我的结果进行独立验证。

1. 2020年第一天开始在（arXiv.org）上发表了文章“求解n皇后完成问题的线性算法”。 最初，该文章是用俄语撰写的，因此此处提供了基本介绍，并提供了翻译。
2. 此任务以及其他许多NP-完全集（满足布尔公式（3-SAT）的任务，寻找最大集团或给定大小的集团...的任务）在不同的时间都在我感兴趣的领域。 我一直在寻找一种基于各种计算实验的算法解决方案，但是并没有取得具体的成功。 就像一个人试图学习如何使一只手的单杠适应。 没有结果，但是每次都有希望一切都会很快解决的希望。 我最后一次决定，我应该在n-Queens完成任务上停留更长的时间（作为家庭成员之一），并尝试做一些事情。 在这里，您应该回想一下敖德萨的一个有趣的笑话：“在傍晚颠簸的道路上返回郊区的拥挤公交车中，听到了女人的声音-男人，如果您完全躺在我身上，至少可以做点什么。”
3. 该研究持续了足够长的时间-将近一年半。 一方面，这是由于在研究过程中考虑了其他任务，另一方面，在此过程中存在许多难题，没有这些问题我们就无法前进。 我将列出其中一些：
   
   
   • 决策矩阵中有n行，如果这种选择的可能性为n，则应按什么顺序选择行索引！
   • 当制作一行时，应选择该行中剩余的空闲位置中的哪一个，因为这种选择的可能性很大，以至于可以将其视为无穷大的“近亲”（例如，为大小为100的棋盘在所有行中选择一个空闲位置的可能方式的数目x 100约为¹⁰¹²⁴ ）
   • 这两个指标一起形成一个状态空间（一个选择空间）。 似乎有很多机会，您可以选择想要的。 但是在每个步骤的每个特定选择之后，还有另一个问题-所有后续步骤中选择的局限性。 此外，这在解决问题的最后阶段特别敏感。 我们可以说决策矩阵是“报仇性的”。 您在前一阶段做出选择时所犯的所有“无意识的错误”都是“累积的”，而在决定的最后，这一事实表明，在您应该放置女王/王后的那一行中，没有空位，搜索分支陷入停顿。 。 就像兹瓦涅茨基所说的：“一个错误的举动，你就怀孕了。”
   • 当搜索解决方案的分支陷入停顿时，我们就有机会回到一些先前的位置（“后退跟踪”），以便从该位置开始，我们将再次开始形成搜索解决方案的分支。 这是非确定性问题的自然“属性”。 问题是应返回先前的哪个级别。 这与选择行索引或在该行中选择自由头寸的问题是相同的未解决问题。
   • 最后，应注意与算法速度有关的问题。 如果没有目标来创建快速运行的算法，那将是可悲的。 在建模过程中，不可能开发出一种能够在问题解决方案的所有领域中快速有效地工作的算法。 我必须开发三种算法。 他们像指挥棒一样将结果相互传递。 其中一个工作非常迅速，但是粗鲁地工作，另一个-相反，工作缓慢但有效。 他们每个人都在“职责范围”内工作。
4. 最初，研究的目的仅仅是找到至少一些解决方案。 在开发第一个解决方案之前，我有很多事情要弄清楚。 花了四个多月的时间。 可以在那里停下来，实现了目标-好的，好的。 但是在我看来，并不是所有用算法解决此问题的可能性都被穷尽了。 自然地，需要改进开发的算法，以使算法的时间复杂度为线性-O（n）。 当找到这样的线性解决方案时，“又有一个愿望”-减少在解决方案搜索分支的形成中使用反向跟踪（BT）程序的情况。 将任务从不确定性转移到有条件确定（尽可能）是“无礼的”愿望。 它花费了很多时间，但达到了目标，例如，在棋盘大小的值的间隔n =（320，...，22500）中，从未使用过BT程序的情况数量超过了50％。 事实证明，在启动程序的50％的情况下，算法“有目的地”构成了解决方案，而从未“绊脚石”。 （回想起关于金鱼的童话故事，我停止了这两个愿望……）
5. 通过比较研究过程中我能结识的出版物，我得出的结论是，无法基于严格的数学方法（即仅基于定义，引理和定理证明）来解决该问题和此类问题。 文章中对此有“哲学评论”。 我相信，只有借助计算机建模，才能在算法数学的基础上解决许多NP-Complete中的许多问题。 这样的结论并不意味着限制数学，相反，它意味着通过算法数学方法的发展来扩展数学的能力。 对于每个问题系列，您都需要使用自己的适当数学方法。 （如果已知没有什么真正意义的话，为什么要指派一名研究生来解决NP-Complete家族的问题而不应用算法数学和计算机建模方法）。
6. 任何算法（程序）都具有简单的属性-不管是否起作用！ 我想向我们的Habro社区的那些在无障碍区域中装有装有Matlab的计算机的成员发出呼吁。 我想请您测试考虑的算法来解决n皇后完成问题 。 这仅需5-10分钟。 要测试算法，您需要执行一些简单的步骤：
   
   
   • 从k个皇后生成一个随机构图，并检查此构图的正确性。
   • 基于提出的决策算法，完成此组合以得到完整的解决方案。 否则程序必须确定此组合没有解决方案。
   • 检查作为配置结果获得的解决方案的正确性。
   
   
   您不必为此类测试编写任何代码。 除了主程序外，我还用Matlab语言编写了两个程序：
   
   1. Generarion_k_Queens_Composition-为大小为nxn的任意棋盘生成大小为k的随机组合
   
   2. Completion_k_Queens_Composition.m-完成任意组合直到完成一个完整的决定，或者确定该组合没有解决方案（ 主程序 ）。
   
   3. Validation_n_Queens_Solution.m-检查n皇后问题的解的正确性，或k个皇后的组成的正确性。
   
   他们工作非常快。 例如，对于大小为1000 x 1000格的棋盘，平均生成一个任意成分的总时间（0.0015 s。），完成此成分（0.0622 s。），并验证所获得溶液的正确性（0.0003 s。）不超过0.1秒。 （不包括下载数据或保存结果所需的时间）
   
   给我发送电子邮件（ericgrig@gmail.com），如果您有机会帮助朋友，我会立即向您发送这三个程序。 我将感谢所有能够客观地测试算法并在讨论中表达意见的同事。
7. 我准备了程序的源代码，并附有详细的注释，希望不久后可以在Habré上发布。 我认为那些对解决NP-Complete家庭的复杂问题感兴趣的人会为自己找到一些有趣的东西。
8. 我想再次呼吁Habr社区的成员，但是出于另一个原因。 在这里，法国的马赛（France Fold Group）团队正在组建中，其目的是研究和开发用于预测高分子量化合物的理化性质的算法。 我认为不应该说这是一项艰巨的任务，历史悠久，而且不同国家的认真团队正在致力于解决此问题，包括Deep Mind的Khasabis团队（您可以在Habré （habr.com_Folding）上看到该文章。我们的目标是创建一个不怕解决复杂问题的强大团队，以分散的形式开展联合工作，每个团队成员都居住在自己的城市并在业余时间从事项目工作，我们需要程序员和研究人员（物理学家，化学家，数学家，生物学家） ）等 osto“鲁re的”程序员-（平方）如果您觉得有趣，请写信给我，上面是我的电子邮件，我可以在回复信中详细说明。

文章的序言与文章本身一样长。 哈布雷（Habré）上的家庭介绍形式使我可以更自由地表达自己的想法，但是从规模上来看，我相当自由地利用了它。 我想简短地写，但“结果还是一如既往”。

PS：我认为Habr社区的成员很想知道我在尝试发布研究结果时遇到的困难。 在准备本文时，我根据《人工智能研究杂志》（JAIR）的要求将其重新格式化为.tex格式，并将其发送到那里。 曾经有过类似主题的出版物。 特别值得注意的是C. Gent，I.-P。 Jefferson and P.Nightingale（2017） （n-皇后完成的复杂度） ，作者证明了所讨论的问题属于NP-完全集，并讨论了尝试解决该问题时遇到的困难。 在结论中，作者写道：“对于任何了解国际象棋规则的人，n-Queens完成可能是所有最自然的NP-Complete问题之一”（ 对于每个了解国际象棋规则的人，n-Queens完成任务可以成为其中一项最自然的NP完成任务 ）。

10天后，我收到JAIR的拒绝，其措词是：“该文章与期刊的格式不符”，即 甚至没有考虑这篇文章。 我没想到会有这样的答案。 我认为，如果期刊发表的文章认为作者很难解决给定的问题并且不提供任何具体解决方案，那么提供有效解决方案算法的文章肯定会被接受。 但是，编辑对此事有自己的见解。 （我相信有能力的专家在那里工作，并且他们很可能受到“无礼的”文章标题和那里所说的一切的质疑。我们认为，“最有可能是某种错误，我轻率地把我送走了，指的是格式”）。

我不得不选择另一本有关主题的同行评审期刊科学出版物。 在这里，我面临着严峻的现实。 事实是，大约80％的杂志都是付费的：要么我必须向该杂志支付一定数额的费用，以便所有读者可以免费获得该文章，要么他们需要把该文章作为礼物“送礼”，并且他们将向所有想了解这项研究。 从根本上说，第一和第二种选择是我无法接受的。 当我试图使自己熟悉一些出版物时，我对这种发行人球拍的方法感觉很好。

另一本以免费获取信息为原则的杂志是《 SMAI计算数学杂志》 。 他们也拒绝了同样的措辞，尽管速度更快了-两天之内。

然后选择了期刊： 离散数学与理论计算机科学 。 这里的要求很简单，首先您需要在arXiv.org中发布文章，然后再注册该文章以供考虑。 好的，我们会遵守规则-我在arXiv.org中提交了一篇文章。 他们写信给我说，他们将在8小时内发布该文章。 但是，这不会在8小时后发生，而不是在8天后发生。 该文章由导师“持有”，并且仅在9天后才发表。 在文章的形式和本质上没有任何抱怨。 我认为，与JAIR一样，导师对“这样做并编写”的可能性表示怀疑。 一段时间后，纠正了技术错误后，文章进行了更新，最终形式在新年之夜发布。

我必须详细说明这一点，以表明在研究结果发表的阶段可能存在无法逻辑解释的问题。

以下是在（arXiv.org）上发布了其英语翻译的文章。

1.简介

在制定n皇后问题的各种选择中，有问题 的n皇后完成任务由于其复杂性而处于特殊位置。 在他们的工作中（Gent at all（2017））显示n-皇后完成问题属于集合NP-完成 （ 表明n-皇后完成既是NP-完成又是＃P-完成 ）。 假定该问题的解决方案可以为我们解决NP-Complete集中的其他问题打开道路。

问题被表述如下。 由k个皇后组成，一贯分布在大小为nxn的棋盘上。 需要证明该组合物可以完成为完整的溶液，并给出至少一种溶液，或者证明不存在这种溶液。 在这里，通过一致性，我们指的是满足以下三个条件的k个皇后的组合：在每一行，每一列以及穿过女王所在的单元格的左右对角线上，最多只能有一个皇后。 这种形式的问题最早由Nauk（1850）提出 。

1.1定义

在下文中，我们将用符号n表示棋盘侧面的尺寸。 如果将所有n个皇后号始终放在棋盘上，则该解决方案将称为“完整”。 所有其他解决方案，当正确放置的皇后数k小于n时 ，我们将其称为合成。 如果可以在完整的解决方案之前完成，我们称k个皇后组合为正。 因此，直到完成解决方案才能完成的构图称为否定构图。 作为大小为nxn的“棋盘”的类似物，我们还将考虑大小为nxn的“解决方案矩阵”。 例如，将使用Matlab语言介绍为解决该问题而开发的所有算法。

该研究是在计算机仿真（计算仿真）的基础上进行的。 为了检验这个假设或该假设，我们在各种值n =（10，20，30，40，50，60，70，80，90，100，200，300，500，800，1000，3000， 5000，10000，30,000，50,000，80,000，10 5，3 * 10 ^5，5 * 10 ^5，10 6，3 * 10 ^6，5 * 10 ^6，10 7，3 * 10 ^7，5 * 10 ^7，8 * 10 ^{7，10 8} ），并根据n的值生成足够大的样本进行分析。 我们称此类列表为进行计算实验的“ n个值的基本列表 ”。 所有计算均在常规计算机上进行。 在组装时（2013年初），它的配置相当成功： CPU-Intel Core i7-3820、3.60 GH，RAM-32.0 GB，GPU-NVIDIA Ge Forse GTX 550 Ti，磁盘设备-ATA Intel SSD，SCSI，OS- 64位操作系统Windows 7 Professional 。 我们将此套件简称为-desktop-13 。

2.数据准备

该算法首先读取一个文件，该文件包含一维数据数组，该数据数组包含k个皇后的任意成分的分布。 假定以以下方式准备数据。 设一个归零数组Q（i）= 0，i =（1，...，n） ，其中该数组的单元格索引对应于解矩阵的行索引。 如果在解决方案矩阵的任意行i中的位置j处有一个皇后，则执行赋值Q（i）= j 。 因此，合成大小k将等于数组Q的非零像元数。 （例如， Q =（0，0，5，0，4，0，0，3，0，0）表示我们正在考虑在矩阵n = 10上构成k = 3个皇后，其中皇后位于第3个，第5和第8行，分别位于：5、4、3）。

3.验证解n-Queens问题正确性的算法

为了进行研究，我们需要一种算法，该算法将使我们能够在短时间内确定n-Queens问题解的正确性。 控制皇后在每一行和每一列中的位置很简单。 问题是对角线限制。 如果我们可以将解决方案矩阵的每个像元映射到某个控制向量的某个像元，那么它可以唯一地描述对角线限制对所讨论像元的影响，那么我们可以为这种核算建立一个有效的算法。 然后，基于控制向量的单元格是空闲还是繁忙，可以判断决策矩阵的相应单元格是空闲还是关闭。Sosic＆Gu（1990）首先使用了这种想法，以考虑并积累皇后不同位置之间的冲突情况。我们在下面介绍的算法中使用了类似的想法，但只是要考虑解决方案矩阵的单元格是空闲还是繁忙。例如，图1显示了一个8 x 8的棋盘，上面有24个单元格的序列。


图1.矩阵单元的对角线投影与控制阵列D1和D2的相应单元的对应关系的演示示例，（n = 8）

将前15个单元视为控制矢量D1的元素。来自解矩阵的任何单元的所有左对角线的投影落入控制向量D1的单元之一。实际上，所有这些投影都位于两个平行的线段内，其中一个将矩阵（8.1）的单元与向量D1的第一个单元相连，将第二个-矩阵（1.8）的单元与控制向量D1的第15个单元相连。对于右对角线投影，我们给出了类似的定义。为此，将原点从单元格1移动到右侧的单元格9，并将16个单元格的序列视为控制向量D2的元素（在图中，这些是从9号到24号的像元。）从解决方案矩阵的任何像元开始的所有对角线的投影将从第二个像元到第16个像元（从图中的第10个像元开始）落入此控制向量的一个像元中。 24）。在这里，所有这些投影都位于两条平行线段之间：将溶液矩阵的单元格（8,8）与向量D2的单元格16 （图中的单元格24）相连接的段以及将溶液矩阵的单元格（1,1）与单元格之间的连接段控制向量D2的第2 步（图中的单元10）。位于同一左对角线上的解矩阵的所有单元的投影都落在左控制向量D1的同一单元中分别位于相同右对角线上的解矩阵的所有单元的投影分别落入右控制向量D2的相同单元中。因此，这两个控制矢量D1和D2允许完全控制决策矩阵的任何单元的所有对角线抑制。

重要的是要注意，在控制向量的单元上使用对角线投影来确定具有坐标（i，j）的求解矩阵的单元是空闲还是繁忙的想法后来在Richards（1997）中得到了实现。。它基于带位掩码的操作，为所有解决方案提供了最快的递归搜索算法之一。一个重要的区别是，所示算法设计用于从解决方案矩阵的第一行（向下）或从矩阵的最后一行（向上）开始的所有解决方案的顺序搜索。我们提出的算法基于以下条件：皇后位置的每行编号选择必须是任意的。对于正在考虑的算法，这是至关重要的。请注意，上面的图1是我们与本文所发表的内容类似地构建的。
检查n皇后问题的给定解是否正确或k的给定组成是否正确的程序皇后如下。

1.要控制对角线禁令，请创建两个数组D1（1：n2）和D2（1：n2），其中n2 = 2 * n，以及一个数组B（1：n），以控制解决方案矩阵各列的占用率。将这三个数组清零。

2.我们介绍正确安装的皇后数量（totPos = 0）的计数器。一致地，从第一行开始，在一个周期中，我们考虑所有皇后位置。如果Q（i）> 0，则根据第i行的索引和该行中女王的位置的索引j = Q（i），我们为控制数组D1（r）和D2（t）形成相应的索引：
r = n + j-i
t = j + i

3.如果满足所有条件（D1（r）= 0，D2（t）= 0，B（j）= 0），则意味着该单元格（ i，j）是自由的，并且不属于先前建立的女王形成的对角线限制的投影区域。女王在这个位置上的位置是正确的。如果不满足这些条件中的至少一个，则分别选择该位置将是错误的，并且该决定将是错误的。

4.如果解决方案是正确的，则增加正确安装的皇后数的计数器（totPos = totPos + 1），并关闭控制数组的相应单元格：（D1（r）= 1，D2（t）= 1，B（j）= 1）。所以我们关闭列中的所有单元格（j）以及沿着矩阵的左，右对角线与单元格（i，j）相交的解矩阵的单元格。

5.对所有剩余职位重复验证过程。
也许这是用于评估n皇后问题解的正确性的最快算法之一。桌面13上的解决方案10 ⁶ x 10 ⁶矩阵的一百万个位置的验证时间为0.175秒，大约对应于按下“ Enter”键的时间。显然，该算法相对于n计数时间是线性的。

4.解决问题的算法说明

一般 。 n-皇后完成问题是一个经典的不确定性问题。 它的解决方案的主要困难与在状态空间很大的情况下在该行中选择行索引和位置索引的问题有关。 当寻找所有可能的解决方案时，不会出现这样的问题。 我们必须考虑状态空间中的所有有效搜索分支，并且考虑它们的顺序无关紧要。 但是，当需要完成k个皇后的任意组合直到完成一个完整的解决方案时，在这种情况下，我们需要一种用于选择行和列索引的算法，该算法应能充分感知现有的组合并比其他方法更快地得出解决方案。 在此项目中，我们根据以下一般位置决定了选择问题- 如果我们无法制定优先于任何行或该行中任何位置优先于其他条件的条件，则我们将基于均匀分布的随机数 。 解决状态空间巨大的问题的类似随机选择方法是很自然的。 DIMACS研讨会论文集（1999）中的一个版本完全致力于在解决复杂问题的算法开发中使用随机选择。 尽管这是完成解决方案的必要条件，但不是充分条件，但是随机选择算法的正确实现可以是一种非常有效的解决方案。 Sosic and Gu（1990）是最早使用随机选择算法解决n-Queens问题的研究之一 。 他们检查的算法基于一个相当简单而简洁的想法。 假设有一个从1到n的数字序列，它们是随机重新排列的。 这样的一组数字具有重要的性质。 它包含以下事实：无论这些数字如何作为皇后位置分布在解决方案矩阵的不同行上（每行一个数字），前两个规则始终会在问题的陈述中得到满足：每一行和每一列都不会不止一位女王。 然而，仅由此获得的位置的一部分将没有对角线限制。 另一部分将与先前建立的皇后区处于“冲突”状态。 为了摆脱这种情况，作者使用比较和互换冲突位置的方法来获得完整的解决方案。 在我们提出的算法中，冲突情况是不可能的，因为在解决问题的每个步骤中，仅在有空的单元格中，才将女王安装在有问题的单元格中。

4.1选择回溯模型（BT）

在寻找问题的解决方案的过程中，当解决方案的顺序链导致死胡同时，可能会出现这种情况。 这是非确定性问题的“遗传”性质。 在这种情况下，您需要返回到先前的步骤之一，按照此级别还原任务的状态，然后从该位置再次开始寻找解决方案。 问题是应该返回哪个先前的级别，以及应该返回多少个此类级别（按级别，这意味着要使用给定数量的正确安装的女王/王后解决该问题的特定步骤）。 显然，选择要返回的解决方案级别与在该行中选择行索引或位置索引一样重要。 因此，不管解决该问题的方法如何，都必须首先确定用于返回的基本级别的数目，以及用于返回到这些级别之一的机制和条件。 在我们提出的算法中，我们将解决方案矩阵分为三个基本级别。 这些是返回点。 如果作为解决方案的结果，发生死锁，那么根据任务的参数，我们将返回到这三个基本级别之一。 第一基本级别（ baseLevel1 ）对应于所讨论的构图的数据验证完成时的状态。 这是程序的开始。 以下两个基本级别（ baseLevel2和baseLevel3 ）的值取决于矩阵n的大小。 这些基本值对解决方案矩阵大小的经验依赖性是根据大量计算实验确定的。 为了更准确地表示这种依赖性，我们将整个考虑的间隔从7到10 ⁸分为两部分。 令u = log（n） ，然后如果n <30 000 ，则

baseLevel2 = n-舍入（12.749568 * u3-46.535838 * u2 + 120.011829 * u-89.600272）
baseLevel3 = n-舍入（9.717958 * u3-46.144187 * u2 + 101.296409 * u-50.669273）

否则

baseLevel2 = n-舍入（-0.886344 * u3 + 56.136743 * u2 + 146.486415 * u + 227.967782）
baseLevel3 = n-舍入（14.959815 * u3-253.661725 * u2 + 1584.713376 * u-3060.691342）

4.2区块结构

该算法以五个事件块的序列的形式构造，其中每个事件与问题解决方案的特定部分的执行相关。 每个块中的处理算法互不相同。 五个模块中只有三个用于形成解决方案的顺序链，其余两个模块是准备性的。 开始计算的块编号的选择取决于n的值以及将合成大小k与baseLeve2和baseLevel3的值进行比较的结果。 n =（7，...，99）的值是一个例外，由于本节中算法行为的特殊性，可以将其称为“湍流区”。 对于n =（7，...，49）的值 ，无论构图的大小如何，在输入和监视数据后，计算将从第4块开始。 对于值n =（50，...，99） ，根据构图的大小，计算从第二个块开始或从第四个块开始。 如上所述，在解决问题的每个步骤中，仅认为生产线上的那些位置不属于先前确定的女王/王后创建的限制区域。 这些职位被称为自由职位。
让我们简要地描述在程序的这五个模块中的每个模块中执行什么计算。

4.3算法开始

输入数据并检查组成是否正确。 在每个验证步骤，将更改控制阵列的单元。 计算正确安装的女王/王后的数量。 如果合成中没有错误，则解决方案继续，否则显示错误消息。 验证完成后，将创建主阵列的副本，以供在此级别重用。 此后，控制权转移到Block-1 。

4.4区块1

搜索分支形成的开始。 我们以位于棋chess上的k个皇后为起点。 需要继续完成此组合并将皇后区放置在棋盘上，直到其总数等于baseLevel2为止 。 这里使用的算法称为randSet＆randSet 。 这是由于以下事实：我们在这里不断比较两个随机的索引列表，以寻找没有对应对角线限制的对。 为此，执行以下操作：

a）形成两个列表：一个自由行索引列表和一个自由列索引列表；

b）随机重新排列每个列表中的数字；

c）在一个循环中，每对连续的值对（i，j） ，其中从自由行索引列表中选择索引（i） ，从自由列索引列表中选择索引（j） ，被视为潜在的皇后位置，并检查是否对角线例外的投影区域中的位置。

如果不违反对角线例外规则，则认为该位置正确，并且将女王放置在该位置。 之后，将计数器增加正确安装的皇后区的数量，并更改控制阵列的相应单元。 如果位置（i，j）落入由先前建立的皇后区形成的对角线限制区域，则没有任何变化，并且过渡到考虑下一对值。

当列表中所有对的比较周期完成时，然后，根据对角线排除区域中的其余索引，再次形成剩余空闲行和空闲列的索引列表，并重复此过程，直到正确放置的皇后总数（totPos ）将不等于或超过baseLevel2的限制值。 一旦满足此条件，控制权就会转移到Block-2 。 如果发现由于寻找解决方案而导致的情况是，从剩余的空闲行和空闲列的整个索引列表中发现，没有一个对适合女王/王后的位置，那么在这种情况下，将根据先前生成的副本恢复控制数组的原始值，控制权将转移到Block-1的开头进行重新计数。

4.5第2区

该块用作过渡到块3的准备阶段。 在此级别上，剩余的自由行数（ freeRows ）明显少于n 。 这使您可以将事件从大小为nxn的原始矩阵传输到大小为L的矩阵（1：freeRows，1：freeRows） 。 此外，基于关于原始解矩阵中剩余的空闲行和空闲列的信息，将零写入阵列L的相应单元中，指示这些单元是空闲的。 通过这种“投影”过渡，新矩阵的行和列索引与原始矩阵的相应索引的对应关系得以保留。 重要的是要注意，尽管在解决此问题的过程中，所有事件都在大小为nxn的原始矩阵上展开，并且这样的矩阵是主要的活动场所，但实际上并没有创建此矩阵 ，而仅控制占行索引A（1：n）和此矩阵的B列（1：n） 。

与L数组一起，在此块中还形成了两个工作数组rAr（1：freeRows）和tAr（1：freeRows） ，以保存控制数组D1和D2的相应索引。 这是由于以下事实：当我们在大小为nxn 的初始矩阵的像元（i，j）中安装下一个皇后时，然后我们必须排除落入原始``大''数组对角线例外投影区域的数组L的像元。 由于对角线约束的控制仅在大小为nxn的原始矩阵内执行，因此工作数组rAr和tAr的存在使我们能够保持对应关系并将禁止的单元格转换为数组L的边界。这大大简化了排除位置的核算。
在完成该块中的准备工作之后，将创建主阵列的副本以在此级别上重复使用，并将控制权转移到Block-3 。

4.6方块3

在此块中，根据上一个块中准备的数据继续进行求解搜索分支的形成。 正确设置了皇后的行数等于或大于baseLevel-2 。 您需要继续选择，直到安装的皇后数量等于baseLevel-3为止 。 在这里，我们使用rand＆rand解决方案搜索算法，即 为了形成女王的位置，而不是使用自由索引列表，仅使用两个索引，一个自由行的随机索引值和该行中一个自由位置的随机索引值。 循环重复此过程，直到放置的皇后总数等于baseLevel-3的值为止 。 满足此条件后，控制权立即转移到Block-4 。 如果作为计算结果，搜索分支变成死胡同，则关闭搜索分支形式的这一部分，并返回到Block-3的开头，从此处再次重复计算。 为此，将还原所有控制数组的初始值。

4.7方块4

在此块中，准备了将控制权转移到块5的数据 。 到此步骤，在完成块3中的过程之后，空闲行数（ nRow ）变得更少了。 因此，将事件从较大的数组转换为较小的数组也是有益的。 这种方法使我们有机会快速确定在此阶段需要的其余生产线的必要特性。 特别重要的事实是，基于这样的阵列，可以在不完成计算的情况下预测搜索分支前进许多步的前景。 条件很简单。 如果发现剩余的空闲行中有一条没有空闲位置的行，则所考虑的搜索分支将关闭，控制权将转移到较低级别的块之一。 此处执行的准备操作在很大程度上与Block-2中的操作类似。 基于自由行和自由列的原始索引，形成一个新的二维数组，其零值对应于原始解决方案矩阵中的自由位置。 另外，在此块中创建了一个特殊的数组E（1：nRow，1：nRow） ，根据该数组，您可以确定如果选择位置（i，j）设置女王/王后将要关闭的剩余空闲行中的空闲位置数。源矩阵。 在将控制权转移到块5之前，执行以下操作：

a）确定所有剩余行中的空缺职位数量，

b）对于有问题的行，其空缺头寸数量的数组按升序排序，

c）如果所有剩余的空闲行都具有空闲位置（即，此排序列表中的最小值不同于0），则控制权转移到Block-5。

如果发现在其余任何行中都没有空闲位置，则根据存储的副本还原必要的数组，然后根据任务的参数将控制转移到基本级别之一。

d）形成此第4级所有控制阵列的备份副本。

4.8区块5

这个阶段是最后的阶段，此处搜索分支的形成更加“平衡”和“合理”。 这是“最后一英里”，仅剩下少量的免费线路。 但是同时，这是最困难的部分。 总体上，在寻找解决方案的分支的形成的先前阶段中可能已经犯下的所有错误，都以该行中缺少自由位置的形式出现。

该块的算法基于两个嵌套循环执行，在其中执行第三个循环。 第三个循环的一个特点是可以重复执行，而无需更改两个外部循环的参数。 如果生成的搜索分支处于死锁状态，则会发生这种情况。 此类重复的数量不超过repeatBound的边界值，其最佳值是根据计算实验确定的。

外循环索引与行索引的顺序选择相关联，这些行索引在第三基本级别进行计算后仍然保持空闲。 这是根据先前排序的行列表（通过该行中的空闲位置的数量）完成的。 选择从一条线开始，该线具有最少的自由位置，然后在后续步骤中按升序排列。 在此循环内，形成第二个循环，该循环的索引通过所讨论行中所有空闲位置的索引。 第一个循环的目的仅是选择该级别上空闲线之一的索引。 因此，第二个循环的目的仅仅是在所考虑的行中选择一个自由位置。 这些操作仅在第三基本级别上发生。 选择此选项后，安装的皇后数量将增加，并且所有控制阵列的相应单元也将更改。 此外，控制在嵌套（第三）循环内转移，该循环的活动区域已经是所有剩余的自由线。 在此循环内，将根据以下规则执行行索引的选择和该行中自由位置的选择：

a） 选择一条空闲线路 。 考虑所有剩余的自由行，并确定每行中的自由位置数。 选择该行的空闲位置数量最少。 这样可以最大程度地减少与以下可能性有关的风险：排除剩余的某些行中的最后一个空缺职位，这些状态对于空缺职位的数量而言是最小且至关重要的（ 最小风险规则 ）。 顺便说一句，牢记这一规则是，在第五个块中的第一个循环的索引始于对行的顺序选择，其中行的空闲位置数为最小值。 如果在某一步骤上发现这两行具有相同的最小空缺职位数，则将随机选择排名列表中最先列出的两个职位之一的索引。 如果具有相同的最小空闲位置数的行数大于2，则将随机选择排名列表中最先列出的三个位置之一的索引。

b） 连续选择自由位置 。从所讨论的行中所有空缺位置的列表中，选择一个对所有其余行中的空缺位置造成最小损害的设备。这是在先前生成的数组E的基础上完成的。“最小损坏”是指在给定行中选择这样的位置，该位置排除了所有其余行中最少的自由位置（最小损坏规则））如果事实证明，根据损坏标准，一行中的两个或多个空闲位置具有相同的最小值，则将随机选择列表中最先列出的两个位置之一的索引。选择一个在剩余行中排除最少数量自由位置的位置可以最大程度地减少与女王位置在该位置相关的“损坏”。使用这两个规则，可以在形成搜索分支的每个步骤中更合理地使用资源。如果所讨论的组合物具有解决方案，这将大大降低风险，并增加选择任意组合物成为完整解决方案的可能性。如果在解决方案的某个步骤中发现在要考虑的其余行之一中没有空缺位置，则关闭此搜索分支。在这种情况下，基于备份，将还原所有控制阵列，并且如果重复次数计数器不超过限制值repeatBound，然后在不更改第一外部循环和第二外部循环的索引的情况下，再次重复第三嵌套循环的工作。这是因为在相关标准的最小值一致的情况下，我们进行了随机选择。在基本级别的相同条件下重新形成搜索分支可以更有效地利用此级别提供的“启动资源”。限制第三个嵌套循环的重复启动次数，如果超出极限值，则该循环的操作将中断。之后，恢复控制数组的值，并将控制转移到第三基本级别的循环以转到下一个索引值。循环重复此过程，直到获得完整的解决方案，或者事实证明我们在此基本级别上使用了所有自由行和这些行中的所有自由位置。在这种情况下，根据在各个基本级别上重复计算的总数，并考虑决策矩阵的大小和构图的大小，可以返回到较低的级别之一进行重复计算，或者判断为所讨论的构图不能配备完整的解决方案。在程序中，为了限制账单的总时间，程序被接受或做出判断，直到完成一个完整的决定才能完成所涉及的构图。在程序中，为了限制账单的总时间，程序被接受或做出判断，直到完成一个完整的决定才能完成所涉及的构图。在程序中，为了限制账单的总时间，程序被接受无论返回的是先前的哪个级别，都可以执行不超过totSimBound次的Back Tracking。基于计算实验针对n的各种值选择该边界值。

5.选择算法的有效性分析

randSet和randSet算法的效率。为了分析该算法的功能，进行了计算实验，其中包括在存在randSet和randSet模型的情况下将皇后区放置在解决方案矩阵中。一旦搜索分支达到死胡同，或获得了完整的溶液，就确定了组成尺寸，溶液时间，并再次重复了测试。对n个值的整个基本列表进行了计算实验。值n =（30，40，...，90，100，200，300，500，800，1000）的重复测试次数等于一百万次，对于剩余值，测试次数随着n的增加而增加，从100000逐渐减少到100。对计算实验结果的分析使我们得出以下结论：

a）仅由于randSet和randSet过程的第一个循环，平均正确放置了所有皇后区的60％。对于n = 100，正确放置的皇后数为60.05％。随着n值的增加，该值逐渐减小，对于n = 10 ^7，其值为59.97％。

b）无论决策矩阵n的大小如何，获得的组合物的长度值分布的直方图都具有相同的形式。此外，它们都具有特征-分布的左侧（至模态值）与右侧不同。在图2中，作为一个例子，示出了对应的直方图


所示。 2. randSet和randSet模型（n = 100，样本大小= 10 ⁶）的各种长度的溶液分布的直方图。

n = 100。似乎直方图是从两个不同事件的频率分布中收集的，因为分布的左右部分中事件发生的频率不同。为了描述这种分布，最有可能适合使用正态分布密度的两个函数，其中一个覆盖模态值的间隔，另一个覆盖模态值之后的间隔。

c）基于该算法的决策矩阵中可以设置的皇后数（qMean）的平均值随n增加。从图3中可以看到，其中显示了qMean / n比值与矩阵大小n的依赖关系图，该比值随矩阵大小的增加而增加。例如，

图3.比率qMean / N的值的Ñ为矩阵尺寸的各种解决方案。模型是randSet＆randSet，qMean是解决方案长度的平均值。

如果对于大小为100x100的矩阵，选择位置的算法为randSet和randSet允许“不停”将皇后区平均放置在89行上，然后对于1000x1000矩阵，此类行的数量平均增加到967。d

）基于randSet和randSet算法，您可以获得完整的解决方案，但是这种方法的“生产率”极低。从图4可以看出，对于


图。 4.随着n的增加，在randSet和randSet模型中获得完整解的可能性降低。值n = 7，获得完全解的概率为0.057。此外，随着n的增加

获得完整解的概率迅速降低，渐近接近零。从值n = 48开始，获得完整解的概率约为10 ^-6。在阈值n = 70之后，对于后续的n值，未获得一个完整的解决方案（测试数量等于一百万）。

e）randSet和randSet模型以很高的速度生成搜索分支。对于n＝ 1000，获得组成的平均时间为0.0015秒。组合物的平均长度为967。因此，对于n = 10 ⁶平均时间为2.6754秒，平均歌曲长度为999793。f

）除很小的间隔n <= 70外，当randSet和randSet模型在极少数情况下可以得出完整的解决方案时，在所有其他情况下，决策分支都以否定乐曲结尾。在完成解决方案之前无法完成。所以randSet和randSet算法它具有一个重要的优点-搜索分支的形成速度很高，并且一个显着的缺点是，如果合成物的大小超过某个阈值，则此算法会导致形成合成物，直到完成完整的求解。为克服此缺点，当达到阈值baseLevel-2时，我们停止了搜索分支的形成。rand＆rand

算法的效率。为了确定rand＆rand算法的功能，对n值的基本列表进行了相当详细的计算机仿真。与randSet和randSet模型一样在大多数情况下，重新测试的次数等于一百万。对于其他值，测试数量从100,000逐渐减少到100。

这两种算法均基于随机选择的原理。因此，应该期望这里得出的结论与为randSet和randSet模型制定的结论基本上相同。但是，它们之间有根本的区别，它包括以下内容：

a）rand＆rand模型不像randSet＆randSet模型那样“困难” 。如果我们谈论一些“合理利用所提供的机会的指标”，那么rand＆rand模型每一步都更加合理地使用资源。这导致这样一个事实，例如，在n = 30时，在此模型中获得0.00170的完全解的概率是randSet＆randSet模型的相似值0.00011的15倍。另外，在此，直到阈值n = 370，仍保留了在一百万次测试中获得至少一个完整解的可能性。在此阈值之后，对于n的后续值（测试数量等于一百万），在rand＆rand模型的基础上没有获得一个完整的解。

b）该算法比randSet和randSet算法要慢得多。如果是n = 1000以生成大小为967的合成，获得一个合成的平均时间将为0.0497秒，这比randSet和randSet模型的相应值0.0015多33 。

两种基本相似的随机选择方法之间存在差异的原因是由于在randSet和randSet模型中，为了加快计算速度，并未在每个步骤中从其余列表中进行随机选择。而是从两个列表中顺序选择一对索引，它们的元素被随机重新排列。这样的选择并不是完全随机的，但是，它很适合问题的逻辑，可以让您快速地进行计数。

直观地演示rand＆rand算法的操作，则进行了以下实验：

a）对于大小为100x100的棋盘，在女王/王后在任意行中的位置的每一步之后，确定其余所有空闲行中的空闲位置数。因此，在解决问题的每个步骤之后，我们都会收到一个空行列表和一个相应的空行数量列表。这样就可以构造一个图表，其中所讨论的矩阵的列的索引沿横坐标轴绘制，剩余的自由位置数沿纵坐标轴绘制。为了进行比较，还对职位的顺序选择模型进行了计算。顺序选择是指以下内容。考虑第一行，其中选择了列表中的第一自由位置。然后，考虑第二行，其中还选择了列表中的第一自由位置等。在图5和6中


图5.减少放置皇后后剩余空闲线中的空闲位置数。顺序定期选择职位。

给出了与正在考虑的模型相对应的结果。为了清楚起见，该图仅显示步骤（10、40、60）之后的结果。对于顺序选择位置的模型，最后一个是第62步之后的图形，因为搜索分支由于第63行中缺少自由位置而终止。另一方面，在rand＆rand模型中，最后一张图是在放置皇后的第70步之后显示的，尽管在这里，正确放置的皇后的平均数目达到89，比顺序模型多了26步。rand＆rand模型中图形的奇异视图由于行索引是在剩余的空闲行中随机选择的，因此它们在整个求解矩阵中是随机分散的。这两个图的比较表明，在头寸选择的顺序模型中，自由头寸数量的变化范围大于rand＆rand模型。这是由于以下事实：在常规选择中，对角线约束会不均匀地排除其余行中的自由位置，这导致以下事实：在某些行中，空位数量的减少率高于其他行。


图6.放置皇后后，减少剩余空闲线中的空闲位置数。定位模型为rand和rand。

相反，在自由行索引和自由列索引的随机选择下，女王的位置均匀分布在决策矩阵的“区域”上，从而降低了剩余行中自由位置数量的“平均”减少率。因此，考虑到rand＆rand算法的功能，我们在程序中使用它来继续形成解决方案搜索分支，直到达到baseLevel-3级别为止。

应该注意的是，即使选择算法（randSet和randSet，rand＆rand）不是那么有效，在开发算法时我们仍然必须使用其他随机选择方法。这是由于问题的陈述所致。n-皇后完成问题。如果我们想象有一个解决该问题的最佳算法，那么在输入时，这种算法将始终接收到行和列索引的某个随机集合。每次都会有来自各种可能性的一组新的随机行和列索引集。为了能够“接受”算法中的各种随机成分，必须在随机选择的基础上构建算法本身。匹配应该像一把锁的钥匙。如果我们根据此原理构造算法，则来自k的任何一致组成皇后将被视为决策周期中的初始（开始）位置。而且，目标仅是继续形成寻找解决方案的分支，直到找到给定成分的解决方案，或者证明不存在这种解决方案。

6.使用最小风险规则的示例（n = 100）

在寻找解决方案的初始阶段，当行中空闲位置的数量不是关键时，那么选择空闲行的索引或该行中位置的索引并不是致命的。但是，在最后阶段，当某些行中的空缺职位数为1或2时，在这种情况下，您应该选择其他选择算法。在此级别上，随机选择算法randSet＆randSet和rand＆rand将不再起作用。

下面的简单示例可以解释随机选择算法不起作用的原因。在某个问题的解决步骤中，对于其余任意行i ₁，i ₂，...，i _k为n的任意值空位的数量（在方括号中表示）为：i ₁（1），i ₂（2），i ₃（4），i ₄（5），i ₅（3），i ₆（4）等。如果您随机选择任何行，但没有选择第i ₁行，而其中只有一个自由位置，则当与所选行中女王/王后位置相关的对角线禁止会导致该行中唯一自由位置的关闭时，可能会导致风险情况i ₁，这将导致解决方案陷入僵局。在所有行i ₁，i ₂，...，i _k对行索引的选择最脆弱和最敏感的是第i ₁行。在这种情况下，您应该首先选择状态最关键的行，这会带来解决问题的风险。因此，在解决问题的最后阶段，在每个步骤中，都必须基于最小风险的简单算法来选择生产线的位置。

为了清楚起见，让我们以一个100 x 100矩阵为例，它是第88步之后形成真实解的最后阶段。在任务完成之前，还剩下12条空行，每个空行都找到了空缺职位（这些行按空缺职位的数量递增顺序排列）：步骤89-25（1），12（2），22（2），82（2），88（2），7（3），64（3），3（4），76（4），91 （4），4（5），96（5） -表示自由线的索引，括号中-表示该行中自由位置的数量。根据最小风险规则，在解决问题的第89步中，选择第25行，并选择其中的一个自由位置。重新计票的结果是，我们还有11条空闲行：Step-90-7（2），12（2），22（2），82（2），88（2），3（3），64（3）， 76（3），4（4），91（4），96（4）。如您所见，前五行中的空闲位置数量相同且等于2。因此，前三行之一的索引是随机选择的。在这种情况下，选择了第12行，而这两个行的位置仍保留在该行中，因此损害最小。因此，在溶液形成的第91步中，我们有10条自由线：步骤91-22（1），3（2），7（2），82（2），88（2），64（3） 76（3），91（3），4（4），96（4）。在此步骤中，选择了第22行以及其中的一个自由位置。以类似的方式继续，形成了以下决策序列（表1）。所选行的索引以粗体显示。

在此特定示例中，在12个案例中有11个出现了这样的情况：在剩余的空闲行列表中，至少有一行仅保留一个空闲位置。如果我们不使用最低风险规则，那么我们将无法解决问题。由于在选择自由线的索引时出现“错误的举动”，因此很可能导致销毁剩余自由线之一中唯一的自由位置。这就是为什么仅使用randSet x randSet或rand x rand算法获得完整解决方案的原因，在最后阶段，解决方案将走到尽头。
应该注意的是，最小风险算法具有简单的日常含义，并且经常用于决策中。例如，医生首先对病情至关重要的病人进行手术，同样地，农民在严重干旱期间试图保存农作物，首先浇灌那些病情最严重的地区...

7.算法效率分析

为了评估各种n值算法的效率，进行了相当长的（就总时间而言）计算实验。最初，开发了一种相当快速的算法，用于生成任意值n的解决方案数组nQueens问题。然后，基于该程序，为n值的基本列表形成了较大的解样本。对于各个n值，分别获得的nQueens问题解决方案样本的大小相等：（10）-1000，（20，30，...，90，100，200，300，500，800，1000，3000，5000，10,000）- -10000，（30000，50000，80000）-5000，（105，3 * 105）-3000，（5 * 105，8 * 105，106）-1000，（3 * 106）-300，（ 5 * 106）-200，（10 * 106）-100，（30 * 106）-50，（50 * 106）-30，（80 * 106、100 * 106）-20。此处，在方括号中指示了n个值的列表，并且双破折号指示了获得的溶液的样本量。之后，基于溶液的每个样品形成任意大小的无规组合物。例如，对于n = 1000的10,000个溶液中的每一个，形成了100个任意大小的随机组合物。结果是一百万首歌曲的样本。由于在现有解决方案的基础上形成的任意大小的成分都可以至少完成一次，直到完成一个完整的解决方案，因此任务是基于n皇后完成问题解决方案算法，完成从生成的样本到完整解决方案的每个成分。由于在所考虑的算法中，每一步都检查了皇后在棋盘上的正确放置，因此原则上不能在溶液的每个样品的基础上形成任意大小的无规组合物。例如，对于n = 1000的10,000个溶液中的每一个，形成了100个任意大小的随机组合物。结果是一百万首歌曲的样本。由于在现有解决方案的基础上形成的任意大小的成分都可以至少完成一次，直到完成一个完整的解决方案，因此任务是基于n皇后完成问题解决方案算法，完成从生成的样本到完整解决方案的每个成分。由于在所考虑的算法中，每一步都检查了皇后在棋盘上的正确放置，因此原则上不能在溶液的每个样品的基础上形成任意大小的无规组合物。例如，对于n = 1000的10,000个溶液中的每一个，形成了100个任意大小的随机组合物。结果是一百万首歌曲的样本。由于在现有解决方案的基础上形成的任意大小的成分都可以至少完成一次，直到完成一个完整的解决方案，因此任务是基于n皇后完成问题解决方案算法，完成从生成的样本到完整解决方案的每个成分。由于在所考虑的算法中，每一步都检查了皇后在棋盘上的正确放置，因此原则上不能形成了100个任意大小的随机组合物。结果是一百万首歌曲的样本。由于在现有解决方案的基础上形成的任意大小的成分都可以至少完成一次，直到完成一个完整的解决方案，因此任务是基于n皇后完成问题解决方案算法，完成从生成的样本到完整解决方案的每个成分。由于在所考虑的算法中，每一步都检查了皇后在棋盘上的正确放置，因此原则上不能形成了100个任意大小的随机组合物。结果是一百万首歌曲的样本。由于在现有解决方案的基础上形成的任意大小的成分都可以至少完成一次，直到完成一个完整的解决方案，因此任务是基于n皇后完成问题解决方案算法，完成从生成的样本到完整解决方案的每个成分。由于在所考虑的算法中，每一步都检查了皇后在棋盘上的正确放置，因此原则上不能那么任务就是根据n皇后完成问题解决方案算法，从生成的样本中完成每个构图，最后完成一个完整的解决方案。由于在所考虑的算法中，每一步都检查了皇后在棋盘上的正确放置，因此原则上不能那么任务就是根据n皇后完成问题解决方案算法，从生成的样本中完成每个构图，最后完成一个完整的解决方案。由于在所考虑的算法中，每一步都检查了皇后在棋盘上的正确放置，因此原则上不能错误的积极决定（即我们错误地认为正确的错误决定）。但是，可能会有False Negative解决方案-如果在解决方案完成之前，程序无法完成基于现有解决方案形成的任何组合物（尽管我们知道所有组合物都有解决方案）。在如此广泛的n值范围内进行计算实验，我们为自己设定了以下目标：

a）确定算法的时间复杂度，

b）确定n的各个值的假阴性解的概率，

c）确定使用反向跟踪程序进行测量的频率n的不同值。

表2列出了这种计算实验的结果。

根据获得的结果可以得出的一般结论如下：

a）该算法工作足够快。例如，基于一百万次计算实验获得的1000 x 1000大小的棋盘的任意合成物的平均编译时间为0.062157秒。这意味着，如果合成物有溶液，则可以在按“ Enter”键后立即找到它。对于所有n值，范围从7到30,000，任意合成的平均编译时间不超过一秒钟。

b）在每个样品中，大约有10％的组合物需要更多的时间才能完成。这样的组成在分布直方图中形成了一条长长的右尾。如果我们排除这10％的成分，并对其余90％的溶液进行计算，那么计算时间（t90 _平均值）将大大减少。例如，对于1000 x 1000的棋盘，平均计数时间将为0.027727秒，比从整个样本获得的平均时间少2.24倍。

c）对于n≤800的值，在组合物样本中存在直到完全解决才完成的值。这是假阴性决定。在程序指定的限制内，允许执行多达1000次的“ 回溯”过程，该算法未能完成这些合成。他们被错误地归类为负面作品，即那些没有解决方案的人。此类假阴性解决方案的数量微不足道，并且它们在样本中的份额小于0.0001。此外，随着n的增加，假阴性解的比例会减少。对于所有n > 800的值，在该系列计算实验中，没有一个假负解的情况。但是，很明显，如果样本数量增加很多倍，则不会排除出现假阴性的可能性。解决方案，尽管发生此类事件的可能性很小。

该算法的时间复杂度。图7示出了对于各种n值的随机组合物的平均拾取时间的变化图。


图7. 随机成分的平均选取时间（t）与决策矩阵大小（n）的关系。n

值的十进制对数绘制在横坐标轴上，平均计数时间增加1000倍的对数绘制在纵坐标轴上。为了清楚起见，该图还显示了象限对角线的虚线。可以看出，拾取时间随着n的增加而线性增加。在n从50到10 ⁸的整个范围内计数时间的实验值形成一条直线，其线性回归方程log（1000 * t）=-0.628927 + 0.781568 * log（n）具有较高的相关性（R = 0.9998），仅当值n =（ 10，... 49），这是由于在该范围内仅使用第五个计算块来解决该问题，该算法的算法与第一个和第三个块的算法明显不同。在得出的相关性中，线性系数（0.781568



）小于1，这导致以下事实：随着n值的增加，回归线和象限的对角线发散。为了清楚地说明这种差异的原因，而不是最初的时间，我们考虑将一位女王/王后排成一行的平均时间。将平均计数时间除以n。我们称这种指标为减少时间。显然，如果减少的时间不随n的增加而变化，则这样的解将是线性的（O（n））。如所看到的在图8中，对给定的时间，对数的，其中的曲线


图。 8平均时间依赖性（t _行），这对于将女王/王后从求解矩阵的大小（n）定位在任意一条线上是必需的。

（tRow）从溶液矩阵大小的对数增加10 ⁶倍，在n从50到10 ⁸的范围内，减少的时间随着n的增加而减少。如果n = 50的减少时间为10.7146 * 10 ^-6秒，则n = 10 ⁸的对应时间^将减少21次，为0.5084 * 10 ^-6秒。乍看之下，这种算法的行为似乎是错误的，因为没有客观的原因，为什么对于n的小值，算法认为它比大的值要慢。但是，没有错误，这是该算法的客观属性。这是由于以下事实：该算法是三种以不同速度运行的算法的组合。而且，由这些算法中的每一个处理的行数随着n值的增加而变化。由于这个原因，计数时间在值n =（10，20，30，40）的初始范围内增加，因为在这个小区域内的所有计算仅基于第五步程序进行，该程序非常有效，但速度不如第一步程序。因此，考虑到将皇后放在一条线上所需的计数时间，随棋盘大小的增加而减小，这种算法的时间复杂度可以称为减小-线性。

使用反向跟踪（BT）的次数。在计算实验的所有案例中，我们使用BT程序跟踪了解决每个问题的案例数。不管使用何种BT返回解决方案，都对使用BT的所有情况进行了累积求和。这使我们有机会为每个样本确定从未使用BT程序的那些决策的比例。图9显示了


图。 9.从未在

图表中使用“回溯”过程的样本中的决策比例，该图表显示了不使用BT（零“回溯”过程）而解决方案的案例比例如何随着n的增加而变化的情况。。可以看出，在值n =（7，...，100000）的范围内，从未使用BT程序的解决方案数量超过35％。此外，在值n ＝（320，...，22500）的范围内，这种情况的数量超过50％。对于大小为5000 x 5000的棋盘，获得了最有效的结果，其中在10,000个成分的样本中，在61.92％的情况下，执行了非确定性问题的“确定性”解决方案，因为BT程序占61.92％案件从未使用过。在其余的解决方案中，在21.87％的情况下，使用了BT程序1次，在9.07％的情况下使用了2次，在3.77％的情况下使用了3次。一起，占案件的96.63％。在值n = 5000之后，不使用BT程序解决配置问题的情况逐渐减少的事实与选择模型有关，该模型用于选择baseLevel2和baseLevel3的边界值。您可以更改这些参数，并且无需使用BT程序即可增加解决方案的数量。然而，这将导致计算时间的增加，因为第五块对算法操作的参与将增加。

时间分配分布的直方图。在图10中，对于n = 1000的值给出了一百万个解决方案的选取时间分布的直方图。分布直方图的视图不是很普通（很可能类似于高层建筑的夜间轮廓），与间隔长度或间隔数选择中的错误无关。这是该算法的自然属性。要了解，


图。 10.任意大小组成的汇编时间的直方图。 （n = 1000；样本大小= 1,000,000）

为什么直方图具有这种形式，请考虑具有相同大小的组合物的选取时间分布。为此，举例来说，我们将从初始样本中选择大小为800的所有成分。一百万个样本中有998种成分。图11展示了该样品的计数时间分布的直方图。从图中可以看出，分布由六个独立的直方图组成，并且大小逐渐减小。


图11.相同大小的组合（k = 800）的编译时间的直方图。 （n = 1000；样本大小= 998）

之所以将998个作品的编译时间（其中每个800个皇后随机分配）的时间“汇总”为6组，是因为使用了Back Tracking程序。图中的第一个直方图具有最大的样本量，是从未使用过BT程序的那些拣选解决方案。这是一组最快的解决方案。第二个直方图的大小明显小于第一个直方图，是那些仅使用BT程序一次的解决方案。因此，该组中的决策时间比第一组中的决策时间稍长。因此，在第三组中，BT程序被使用了两次，在第四组中被使用了三遍，等等。较长时间执行了重复使用BT程序的决策。这样的解决方案形成了所需分布的右长尾。

错误的负解。如果我们将所有可能的成分除以n的任意值从正数到负数，则在正数构成中有一些可以被该算法归类为负数。这是由于以下事实：在搜索参数设置的限制内，算法找不到正确的方法来完成此类合成。如实验结果（表2）所示，此类情况的数量不超过样本量的0.0001，并且该误差的值随n的增加而减小。另外，对于所有n> 800的值，没有一个假负解的情况。即使在n = 1000的情况下将样本量增加到一百万，也不会导致假阴性决定。结果使我们能够制定以下规则来解决该问题：“任何连续地分布在大小为nxn的棋盘上的k个皇后区的随机组成都可以完成，直到提出完整的解决方案为止，否则将确定该组成为负，并且不能待完成。做出此决定的可能性不超过0.0001。随着棋盘的尺寸增加，做出错误决定的可能性减小。该算法的时间复杂度是线性的。”

8.结论

1.提出了一种算法，该算法允许在线性时间内解决完整集的问题，直到k个皇后区的随机组成的完整解，并一致地分布在任意大小nxn的棋盘上。此外，对于任何k个皇后（1≤k <n）的组合，都提供一个解决方案（如果有的话），或者确定该组合无法完成。做出这样的决定时出错的概率不超过0.0001，并且该值随着棋盘尺寸的增加而减小。

2.此算法的操作基于两个重要规则的使用：

a）在解决问题的最后阶段，从所有剩余的空闲行中选择一个空闲位置最少的行（最小风险规则）。这将与排除某些剩余生产线中最后一个空缺职位的可能性相关的风险降至最低。

b）在相关生产线的所有空缺位置中，选择该位置对剩余的自由生产线中的自由位置造成最小损坏（最小损坏规则）。 “ 最小损坏 ”是指在一条线中选择这样一种位置，该位置排除了所有其余自由线中最少的自由位置。

3.已经确定，由于该算法的操作，将女王放置在一条线上的平均时间随着n值的增加而减少。在n为10 ⁸的情况下将皇后放在一行上的平均时间比在n = 50的情况下的相应时间少21倍。

4.发现在值n =（7，...，100000）的范围内，从未使用反向跟踪过程的解决方案数量超过35％。此外，在值n =（320，...，22500）的范围内，此类情况的数量超过50％，这表明该算法的效率很高。

5.提出了组织回溯程序的模型。，基于基础层上决策步骤的分离。等级意味着一定的决策步骤，正确放置一定数量的皇后。给出了用于根据n计算第二和第三基本级别的值的回归公式。

6.给出了两种随机选择方法randSet和randSet以及rand＆rand的比较分析结果。据该算法发现randSet＆randSet快速而粗糙。因此，在达到第二基本级别时，其使用受到限制。之后，使用rand＆rand算法。，执行速度不是很快，但可以更有效地将皇后放在棋盘上。

7.给出了一种验证n-Queens问题解的正确性的有效算法。该程序还旨在验证任意大小的随机成分的正确性。该程序运行足够快。例如，验证包含500万个职位的解决方案所需的时间为0.85秒。

9.评论

1.如本文开头所述，在n值范围内（从7到1亿）进行了研究。但是，该程序已在n值（最多10亿）的更宽范围内进行了测试。的确，在后一种情况下，鉴于数组的大小，该程序必须稍作调整。因此，如果RAM的大小允许，则可以对大的n值进行计算。

2.优化基线指标的值以及各个级别重复次数的边界值，以解决整个研究范围内的问题。可以在较小范围内更改它们，并减少计数时间。重要的是不要增加误报解决方案的份额。

3.在本文中，我使用Enter键按下时间作为时间量度，以评估算法的运行速度。如果结果在按下键后立即出现，则在用户感知的级别上，该程序似乎“非常”快速地工作。无论该算法以多快的速度运行，在完成按键之前，结果都不会出现在屏幕上。因此，在我看来，这种时间的条件度量可以用作阈值级别，用于不严格比较各种算法的速度。

4.哲学...在研究过程中，考虑了许多与解决非确定性问题有关的出版物。在大多数情况下，这些任务需要在给定限制条件下在很大的国家空间中做出选择。比较它们，很有趣的是知道使用标准数学方法可以解决这些问题的程度。我的印象是，仅根据定义，引理陈述和定理证明不可能解决这些问题。在我看来，要解决此类问题，有必要使用通过计算机仿真的算法数学方法。为了证明此结论的有效性，作为一个简单示例，我准备了一个大小为10的棋盘⁹ x 10 ⁹两个相同大小的合成，包括999,999,482个皇后。它们按照本文开头所述进行准备，并以.mat格式显示为两个文件。可以从此链接下载它们（两个测试文件）。文件非常“繁重”，每个文件的大小约为3.97 Gb。在999 997 976行（在99.9998％的情况下）中，两个组合中的皇后位置都重合，并且仅在任意1506行中，皇后的位置不同。

要完成构图数据以获得完整的解决方案，您需要将皇后区正确放置在其余518条自由行中。在剩余的空闲行中排列518个皇后的可能方式的数量（仅考虑在所选行中选择空闲位置的方式的数量）约为10 ¹⁴⁶⁶。这两种成分之间的区别仅在于，其中一个成分为正，可以完成直到完全溶解，而另一个成分为负-直到完全溶解才可以完成。问题：“是否有可能基于严格的数学方法（即不执行算法计算操作）来确定这两个组成中的哪个为正？”如果这无法解决，则我们可以假设所提出的命题是矛盾的。

我要指出的是，无论采用什么数学方法严格解决这个问题，都必须确定状态518 * 10 ⁹剩余的空闲行中的单元格。为此，有必要考虑先前设立的女王/王后的每个职位，并且几乎有十亿个女王/王后，以便确定每个设立的女王/王后对其余518行中的自由职位施加的限制。我没有找到一个“支点”，只能在严格的数学方法的基础上进行这项工作，而无需进行算法计算。

我在这里给出了一个仅包含两个组成部分的最小示例。如果需要，可以增加这种组合物的数量。

应该注意的是，在提出的线性算法的基础上，该算法略微适合于处理大型合成，可以完成两个测试合成中的哪一个的任务，直到在Desktop-13上执行完整的解决方案为止 ，大约需要4.5分钟（不包括输入数据加载时间）。

10.加法

教授建议有能力的任务供学生发展和研究的教授的举动值得尊重。这需要付出巨大的努力，但要克服困难，研究人员对其他复杂任务的看法有所不同。我认为为此类目的扩展设置n皇后问题的选项将很有用。如果从不同的角度看待同一任务，您会看到不同的事情。以下是其中一些。

1.考虑在大小为nxm的矩形“象棋”板上布置n个皇后的问题。表示k = m-n。假设得到了一些解决方案，并且每个的Ñ每行有一个女王。我们不再考虑皇后所在的位置。现在每行有m-1个自由位置。在剩余的空缺职位中，我们再次找到一个解决方案。和以前一样，我们不再考虑第二个解决方案的皇后所在的位置。现在每行有m-2个空缺职位。显然，第一和第二解在任何行中的位置都不相交-它们是正交的。需要确定各种k值的相互正交解的最大数量。如果找到n个相互正交的解，其值k = 0然后将建造皇家拉丁广场。

备注。纸张Grigoryan的E.（2018）表明，对于任何解决方案正皇后问题有一种补充的解决方案，其不干扰它。这意味着对于n的任意值，n -Queens问题的所有解的集合被分为两个相等大小的子集。来自第二子集的任何解决方案都是对来自第一子集的相应解决方案的补充解决方案。规则很简单，如果Q1（i）是第一组的解，则对应的互补解Q2（i）通过公式Q2（i）= n + 1-Q1（i）确定第二个子集中的i，其中i =（1，...，n）。正是这个规则解释了以下事实：对于n的任意值，n 皇后问题的所有解的数量始终是偶数。 （这条规则可以让你在任何尺寸的完整解决方案的计算一半的时间削减ñ棋盘。如果我们用2 * K所有的解决方案的总数量，价值ķ等于指数中的所有解决方案的顺序列表，当Q（K）+ Q（ k + 1）= n + 1）。

2.在问题n-Qeens问题的初始表述中，将女王放置在位置（i，j）之后，将执行以下操作：

a）排除第i行和第j 列的

所有单元格； b）排除通过单元格（i，j）的左右对角线上的所有单元格。

我们在问题陈述中更改条件b）。代替消除单元，我们将使用单元切换。如果位于左或右对角线上的单元格是空闲的，则将其关闭；如果该单元格关闭，则将其打开。这样可以更轻松地找到解决方案。但是，我们考虑大小为nx（n-k）的矩形矩阵，而不是正方形矩阵nxn。对于给定的n值，需要找到k的最大值至少可以得到三个正交解。k的值如何随着n的增加而变化？

3.更改n皇后问题问题的初始公式中的某些条件。如果女王/王后位于大小为nxn的棋盘上的位置（i，j）：a）排除第i行中的所有单元格，b）如果索引j为偶数，则：b1）排除第j列偶数行中的单元格，b2）排除第i列中的单元格与左右对角线相交的偶数行穿过像元（i，j），c）如果索引j









奇数，则满足位于奇数行上的单元的项目b1）和b2）。

3.1已知（Sloane-2016）n 皇后问题的所有解决方案的值列表，其中n =（8，9，10，11，12，12，13，14，15，16 ）分别为（92，352，724，2680， 14200、73712、365596、2279184、14772512）。如果在问题陈述中，将对角线例外的标准条件更改为b）或c）段，所有解决方案的数量将如何变化？

3.2 Grigoryan（2018）知道，如果我们确定解决方案矩阵的不同单元参与形成所有解决方案列表的频率，我们会发现所有单元之间都存在对应频率的垂直和水平对称形式的和谐关系。这意味着，如果我们假设k <n / 2，则第k行的单元频率将与行n-k + 1的单元频率相同。类似地，第k列的单元的频率将与列n-k + 1的单元的频率相同。问题：“这些和谐关系在任务范围内将如何变化？”

4.棋盘的所有单元格按其颜色分为两类。据信一种颜色是白色，另一种颜色是黑色。考虑两个棋盘，并将其中一个放在另一个上，以使边缘完全重合。结果，我们从两个棋盘上得到一个“三明治”，白色和黑色单元格的排列重合。任务是在两个板上同时找到解决方案，并遵守以下条件：

a）如果在一块板上，皇后位于索引为（i，j）的黑色单元上，则：

-在两个板上，所有出现的黑色单元在第i行和第j列，

-在两个板上，排除了沿穿过单元（i，j）的左右对角线的所有黑色单元。

b）如果皇后位于一个带有索引（i，j）的白色单元格上，则仅对白色单元格执行a）段的所有操作。

5.想象一下，在大小为nxn的解决方案矩阵中，行可以以k个单元为单位相对于彼此左右滑动。此外，例如，如果前一行向左移动，那么下一行应向右移动，即每行的下一行都与上一行的方向相反。作为这种构造的结果，我们获得了尺寸为1的矩形矩阵。nx（n + k），其中在每行中，从行的开头或结尾开始的k个单元将被排除在外。任务是为任意一个n值找到k的最大值，对于该值至少存在一个解n-Queens问题。
考虑问题的一种变体，其中一条线相对于另一条线的偏移是一个从k1到k2的随机数。

6. nQueens问题的一维表述。让n个任意长度的段（从1到n编号）布置在半轴上。将每个细分除以n任意大小的像元，并且在每个段中，将像元从1到n进行编号。我们称这种细胞为开放的。它要求在每个段靠近一个小区，考虑以下限制：

a）我们可以选择具有索引开孔Ĵ的我个片段，如果：

D1（R）= 0;

D2（t）= 0；

其中，r = n + j-i，t = j + i，D1和D2是一维控制数组，由2n个先前为零的像元组成。

b）选择之后，段i和编号为j的单元格将关闭在所有剩余的免费细分中。还必须关闭控制数组中的相应单元：

D1（r）= 1;

D2（t）= 1；

在此设置下，任务与原始任务完全相同。有趣的是在其他约束条件下解决此问题。例如，如果代替公式：
R =正+ J - I，T = J + I， ，
将被认为是其它比例，这在功能上相关联的索引- [R和吨索引（I，J）的制备基体。

7. 基于带球an的任务措辞（与之前的措辞相同）。假设有n个骨灰盒，编号从1到n，每个中都有n个球，编号也从1到n。需要瓮从每一个球距，考虑以下限制：

a）我们可以选择以数字球囊Ĵ的我个瓮如果：

D1（R）= 0，

D2（T）= 0，

其中R =正+ J -i，t = j + i，D1和D2是一维控制数组，其中包含2n个先前被置零的像元。

b）选择此选项后，所有剩余的免费投票箱中的投票箱i和编号为j的球都将关闭。还需要关闭控件数组中的相应单元格：

D1（r）= 1，

D2（t）= 1。

在此设置下，任务与原始任务完全相同。与前面的情况一样，该问题的陈述还有其他条件，这些条件在功能上将索引r和t与决策矩阵的索引（i，j）连接在一起。

8. 游戏。考虑大小为nxn的棋盘。让我们将颜色返回皇后区，让一些皇后区具有白色，而其他皇后区则为黑色。我们还根据索引为（1，n）的单元格的事实，将黑白交替的颜色返回到棋盘格的单元格应该是白色的。游戏开始时的所有单元格均视为免费。白皇后走出第一步。玩家将女王放置在带有索引（i，j）的任意空闲单元格中。让它成为一个白细胞。由于此选择，它们被关闭：

a）第i行的所有白色单元格，

b）第j列的所有白色单元格，

c）穿过单元格（i，j）的左右对角线上的所有白色单元格。

如果单元格（i，j）变成黑色，则满足所有点（a，b，c），因此，所有黑色单元格均关闭。接下来，布莱克执行移动，将女王放置在任何剩余的自由单元中。之后，如上所述，以类似的方式关闭单元。考虑下一步行动的时间是固定的，并由双方协商确定。如果在指定时间内，其中一个玩家未完成其移动，则将游戏转移到另一个。如果两个玩家，一个接一个，都未能在指定时间内完成回合，则游戏结束。可以在董事会中放置更多皇后的人将获胜。

9.关于稳定性的随机选择。考虑randSet和randSet模型。通过比较n个随机的行和列索引对，在循环的第一阶段，有可能平均建立皇后k * n行。k的值可以被认为是等于0.6的常数。其值从n = 10时的 0.605701变化到n = 10 ^6时的 0.599777 ，并且随着n的增加，该值的方差减小。这种“恒定”的原因是什么？为什么在随机选择行索引和女王/王后在该行中的位置索引时，基于从1到n的数字随机排列而获得的两个数字列表，能否将女王/王后（平均）始终放置在60％的行上？

10.令棋盘的大小为nxn。基于randSet和randSet过程将皇后放在棋盘上，直到搜索分支达到死胡同为止。用k表示由此获得的合成物的长度。如果对于给定的n值，重复此过程多次，并建立k值分布的直方图，那么事实证明，事件发生频率向分布模式值的变化与该值之后事件发生频率的变化不同。如果基于模态值将直方图分为两部分，则左侧部分将与右侧部分不一致。此模式是n的任何值的特征。为什么在成分的长度通过模态值过渡后，事件开始的频率采用不同的形式？所谓事件，是指在陷入僵局之前接受给定大小的组成。

文学作品

1. Nauck，F.（1850）。Briefwechsel mit allen fur alle。 Illustrierte Zeitung，15，182。2

. Gent，IP，Jefferson，C。 ＆Nightingale，P.（2017年）。 n-皇后完成的复杂性，
《人工智能研究杂志》，第59卷，第815-848页。

3. Sosic，R.，＆Gu，J.（1990）。n皇后问题的多项式时间算法。 SIGART公告，1（3），7-11。

4. Richards，M.（1997）。 MCPL中使用位模式和递归的回溯算法。
科技剑桥大学计算机实验室代表。

5. 算法设计中的随机化方法，DIMACS研讨会论文集，美国新泽西州普林斯顿，1997年12月12日至14日。DIMACS系列离散数学和理论计算机科学43，DIMACS / AMS 1999，ISBN 978-0-8218-0916-7

6. Grigoryan E.（2018）。 解n皇后问题形成规律的研究。人工智能建模，5（1），3-21

7. Sloane N.-JA（2016）。整数序列的在线百科全书。