八皇后問(wèn)題課程設(shè)計(jì)報(bào)告

for(queen[++j]=0;queen[j]<8;queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;queen[j]++)if(judge(queen,j))輸出正確解法的 輸出正確解法的 排列形式輸出止確解法的棋盤擺放形式課程設(shè)計(jì)題目：名稱：八皇后問(wèn)題內(nèi)容：設(shè)計(jì)程序完成如下要求：在8X8的國(guó)際象棋棋盤上，放置8個(gè)皇后，使得這8個(gè)棋子不能互相被對(duì)方吃掉。要求：（1）依次輸出各種成功的放置方法。（2）最好能畫出棋盤的圖形形式，并在其上動(dòng)態(tài)地標(biāo)注行走的過(guò)程。（3）程序能方便地移植到其他規(guī)格的棋盤上。一、問(wèn)題分析和任務(wù)定義八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，根據(jù)國(guó)際象棋的規(guī)定，皇后可以攻擊與它在同一行、同一列或者同一斜線上的棋子，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。在8!=40320種排列中共有92種解決方案。本程序需要解決的問(wèn)題有：1、建立合適的數(shù)據(jù)類型表示皇后在棋盤上所處的位置。2、成功的輸出全部正確的放置方法。3、畫出棋盤形式，在上面動(dòng)態(tài)的標(biāo)注其行走的過(guò)程。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)1、為了簡(jiǎn)單易行的表示皇后在棋盤所處的位置，在此建立一個(gè)整型數(shù)組queen[i]來(lái)表示，若queen[3]=2則表示皇后處在8、8棋盤的第三行和第二列。2、表示好皇后以后，設(shè)計(jì)judge（和）check（函）數(shù)來(lái)檢測(cè)第一個(gè)皇后的同列和同斜線上有沒有其他皇后（程序以行為基礎(chǔ)，逐行試探每列和斜線上是否有皇后）。然后設(shè)計(jì)輸出函數(shù)show（和）print（分）別輸出正確解法的排列形式和棋盤擺放形式。在輸出棋盤的步驟中，設(shè)計(jì)一個(gè)遞歸函數(shù)go（實(shí)）現(xiàn)棋盤的輸出。3、程序的流程圖如下圖所示：Main建立數(shù)組表示皇后在板盤上的位置在不同行的基礎(chǔ)上檢測(cè)某個(gè)皇后的同列和同斜線上是否存在其他皇后輸出所有正確解法的個(gè)數(shù)，程序結(jié)束圖1程序流程圖—―

三、詳細(xì)設(shè)計(jì)和編碼1、首先定義整型數(shù)組queen[i]表示皇后的位置，i的取值由0到7表示八個(gè)皇后。然后定義一個(gè)整型變量count來(lái)統(tǒng)計(jì)所有正確解法的個(gè)數(shù)。2、因?yàn)槊啃兄荒軘[放一個(gè)皇后，所以在皇后不在同一行的基礎(chǔ)上，設(shè)計(jì)檢測(cè)函數(shù)檢測(cè)皇后的同列和同斜線上是否存在其他皇后。檢測(cè)是否同列的時(shí)候，定義兩個(gè)變量 i和j表示兩個(gè)皇后所在的行數(shù)，則用queen[i^queen[j]表示它們所在的列數(shù)，通過(guò)驗(yàn)證queen[i]和queen[j]是否相等確定兩個(gè)皇后是否處于同一列上。檢測(cè)同斜線的時(shí)候，用到了求絕對(duì)值的函數(shù)abs(函)數(shù)，用abs(p[j]-p[i])==j-i是否相等來(lái)驗(yàn)證任意兩個(gè)皇后是否在同一斜線上。intjudge(int*p,亞/檢測(cè)皇后是否在同列或者同一斜線上{inti;for(i=0;i<j;i++) //皇后在同一列上的{if(p[j]==p[i])return0;情況if(abs(p[j]-p[i])==j-i)return0;}return1;intcheck(intqueen[],int〃檢測(cè)棋盤布局是否合法{intj,k;for(j=0;j<=i;j++){for(k=0;k<=i;k++){if(j!=k&&(queen[j]==queen[k]||abs(queen[j]-queen[k])==abs(j-k)))皇//后不在同一行且在同一列或者同一斜線時(shí){return0;}}}return1;3、設(shè)計(jì)輸出函數(shù)輸出八皇后問(wèn)題的正確解法，首先 show()函數(shù)輸出排列形編寫 式，為了方便，將正確解法的判定條件編寫在輸出函數(shù)中，用多個(gè)案，執(zhí)行之后輸出所有正確方法的排列形式和正確解法的個(gè)數(shù)。然后編寫print(函)數(shù)輸出棋盤形式，按行掃描，用for循環(huán)條件語(yǔ)句判定條件之后，皇后輸出“Q”，非皇后位置輸出+”，在遞歸函數(shù)go(中)調(diào)用print(函)數(shù)可以完整的輸出所有正確解法的棋盤形式。voidshow(intqueen[]){inti=0,j=0,amount=0;

for(queen[0]=0;queen[0]<8;j=0,queen[j]++)//按彳丁開始逐行試探每一^列上的皇后位置是否合法for(queen[++j]=0;queen[j]<8;j=l/queen[j]++)for(queen[++j]=0;queen[j]<8;j=2/queen[j]++)for(queen[++j]=0;queen[j]<8;j=3/queen[j]++)for(queen[++j]=0;queen[j]<8;j=4/queen[j]++)for(queen[++j]=0;queen[j]<8;j=5/queen[j]++)for(queen[++j]=0;queen[j]<8;j=6/queen[j]++)if0udge(queenj)ifQudgefqueenJ))if0udge(queenj)ifQudgefqueenJ))ifQudgefqueenJ)){for(i=0;i<8;i++)printf("%d",queen[i]);//輸出正確解法的排列形式++amount; //統(tǒng)計(jì)所有正確解法的個(gè)數(shù)printf("\n");}printf("\nthereis%danswer\n",amount);voidprint(intqueen{[]) //輸出皇后在棋盤上的擺放形式inti,j;for(i=0;i<8;i++){for(j=0;j<queen[i];j++)皇//后前輸出"+"{printf("+");}printf("Q"); //輸出Q表示皇后for(j=7;j>queen[i];j--)//皇后后面輸出"+"{printf("+");};}printf("pressanykeytoshownextanswer:");getchar();//接收字符getchar();}4、編寫程序主函數(shù)，在main（中）調(diào)用各個(gè)功能函數(shù)實(shí)現(xiàn)八皇后問(wèn)題的要求，其中運(yùn)用getchar（函）數(shù)接收字符，設(shè)置按任意鍵繼續(xù)的功能。5、注：本次課程設(shè)計(jì)主要運(yùn)用VisualC++6的編譯環(huán)境，無(wú)法使用清屏函數(shù)，在turboc的編譯環(huán)境中，使用clrscr（清）屏函數(shù)可以實(shí)現(xiàn)動(dòng)態(tài)的輸出皇后在棋盤上的擺放形式。詳細(xì)代碼如下：voidprint（int //動(dòng)態(tài)輸出棋盤擺放queen[]）{inti,j;形式clrscr（）;for(i=0;i<8;i++){for(j=0;j<queen[i];j+for(i=0;i<8;i++){for(j=0;j<queen[i];j++){printf("+");}printf("Q");for(j=7;j>queen[i];j--){printf("+");};printf("\n");//每行中皇后前面的棋盤//皇后clrscr（）;四、}上機(jī)調(diào)試本次課程設(shè)計(jì)中遇到了許多的困難，產(chǎn)生了不少的問(wèn)題。1、剛開始使用結(jié)構(gòu)體表示皇后的位置，構(gòu)造了較多的變量，程序設(shè)計(jì)中產(chǎn)生了許多的錯(cuò)誤，判斷同斜線情況不太方便，算法性能也不少很好。后來(lái)想到運(yùn)用數(shù)組來(lái)表示皇后的位置，不但數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，而且較容易的表示處皇后的位置，容易分析皇后同列、同斜線的情

況(用到abs(函)數(shù))，所以建立整型數(shù)組來(lái)表示皇后在棋盤上的位置。2、動(dòng)態(tài)輸出棋盤擺放形式的時(shí)候，自動(dòng)輸出的速度太快，無(wú)法觀察清楚，后來(lái)只好運(yùn)用getchar(函)數(shù)接受一個(gè)空的字符手動(dòng)控制棋盤的輸出。五、測(cè)試結(jié)果及其分析程序運(yùn)行結(jié)果如下各圖所示：分析：本次課程設(shè)計(jì)完成之后，仍覺得有些不足之處，例如無(wú)法讓電腦自動(dòng)輸出動(dòng)態(tài)的擺放皇后過(guò)程，必須手動(dòng)操作完成。算法的時(shí)間復(fù)雜度也不是很好。各函數(shù)的時(shí)間復(fù)雜度如下：in時(shí)間復(fù)雜度為in時(shí)間復(fù)雜度為O(n)時(shí)間復(fù)雜度為O(n2)時(shí)間復(fù)雜度為O(n9)時(shí)間復(fù)雜度為O(n2)時(shí)間復(fù)雜度為intjudge(int*p,intj)check(intqueen[],inti)voidshow(intqueen[])voidprint(intqueen[])voidgo(intqueen[],int圖2程序運(yùn)行結(jié)果部分截圖(1)圖3圖3程序運(yùn)行結(jié)果部分截圖(2)XA圖4程序運(yùn)行結(jié)果部分截圖(3)

54圖5程六、用戶使用說(shuō)明54圖5程六、用戶使用說(shuō)明pressanykeytoshownextanswer：執(zhí)行.exe程序按照提示，按回車輸出兩種結(jié)果。七、參考文獻(xiàn)【1】王昆侖李紅.數(shù)據(jù)結(jié)構(gòu)與算法.中國(guó)鐵道出版社.2007年6月第一版.【2】何欽銘顏暉.語(yǔ)言程序設(shè)計(jì).高等教育出版社.200年4月第一版.八、附錄#include<stdio.h>#include<stdlib.h>#include<math.h>intcount=0;定//義一個(gè)整型變量count來(lái)統(tǒng)計(jì)正確解法的個(gè)數(shù)intqueen[8];定//義數(shù)組表示皇后所處的位置（queen[3]=2表示皇后在第三行和第二列上）intjudge(int*p,intj)//intjudge(int*p,intj)//檢測(cè)皇后是否在同列或者同一斜線上{{inti;for(i=0;i<j;i++){if(p[j]==p[i])return0;if(abs(p[j]-p[i])==j-i)return0;//皇后在同一列上的情況return1;}}//皇后在同一斜線上的情況intcheck（intqueen[],in//檢測(cè)棋盤布局是否合法intj,k;for(j=0;j<=i;j++){for(k=0;k<=i;k++){if(j!=k&&(queen[j]==queen[k]||abs(queen[j]-queen[k])==abs(j-k)))/皇/后不在同一{行且在同一列或者同一斜線時(shí){return0;}}}return1;}voidshow(intqueen[]){inti=0,j=0,amount=0;for(queen[0]=0;queen[0]<8;j=0,queen[j]++)//按行開始逐行試探每一列上的皇后位置是否合法for(queen[++j]=0;queen[j]<8;j=1,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=2,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=3,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=4,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=5,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=6,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;queen[j]++)if(judge(queen,j)){for(i=0;i<8;i++)printf("%d",queen[i]);//輸出正確解法的排列形式++amount;/統(tǒng)/計(jì)所有正確解法的個(gè)數(shù)printf("\n");}printf("\nthereis%danswer\n",amount);}voidprint(intqueen[])//輸出皇后在棋盤上的擺放形式{inti,j;for(i=0;i<8;i++)for(j=0;j<queen[i];j++)/皇/后前輸出"+"{printf("+");}printf("Q");//輸出Q表示皇后

for(j=7;j>queen[i];j--)//皇后后面輸出"+"{printf("+");};printf("\n");printf("pressanykeytoshownextanswer:");玄心接0收字符}voidgo(intqueen[],int//遞歸函數(shù)if(i>=8) //一個(gè)棋盤上擺滿8個(gè)皇{count++; 〃統(tǒng)計(jì)一次方法print(queen); 〃輸出一個(gè)正確的解法}else{intj;for(j=0;j<8;j++){queen[i]=j;if(check(queen,i))go(que