基于BFS的八皇后问题算法设计与实现

李钊毅

摘要：该文用宽度优先搜索方法实现了八皇后问题的算法设计，并用队列非递归方法实现了该算法。

关键词：宽度优先搜索（BFS）；八皇后；队列

中图分类号：TP311 文献标识码：A 文章编号：1009-3044(2014)26-6166-03

Abstract:?This paper design the algorithm for?eight?queens?problem based on breadth?first?search, and?implements?the?algorithm by using the queue structure and?non-recursive?method.

Key words: Breadth First Search; Eight Queens; Queue Structure

八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上，见图1示例，图2是一个解示例，图中Q表示皇后的位置。

4 结束语

本文用宽度优先搜索方法实现了数学中的经典问题——八皇后问题， 采用了队列这种数据结构，并且用非递归的方法解决了回溯方法中效率的问题， 可以让初学者对队列这种数据结构的含义有更深入的理解， 为进一步学习《数据结构》这门课程打下良好的基础。

参考文献：

[1] Stephen Prata.C++ Primer Plus 中文版[M].5版.孙建春,译.北京:人民邮电出版社,2011.

[2] Thomas H Cormen.算法导论 [M].潘金贵,等,译.北京:机械工业出版社,2007.

[3] 李志伟.数据结构中八皇后问题的堆栈非递归方法的实现研究[J].福建电脑,2012(2):115-116.