基于对称性计算N皇后问题的非递归算法

摘要

A new non-recursive algorithm of solving N-Queens problem is achieved by using backtracking, which is based on stack and queue. This paper presents four properties of N-Queens solutions, and analyses the symmetry between 10 solutions of 5-Queens problem. Then using the symmetry, searching space is shortened a half of the solution space. The optimization algorithm to calculate the N-Queens problem is obtained. Through theoretical analysis and experimental verification, the symmetry can significantly improve the efficiency of solving N-Queens problem.%利用回溯法,采用栈和队列实现计算N皇后解的一个新的非递归算法,并提出N皇后解的4个对称性质,重点分析5皇后的10个解之间的对称关系.然后利用对称性将搜索空间缩小为解空间的一半,给出计算N皇后问题的优化算法.理论分析和实验表明对称性可以明显提高N皇后问题的计算效率.