完整word版,C++課程設(shè)計(jì)實(shí)踐報(bào)告書-八皇后問(wèn)題

1、課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目： 對(duì)八皇后問(wèn)題進(jìn)行求解學(xué)生姓名：專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)： 09-2學(xué)號(hào)：指導(dǎo)教師： 李俊照完成日期： 2010-5-30合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院（一）需求和規(guī)格說(shuō)明在 8 行 8 列的棋盤上放置8 個(gè)皇后，使任一個(gè)皇后都不能吃掉其他的7 個(gè)皇后（注：皇后可吃掉與她處于同行或同列或同一對(duì)角線上的其他棋子），并將結(jié)果以某種方式顯示出來(lái)。例如，當(dāng)求出下述的一個(gè)解時(shí)，可輸出如下信息來(lái)表示該解（輸出了表示擺放皇后的坐標(biāo)位置以及“棋盤狀態(tài)”棋盤中有皇后的位置放一個(gè)“Q”字符，其他位置為“ +”字符）。(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2

2、,7) (4,8)Q+Q+Q+Q+Q+Q+Q+Q+（二）設(shè)計(jì)（1） 通過(guò)“ int LineNum9; bool a9, b15, c15;”說(shuō)明具有全局作用域的4 個(gè)數(shù)組。其中的：LineNumi 表示第 i 列的皇后要放的行位置（只用其中的列號(hào)1到 8）；ai為 true （ i =1， 2， 8）表示第 i 行上尚未放皇后；bi為 true （ i =0， 1， 2， 14）表示第 i 條斜對(duì)角線上尚未放皇后（斜對(duì)角線指的是“/ ”狀對(duì)角線，該對(duì)角線上各點(diǎn)的行列號(hào)之和i+j 為一個(gè)常數(shù)）；ci為 true （ i=0 ， 1， 2， 14）表示第 i條反斜對(duì)角線上尚未放皇后（反斜對(duì)角線指

3、的是“ ”狀對(duì)角線，該對(duì)角線上各點(diǎn)的行列號(hào)之差i-j為一個(gè)常數(shù)）。從而當(dāng)使用語(yǔ)句“ if ( aj & bi+j-2 & ci-j+7 ) LineNumi=j;”時(shí)，可用于判斷并實(shí)現(xiàn)：如果在第j 行的第 i 列上放置皇后安全的話，則將一枚皇后放置到那兒。（2）編制一個(gè)具有如下原型的遞歸函數(shù)solve ，它負(fù)責(zé)往第 i 列開(kāi)始的連續(xù) 8-i+1列上均放上皇后，若成功則通過(guò)引用參數(shù)ok 返回 true （否則返回 false ）。void solve(int i, bool& ok);擺放皇后之后，若i=8 即已放滿時(shí)則遞歸出口；否則通過(guò)solve(i+1,ok);進(jìn)行遞歸調(diào)用。（3）編制主函數(shù)

4、，首先初始化一個(gè)“空棋盤”，即將 a、b、c 數(shù)組的各元素均置為true （表示當(dāng)前棋盤的 8 個(gè)行、 15條斜對(duì)角線以及15 條反斜對(duì)角線上都尚未擺放皇后）。而后執(zhí)行調(diào)用語(yǔ)句“ solve(1,ok);”，它負(fù)責(zé)往第 1 列開(kāi)始的連續(xù) 8列上均放上皇后，若成功則通過(guò)引用參數(shù) ok 返回 true （否則返回false ）。（三）用戶手冊(cè)直接運(yùn)行即可（四）調(diào)試及測(cè)試運(yùn)行實(shí)例：Q+Q+Q+ +Q+ Q+ +Q+ +Q+ +Q+進(jìn)一步改進(jìn)：（ 1）可改用非遞歸方法設(shè)計(jì)并編寫solve 函數(shù)，那樣的話，通常要設(shè)置數(shù)組來(lái)記錄皇后的擺放位置信息，還要記錄這些皇后所產(chǎn)生的“影響面” （所建立的“勢(shì)力范圍”

5、） 使得哪些行列位置不可再擺放皇后。當(dāng)在新的行列位置擺放了皇后、但此時(shí)又無(wú)法進(jìn)一步擺放其他的皇后時(shí)，要回退（回溯）到上一個(gè)位置接著去考慮另外的“行走”方法（若還有的話）等等。但注意，“回退”一步后，要同時(shí)“撤銷”由于該步的回退而關(guān)聯(lián)的那些“影響面”（釋放“勢(shì)力范圍” ）。（ 2）本程序只是找到了某一種“擺放方案”而終止，還可進(jìn)一步考慮尋找其他各種不同的“擺放方案” （實(shí)際上共有 92 種）。（ 3）也可用同樣的方法去處理其他“階數(shù)” 的皇后問(wèn)題， 如求解四皇后問(wèn)題等。附錄：源程序#include #include using namespace std;int LineNum9;bool a9

6、, b15, c15;void solve(int i, bool& ok);void Output();void main()bool ok;int i;ok=false;for(i = 1 ; i =8 ; i+)ai=true;for(i = 0 ; i =14 ; i+)bi=true;ci=true;solve (1,ok);void solve(int i, bool& ok)int j;if(i = 9 |ok=true)ok=true;Output();return;for(j = 1 ; j= 8 ; j+)if ( aj & bi+j-2 & c7+i-j )LineNumi=j;aj=false;bi+j-2=false;c7+i-j=false;solve (i+1,ok);if(ok=false)aj=true;bi+j-2=true;c7+i-j= true;void Output()int i,j;for(i = 1 ; i 9 ; i+)cout (