摘要
N皇后问题是指在N×N的国际象棋棋盘上放置N个皇后，使得任意两个皇后之间互不攻击。国际象棋中的皇后可以沿水平、垂直和对角线方向移动，因此，任意两个皇后在上述三个方向上均不能处于同一行、同一列或同一对角线上。科学界普遍认为，该问题的分支因子近似呈线性增长。借助人工智能中的搜索策略，如广度优先搜索（Breadth-First Search, BFS）、深度优先搜索（Depth-First Search, DFS）以及回溯算法，众多学者已对该问题进行了深入研究，并提出了多种求解N皇后问题的有效方法。采用无信息搜索策略（即“盲目搜索”）的解法，如BFS和DFS，通常依赖递归实现；同样，回溯算法也通过递归方式求解该问题。然而，所有这些递归算法均依赖系统栈进行函数调用管理，而系统栈空间有限。因此，当N值较小时，递归调用便可能迅速耗尽内存资源，尽管具体表现仍与计算机硬件性能相关。本文针对上述问题，提出一种基于非递归深度优先搜索（DFS）的求解方法，旨在减少系统内存的占用。在本研究中，DFS被作为无信息搜索（即盲目搜索）的典型方法加以应用。实验结果表明，该方法在时间和空间效率方面均取得了显著优化，展现出良好的性能表现。