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

A Non-recursive Algorithm of Solving N-Queens Problem Using Symmetry

作　　者：孙国伟[1] 买阿丽[2] 

机构地区：[1]运城学院应用数学系,山西运城044000 [2]广州大学数学与信息科学学院,广东广州510006

出　　处：《计算机与现代化》2013年第1期19-21,24,共4页Computer and Modernization

基　　金：国家自然科学基金资助项目(11071283);运城学院基金资助项目(JY-2011039;JY-2011026;JY-2011038)

摘　　要：利用回溯法,采用栈和队列实现计算N皇后解的一个新的非递归算法,并提出N皇后解的4个对称性质,重点分析5皇后的10个解之间的对称关系。然后利用对称性将搜索空间缩小为解空间的一半,给出计算N皇后问题的优化算法。理论分析和实验表明对称性可以明显提高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 S- 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 sig- nificantly improve the efficiency of solving N-Queens problem.

关 键 词：栈 队列 非递归算法 N皇后问题 回溯法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]