n皇后问题的多项式时间增量解法

×沙特国王大学学报n皇后问题的多项式时间增量解法布内卜·宰因·阿比丁阿尔及利亚乌姆布瓦吉大学计算机科学与数学系阿提奇莱因福奥文章历史记录：收到2022年2023年1月8日修订2023年2月2日接受在线预订2023年保留字：n queens最大集团反链最小集团A B S T R A C T本文证明了利用补数上的符号运算，n皇后图然而，在增量方法中进一步继续，除了n-1解（其表示对应于棋盘n-1的图的补图上的大小为n-1的最大团）之外，我们需要大小为n-2及以下的最大团。通过这样做，我们需要消除反链问题，这增加了算法版权所有2023作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍N皇后问题是一个德国棋手在1848年提出的8皇后问题的推广。N-Queens问题在算法设计中具有挑战性，即使在Gent等人（2017）的完成问题中，离散数学也证明了NP完全。它需要在一个n乘n的棋盘上放置n个皇后，使得沿着任何行、列或对角线都没有两个皇后受到攻击。虽然n皇后问题通常被用作解决组合优化问题的算法的基准，但它已经找到了一些实际应用，包括实际任务调度和分配，计算机资源管理和VLSI测试（P，2011）。计算n皇后问题的解的数量并不容易。由于没有找到已知的精确数学公式，只是近似Luria（2017），Luria和Simkin（2022），解决方案有趣的是，不能保证随着n的增加而增加解的数量。例如，六皇后棋盘的解的数量少于五皇后棋盘的解的数量。27 27板是最高阶的板，在大约一年的时间里，电子邮件地址：bzine19766@gmail.com沙特国王大学负责同行审查有关信息，请参阅网站上的项目Q27使用符号计算，16x16板是使用BDDBryant（2018）实现的最高阶板。只计算一个解可以在多项式时间内完成（Sosic和Gu，1990）。然而，列出所有的解决方案是一个NP完全问题。有几种可能的方法可以找到这个问题的解决方案，从精确低效的穷举计算到使用随机或遗传算法的现代近似解Sarkar和Nag（2018），Eastridge和Schmidt（2008）。列出所有解决方案的一个简单方法是使用Branch and BoundLajtar（2013）进行回溯，这是耗时的。例如，枚举20个Q的解决方案需要几天时间才能完成。将回溯与符号运算相结合，使用按位运算符，可以使计算速度比递归回溯算法Richards（1997），Zongyan（2002）快两个数量级。本文所处理的问题是枚举n皇后问题的所有解。工程师和科学家，在一般情况下，建立数学模型来解决问题，如线性方程，自动机等，其中一个问题可以从不同的角度来看。例如，最大团的对偶问题可以使用图论中的最大独立集来建模。在本文中，我们使用图论建模的n皇后问题，其中的问题可以看作是枚举所有的最大的皇后。根据定义，团是完全子图。如果一个团不是另一个团的真子图，则称之为极大团。最大团集合中最大的团称为最大团.最大集团不是唯一的。即使在近似情况下，枚举所有最大团也是NP完全问题（Khot，2001）。https://doi.org/10.1016/j.jksuci.2023.02.0021319-1578/©2023作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comB.Z. El Abidine沙特国王大学学报2FGFig. 1.八皇后拼图。该文件细胞的编码是n-queen图的补图的Kneser表示。对n皇后问题提出的算法是增量迭代的。增量步骤是从棋盘（n-1）×（n-1）的解计算棋盘n × n的解增量步长的复杂性是多项式的;这个结果与任何工具无关。2. 背景这篇文章的思想首先由Richards（1997），Zongyan（2002）提出，作者指出将逐位算子与回溯相结合可以显著提高回溯算法的运行速度。例如，使用基本回溯算法的14个皇后的时间可以花费5分钟来获得结果。而将基本的回溯算法与位运算符结合起来可能需要半秒钟。本 文 用 Kneser 表 示 作 为 皇 后 图 的 补 图 的 表 示 在 el Abidine（2022）中，作者介绍了Kneser表示，并从总体上说明了精化及其双词抽象在科学和工程中的重要性。此外，他表明，在计算最大团的细化可能有利于设计一个算法的最大团没有递归。当然，递归消除可以通过堆栈数据结构或使用二叉树计算递归调用的路径来完成然而，有时候，我们并不清楚如何克服递归。作者还展示了消除物联网设备递归的重要性，并在n皇后问题上进行了实验。作者表明，对于4皇后，我们需要使用BronKerboschBron和Kerbosch（1973）进行51次递归调用，并且大多数最大团的算法都是递归的，事实上，由于堆栈的大小，物联网设备对递归有限制，特别是微控制器根本不存在。Cavalcanti et al. （2006）是分阶段开发产品的过程，我们逐渐在每个阶段添加有关抽象级别的相关细节。例如，程序员只关注编程语言，而不关心计算机的电路实现。作者在el Abidine（2022）中解释了最大团算法的改进设计的反映结果是它对动态环境的适应性，因为算法是增量的。此外，作者还证明了给定图的Kneser表示是一个2-SAT问题，其中的求解器通常是线性但递归的（Even等人，（1976年），不适用于IoT设备。因此，作者提出了一个迭代算法，以寻找Kneser表示的给定图与n-顶点在线性时间内飞行，但顶点是在两个n比特编码。本文讨论了n-皇后图的补图的特殊性.由于El Abidine（2022）提出的理论可以应用于任何图。细化的一个好处是组合性。例如，古日语不是合成的。如果你让一个日本人写你的名字，他会说我不会。后来，日本人发明了另一种方法来整合他们语言中的组合性相比之下，阿拉伯语是人类的一项伟大发明，因为它是组合的;单词是由字符组成的，短语是由单词组成一般说来，组成在科学和工程学中是重要的.科学不能独立于其他科学，除非它可以分解为电子学和机械学等基本要素。这里提出的算法设计时考虑了组合性，其中n皇后板的解并讨论了为什么不能用多项式时间迭代求解的问题。3. 贡献3.1. 基本定义定义3.1. 设V ^fb1; b2;. ; b mg m的有序有限集元素s，集合P<$V<$是V的所有子集的集合，由V表示并以v1;v2;. 在几何上，我们定义一个图是空间中的一组点（顶点），这些点相互连接。由一组线（边）连接 对于图G，我们用V表示顶点集，用 E 表 示 边集，记为G <$$>V; E<$。边缘ek，记为vi~vj。此外，8vi;vj2V s：t i如果我们将每个B1看作二进制数字它意味bi2B1/4 f 0; 1g.我们有bj2vi）bj¼1其他 b j¼0。 每个顶点vi 将是一个编码它可以映射到N中的一个数。为一完成图的n顶点我们有：V<$fv 1<$fb1g;v 2<$fb2g;. . . ;vn 00. 01; v2 ¼ 00. 10;. ; vn¼ 10. 00 g。 可以清楚地看到，对于所有vi， 而vj i等效于二进制逐位运算v1v1v20。我 们 提 出 的 符 号 表 示 是 基 于Kneser GraphKneser （ 1955 ） 。Kneser图K（m，k）是其顶点对应于m个元素的集合的k个元素子集的图，其中两个顶点相邻当且仅当两个对应的集合不相交。在本文中，我们使用Kneser的表示，sentation在定义。1，其中的定义的图将只是一个子集的自然数。基于定义1的表示已经在el Abidine（2022）中使用，其中找到给定图的表示的问题是2-SAT问题。SAT问题一般都是NP完全问题。然而，2-SAT问题具有基于蕴涵图Sharir（1981）的线性求解器。但在我们的经验为27皇后使用Z3求解器的运行时间减慢寻找解决方案。为此，我们提出了另一种多项式时间算法，该算法具有良好的复杂性，用于对具有Kneser表示变体的皇后图的顶点进行编码，如Richards（1997）所述，参见下一节。●●●●B.Z. El Abidine沙特国王大学学报3×ð Þ3ð Þ23选项。实际上，（Richards，1997）中的表示是本文使用Kneser表示的团中顶点编码的按位或。定义3.2.与n × n棋盘Tn相关联的皇后图Qn有n × n个顶点，对应于nn棋盘的每一个方格. Q n的两个顶点相邻当且仅当它们在棋盘的同一行或列或对角线上Bell和S.B. （2009年）。引理1.n个胞元的皇后图的边数为nn-1 n-1的证明见贝尔和S. B。（2009年）。为了解决皇后图上的问题，我们必须使用文献中解决最大团的对偶问题，即独立集问题的算法。因此，我们使用皇后图的补图。五皇后的补充描绘在图。 二、定义3.3.皇后图的补图Qn图四、 Q03. 低3.1.1. Kneser编码算法下面介绍的算法是用纯python编写的。整个代码可以在Bouneb（2022）中找到。与n乘n棋盘Tn相关联的具有n个顶点，对应于到n乘n棋盘的每一格。Q0n的两个顶点相邻当且仅当它们不在棋盘的同一行、列和对角线上。推论2. n个胞室的皇后图的补图的边数为5 n-1。Codinglist=[]forKK in range（0，18）：codinglist.append（[]）对于范围（4，18）中的KK：n =KK限值=（2*n-3）代码=[]对于在范围（n）中的i棋盘中的单元格从左到右，从上到下逐行编号例1.棋盘上3乘3的格子如图1所示编号。 3图Q03的棋盘3乘3描绘在（图。 四、codage.append（[]）forjinrange（n）：codage[i].append（0）foriin range（n）：对于范围（n）中的jrow = 2**icol = 2**（j + n）codage[i][j]=row + col如果（i==j）和（i==0或i==（n-1））：diagl=0否则：diagl= 2**（（i+ j-1）+2*n）codage[i][j]= codage[i][j]+diagl如果（（i==0）和（j==（n-1）或（（j==0）和（i==（n- 1）：diagr = 0否则：图二. 5皇后图的补集。图三. 棋盘3 × 3编号。B.Z. El Abidine沙特国王大学学报4if（ij）：中的团的候选者可以使用以下算法从灰色区域和M<$n;n<$1中的单元或来自灰色区域和M<$n;n-1<$1中的团计算。第1部分=[]refvec2= codinglist[n+ 1]for e in Minit：对于TorNupdated.items（）中的K，vb = ev如果b=0：s1 = ensclique（K，refvec2）s1.add（e）part1.append（symboliclique（s1，refvec2））ensclique：is函数获取团k并将其转换为关于列表refvec2的集合。symboliclique：是ensclique的逆函数，它取一组团并将其转换为一个数。第2部分=[]对于Tor.items（）中的K1，v1对于K，TorNMinus1updated.items（）中的v：如果v1v == 0：s1= ensclique（K，refvec2）s2=ensclique（K1，refvec2）对于s2中的ds1.add（d）c= symboliclique（s1，refvec2）如果len（s1）==n+ 1：part2.append（c）证据如果我们假设jM<$n;n<$j <$p和jM<$n;n-1 <$j <$k，则上述算法的最坏情况复杂度为：Tn 2n1 -1ωpn-1n-2ωkOn2。 H4. 实验结果我们注意到BronKerbosch不是递增的，所以形式为n-n + 1的区间的时间是计算n + 1的时间。我们之所以选择布朗克布洛克，是因为它使用了与我们的论文（见图10）相同的集团数学理论。将我们的算法与像Google OR-Tools这样的逐位优化的回溯算法进行比较，我们发现Google OR-Tools更快。尽管如此，Google OR-Tools背后的理论与我们的论文并不相同。此外，n = 9的BronKerbosch要求更多的计算机资源，如线程的并发程度和更多的堆栈，我们的算法继续默默地工作。我们的算法的最好的事情是它的模块化和计算与增量方法的属性。这两个优点对于使用Map和Reduce原语的并行化是有益的。此外，在我们的情况下，Mn;n-1和Mn;n是用算法计算的El Abidine（2022）但这并不妨碍我们在第n阶段使用任何其他稍加修改的算法来集成符号计算。这意味着我们可以使用Google OR工具或BronKerbosch。Google OR工具的问题是，我们需要为大小为n-1的集团添加更多的计算，这会显着减慢速度，请参见讨论部分。5. 以迭代的方式我们已经开发了一种算法，该算法仅考虑Mn;n-1和Mn;n;在以迭代方式仅使用该算法执行解之后，我们发现前两次迭代工作良好，但是在第三次迭代中，我们得到了丢失的解，例如，从n = 4开始。在第一次迭代n = 5中，我们得到了10个解，在第二次迭代n = 6中，我们得到了4个解，而在第三次迭代n = 7中，我们得到了38个解，这是不确定的。rect;分析问题后，我们发现，不仅需要计算Mn;n和Mn;n-1，现在我们可以看到Mn1;n1112，因为Mn;n-1是最大的，Mn;n 是最大的，Mn1;n1也是最大的，不需要反链消去。备注1.我们从实验结果中注意到，一个来自灰色区域的大小为2的团和一个来自Mn;n的大小为n-1的团的情况没有在实验结果中对上述两点添加任何额外的解决方案。我们只使用上面讨论的两种情况进行测试，直到n = 10，而没有省略任何解决方案。我们一直在寻找数学证明，但没有任何结果;我们让这个观察结果向离散数学界开放，为它提供坚实的证据，或者给出反例来反驳这个事实。它本身需要计算Mn;n-2 n等，停止阶段取决于图上的最小团大小。例如，对于八个皇后，最小团大小是五个。为此，我们需要消除反链。这个问题的一个解决方案是按大小递减的顺序计算团。图10个。表1：纸算法与BronKerbosch。●●B.Z. El Abidine沙特国王大学学报96. 结论作为结论，用简单的话来总结这项工作的好处。想象一下，我们想打破27 × 27棋盘的最佳记录。首先，我们必须计算大小为26的最大集团，然后是27 × 27的棋盘解。利用这些信息，我们可以在多项式时间内计算出棋盘28 × 28的解例如，如果大小为27的集团需要270天，大小为26的集团在计算27的时间上增加100天，我们将有370天。比如说，我们的算法计算28个解，加上50天，结果28 × 28棋盘的解要花420天，而从头开始计算28 × 28棋盘的解，可能要花两年，这样，我们就节省了一年。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。引用el Abidine，B.Z.，2022.物联网设备上最大团问题的一种有效算法。国际计算机Sci. Eng.（in press）.贝尔，J.，S. B.，2009. n-皇后的已知结果和研究领域综述。Discr.马瑟309，1-31。URL：https://doi.org/10.1016/j.disc.2007.12.043，arXiv：https://www.sciencedirect.com/science/article/pii/。布内，2022年。n queen项目URL：https://github.com/bzine19766/nqueen。布朗角，Kerbosch，J.，1973.算法457：寻找无向图的所有团。Commun. ACM 16，575-577。https://doi.org/10.1145/362342.362367网站。布 莱 恩 特 河 ， 2018. 二 进 制 和 零 抑 制 决 策 图 的 链 约 简 。 pp. 81-98.https://doi.org/10.1007/978-3-319-89960-2_5网站。Cavalcanti，A.，Sampaio，A.，Woodcock，J.（Eds.），2006.软件工程中的精化技术。施普林格柏林海德堡。https://doi.org/10.1007/11889229.伊斯特里奇河，施密特，C.，2008.用遗传算法求解n皇后及其在计算智能课程中的实用性。J.计算机Sci. Coll.23，223- 230.甚至，S.，Itai，A.，Shamir，A.，1976.时间表的复杂性与多商品流问题。SIAM J. Comput.5，691-703。https://doi.org/10.1137/0205048。arXiv：https://doi.org/10.1137/0205048。根特岛，杰斐逊角，Nightingale，P.，2017. 59.第59章最后的约定Khot ， S. ， 2001. 最 大 团 ， 色 数 和 近 似 图 着 色 的 改 进 的 不 可 近 似 性 结 果 600-609.https://doi.org/10的网站。1109/SFCS.2001.959936。Kneser，M.， 1955.第360章意外收获Lajtar，M.，2013年。n皇后问题-新的变种的第二算法。Ann.UMCS Informatica 13，53Luria，Z.，2017. n皇后构形个数的新界。arXiv：1705.05225。Luria，Z.，Simkin，M.，2022年。n皇后问题的下界2022年度ACM-SIAM离散算法研讨会（SODA）。P，S. S.，2011. n皇后中精确搜索的新判定规则。J. Global Optim. 497- 514理查兹，M.，1997. MCPL中使用位模式和递归的回溯算法。英国剑桥大学。萨卡尔，美国，纳格，S.，2018.求解n皇后问题的自适应遗传算法。ArXivabs/1802.02006。Sharir，M.，1981.强连通性算法及其在数据流分析中的应用。Comput. Math.Appl.7，67-72.索西奇河顾，J.，1990年n皇后问题的多项式时间算法SIGART Bull. 1，7-11. https://doi.org/10.1145/101340.101343网站。Zongyan，Q.，2002. n皇后问题的位向量编码。SIGPLAN不。37，68https://doi.org/10.1145/568600.568613网站。