李釗毅

摘要：該文用寬度優(yōu)先搜索方法實(shí)現(xiàn)了八皇后問(wèn)題的算法設(shè)計(jì)，并用隊(duì)列非遞歸方法實(shí)現(xiàn)了該算法。

關(guān)鍵詞：寬度優(yōu)先搜索（BFS）；八皇后；隊(duì)列

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

八皇后問(wèn)題19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。他的問(wèn)題是：在8*8的棋盤(pán)上放8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列、同一斜線(xiàn)上，見(jiàn)圖1示例，圖2是一個(gè)解示例，圖中Q表示皇后的位置。

4 結(jié)束語(yǔ)

本文用寬度優(yōu)先搜索方法實(shí)現(xiàn)了數(shù)學(xué)中的經(jīng)典問(wèn)題——八皇后問(wèn)題， 采用了隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，并且用非遞歸的方法解決了回溯方法中效率的問(wèn)題， 可以讓初學(xué)者對(duì)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的含義有更深入的理解， 為進(jìn)一步學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課程打下良好的基礎(chǔ)。

參考文獻(xiàn)：

[1] Stephen Prata.C++ Primer Plus 中文版[M].5版.孫建春,譯.北京:人民郵電出版社,2011.

[2] Thomas H Cormen.算法導(dǎo)論 [M].潘金貴,等,譯.北京:機(jī)械工業(yè)出版社,2007.

[3] 李志偉.數(shù)據(jù)結(jié)構(gòu)中八皇后問(wèn)題的堆棧非遞歸方法的實(shí)現(xiàn)研究[J].福建電腦,2012(2):115-116.