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

计算机与现代化 ›› 2013, Vol. 1 ›› Issue (1): 19-21.doi:

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

孙国伟1 ,买阿丽2

1.运城学院应用数学系,山西运城044000； 2.广州大学数学与信息科学学院,广东广州510006

收稿日期:2012-09-04 修回日期:1900-01-01 出版日期:2013-02-06 发布日期:2013-02-06

A Nonrecursive Algorithm of Solving NQueens Problem Using Symmetry 

SUN Guowei1, MAI Ali2

1. Department of Applied Mathematics, Yuncheng University, Yuncheng 044000, China；2. School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China

Received:2012-09-04 Revised:1900-01-01 Online:2013-02-06 Published:2013-02-06

摘要/Abstract

摘要：

利用回溯法，采用栈和队列实现计算N皇后解的一个新的非递归算法，并提出N皇后解的4个对称性质，重点分析5皇后的10个解之间的对称关系。然后利用对称性将搜索空间缩小为解空间的一半，给出计算N皇后问题的优化算法。理论分析和实验表明对称性可以明显提高N皇后问题的计算效率。



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

Abstract: 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.

Key words: 

孙国伟;买阿丽. 基于对称性计算N皇后问题的非递归算法[J]. 计算机与现代化, 2013, 1(1): 19-21.

SUN Guowei;MAI Ali. A Nonrecursive Algorithm of Solving NQueens Problem Using Symmetry  [J]. Computer and Modernization, 2013, 1(1): 19-21.

[1]	李淑霞, 杨俊成, . 一种改进的全覆盖路径规划算法[J]. 计算机与现代化, 2021, 0(02): 100-103.
[2]	李慧鑫,姚文明. 基于不可靠通信链路的数据共享模块[J]. 计算机与现代化, 2019, 0(01): 80-.
[3]	张瑞杰1，张文生1，李战怀2. 基于文件队列的分级存储系统FQ-HSM的设计与实现[J]. 计算机与现代化, 2017, 0(2): 67-72+97.
[4]	芮茂海. 一种使用历史信息的长期公平队列调度算法[J]. 计算机与现代化, 2017, 0(11): 84-88.
[5]	黄益彬,金倩倩,纪元. 网络数据包高性能并行处理技术研究[J]. 计算机与现代化, 2016, 0(12): 57-61.
[6]	陈越洋，顾平，张超. 基于SP调度策略的簇树型无线传感网络QoS上界研究[J]. 计算机与现代化, 2014, 0(7): 117-120.
[7]	邹杰，许涛，林茂，李铁，雷宏声. 基于PBS的勘探数据处理作业管理[J]. 计算机与现代化, 2014, 0(2): 119-123.
[8]	王龙峰. RAODV:一种基于拥塞跳数改进的AODV路由协议[J]. 计算机与现代化, 2013, 1(8): 133-136.
[9]	陈柳1，周伟2 . 基于拜占庭容错的前摄恢复算法[J]. 计算机与现代化, 2013, 12(12): 38-40.
[10]	马灵娟;李长青;刘晖. 基于双缓冲队列的RS485串口/以太网转换器软件设计[J]. 计算机与现代化, 2013, 1(11): 95-99.
[11]	倪东;张素伟. 基于消息中间件的车辆GPS监控系统框架的设计[J]. 计算机与现代化, 2012, 1(11): 186-189.
[12]	沙胜华李欣郭大权. 基于发布/订阅的消息队列在工作流引擎中的应用研究[J]. 计算机与现代化, 2012, 1(10): 142-144,.
[13]	吴红萍. N皇后问题的Java程序实现及分析[J]. 计算机与现代化, 2011, 1(3): 15-16,2.
[14]	朱长元. 递归程序非递归化算法在企业生产中的应用[J]. 计算机与现代化, 2011, 12(12): 185-187,.
[15]	徐攀;冯径;黄立威. 支持队列公平和安全策略的调度算法研究[J]. 计算机与现代化, 2010, 1(6): 9-0012.