算法設(shè)計與實(shí)驗(yàn)分析五：八皇后問題.doc

《算法設(shè)計與實(shí)驗(yàn)分析五：八皇后問題.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法設(shè)計與實(shí)驗(yàn)分析無五：八皇后問題班級：網(wǎng)絡(luò)1101姓名：齊岳川學(xué)號：日期：2013.5.21一：實(shí)驗(yàn)名稱：八皇后問題二：實(shí)驗(yàn)內(nèi)容：在8×8格的國際象棋上擺放八皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。雖然問題的關(guān)鍵在于如何判定某個皇后所在的行、列、斜線是否有別的皇后；可以從矩陣的特點(diǎn)上找到規(guī)律，如果在同一行，則行號相同；如果在同一列上，則列號相同；如果同在“/”斜線上的行列值之和相同；如果在對角線上，則行列號之和或之差相等，逐個紀(jì)錄符合題意的情況,最終得出解?；厮莘ǎ夯厮菟惴ㄒ步性囂椒?，它是一種系統(tǒng)地搜索

2、問題的解的方法。按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。三：程序清單：#include#include#include#include1staticcharQueen[8][8];staticinta[8];staticintb[15];staticintc[15];staticintiQueenNum=0;staticintiNu

3、m=1;voidiQueen(inti);voidmeasure1(){intiLine;intiColumn;for(iLine=0;iLine<8;iLine++){a[iLine]=0;for(iColumn=0;iColumn<8;iColumn++)Queen[iLine][iColumn]='*';}for(iLine=0;iLine<15;iLine++)b[iLine]=c[iLine]=0;iQueen(0);};voidiQueen(inti){intiColumn;for(iColumn=0;iColumn<8;iColumn++){

4、if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0){Queen[i][iColumn]='@';a[iColumn]=1;b[i-iColumn+7]=1;c[i+iColumn]=1;if(i<7)iQueen(i+1);else{intiLine;intiColumn;cout<<"(遞歸法)皇后擺放方式的第"<

5、(2)<nul");iNum++;cout<

6、Column+7]=0;c[i+iColumn]=0;}}}運(yùn)行結(jié)果: