Python：各种算法解决八皇后问题_python解决八皇后问题

作者：从前慢现在也慢 | 2024-06-13 03:45:45

踩

python解决八皇后问题

1 八皇后问题

问题：有一个8乘8的棋盘，现在要将八个皇后放到棋盘上，满足：对于每一个皇后，在自己所在的行、列、两个对角线都没有其他皇后。
在这里插入图片描述

6篇博文，共11种解决方案：

下面对各类方法进行评价：

（1）暴力破解找到了全部的92个解，并且主程序运行时间也并不是很长，基本在5s内。

（2）对遗传算法的代码自己并不满意。性能差的主要原因可能是变异操作没选好，其次是交叉操作不优。

（3）爬山法/随机重启爬山法/允许侧移的爬山法代码中，爬山法经常会陷入局部最优导致无法找到解；随机重启爬山法比较无赖，不行就重来，所以大多都可以找到解；允许侧移的爬山法可以大大提高爬山法解决八皇后问题的成功概率，基本上每次运行都可以得到解序列。

（4）随机游走代码有时候会失败，因为算法是将皇后随机放置在当前列的任意位置，若已放置皇后的前几列中无互相攻击的皇后，则进行下一列位置的选择，因此过程中可能会达到【无合适位置可放】的状态，不得不宣告失败，只能通过重新运行程序来重新进行探索，可能需要多运行几次才能得到解。

（5）DFS/BFS/UCS代码中，DFS、UCS解决八皇后问题的效率与性能较高，BFS最差。

（6）GBF/A*算法代码中，相对于GBF算法，A*算法代码的运行时间更少，毕竟A*算法是全局择优且用到了更多有用的信息。

暴力破解与随机游走代码完全是自己思考的，值得骄傲；虽然自己对遗传算法代码的性能不满意，但是自己在写代码的过程中想了很多，锻炼了自己的逻辑思维，还是很高兴的；6篇博文的代码相似之处较多，但是细节上均有差别，甚至在注释的措辞修改中，自己都进行了仔细的斟酌。

为了解决八皇后问题，使用各种算法进行了“狂轰滥炸”，自己收获不浅，继续加油！

END

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/710744