浅谈N皇后问题解法
发布网友
发布时间：2024-09-07 09:41
共1个回答
热心网友
时间：2024-09-24 19:49
在大小为[公式]的棋盘上摆放[公式]个皇后，使其两两之间不能互相攻击，即任意两个皇后都不能处于棋盘的同一行、同一列或同一斜线上，求出满足条件的所有棋局及局面总数。
特殊地，当[公式]时为著名的以国际象棋棋盘为背景的8皇后问题，易解得符合条件的局面总数为92。本实验主要探究[公式]的棋盘上摆放[公式]个皇后的一般问题。
[公式]皇后问题可以维护一个长度为[公式]的一维数组q表示局面情况。[公式]表示第[公式]行皇后放置位置所在列数[公式]，每个局面可看作由[公式]到[公式]序列组成的一个排列，原问题可以转化成寻找所有不导致行/列/斜线冲突的排列。
直观的想法是将[公式]皇后问题看成组合问题，[公式]的棋盘上每个格都有防放置皇后和空格两种情况，总情况数达[公式]，指数爆炸在时间和空间复杂度上都难以负担。一种改进思路是考虑每列仅允许出现一个皇后，按照行先序顺序放置皇后，第一行有[公式]种可能，第二行有[公式]种可能…第[公式]行有1种可能，总情况数缩减为[公式]略有改善。为进一步提高算法效率，考虑棋盘上每条斜线上仅允许出现一个皇后，在此联想到回溯和剪枝的算法。
引入N叉树的数据结构，构建[公式]皇后问题的解空间树。排列长度[公式]为树的深度，据此判定递归的出口。初始状态将一维数组q置空，以行先序从第0行开始递归求解。遍历[公式]行每一列[公式]，若q中已有[公式]（即第[公式]列已经放置了皇后），则发生剪枝，继续遍历其他列；若q中没有[公式]，则[公式]，递归式进入[公式]行的遍历，直到数组q中已经赋满[公式]个列号，则进入递归出口进行判定局面的合理性（即每个行/列/斜线最多仅有1个皇后）。若局面合理，将该合理局面保存在二维数组result中，继续回溯探索其他合理局面；若局面不合理，同样回溯探索其他合理局面。以此类推，直到遍历完解空间中所有情况，result中所保存的就是所有合理局面，result的长度就是[公式]皇后问题满足条件的所有局面总数。
其中判断局面合理性的方法具体如下：
由数组q可获得第[公式]个皇后的位置记为[公式]，[公式]，一个合理的局面需要满足以下条件([公式])：
以4皇后为例，下图为剪枝与回溯思想的示意图：(仅示意，不代表真实求解情况)
[编译环境] Windows 系统|PyCharm 编译器|python 3.8.11
传统解决[公式]皇后问题的算法都是基于递归的回溯算法，但单线程递归程序不易可视化。因此，我分别设计了用于求解[公式]皇后所有解法数的递归函数search()和用于窗口可视化的基于栈实现的非递归函数 next()，并将它们封装在类NQueen中。其中，search()通过调用dfs()方法递归求解所有[公式]皇后问题的局面；next()输入一组[公式]合理的[公式]皇后排列返回下一组合理的[公式]皇后排列，默认开始为空排列，默认最后一组合理的[公式]皇后排列的下一组排列为空排列。
类NQueen代码如下：
调用python中的tkinter库完成[公式]皇后问题求解可视化呈现，代码详见附件。由于[公式]较大时展示不便，在此取[公式]的调节范围为[公式]，部分界面可视化如下：
具体界面操作见视频演示（连续执行是循环播放所有可能的局面）。
当[公式]时合理局面数已经超过两百万，程序运行时间较长，在此展示[公式]的N皇后问题合理局面总数。
观察结果，仅当[公式]或[公式]时[公式]皇后问题才有非零解。
一种改进的思路是对于不同的皇后问题，使用不同的方法计算合理局面数。
对于[公式]的任意N皇后问题，可以采取分治法确定部分解。例如可以通过5皇后问题的解确定25皇后问题的部分解进而确定125皇后问题的部分解，示意图如下：
以此类推，分治思路成倍向外扩展便能生成一个无穷皇后问题的解。
本实验对传统的八皇后问题进行推广，在求解[公式]皇后问题所有满足条件的棋局及局面总数的过程中掌握了回溯法避免组合爆炸的思想以及剪枝减少时间复杂度的优化算法，同时还设计非递归算法对[公式]皇后问题的结果进行了清晰的可视化呈现，还进一步探究了分治法在[公式]皇后问题中的应用，为生成无穷皇后问题的解提供了可行思路。
