八皇后問題課程設計報告

課程設計題目：

名稱：八皇后問題

內容：設計程式完成如下要求：在8×8的西洋棋棋盤上，放置8個皇后，使得這8個棋子不能互相被對方吃掉。

要求：(1)依次輸出各種成功的放置方法。(2)最好能畫出棋盤的圖形形式，並在其上動態地標註行走的過程。

(3)程式能方便地移植到其他規格的棋盤上。

一、問題分析和任務定義

八皇后問題是乙個古老而著名的問題，是回溯演算法的典型例題。該問題是十九世紀著名的數學家高斯2023年提出：在8x8格的西洋棋上擺放八個皇后，使其不能互相攻擊，根據西洋棋的規定，皇后可以攻擊與它在同一行、同一列或者同一斜線上的棋子，即任意兩個皇后都不能處於同一行、同一列或同一斜線上，問有多少種擺法。

在8!=40320種排列中共有92種解決方案。

本程式需要解決的問題有：

1、建立合適的資料型別表示皇后在棋盤上所處的位置。

2、成功的輸出全部正確的放置方法。

3、畫出棋盤形式，在上面動態的標註其行走的過程。

二、資料結構的選擇和概要設計

1、為了簡單易行的表示皇后在棋盤所處的位置，在此建立乙個整型陣列queen[i]來表示，若queen[3]=2則表示皇后處在8×8棋盤的第三行和第二列。

2、表示好皇后以後，設計judge( )和check( )函式來檢測第乙個皇后的同列和同斜線上有沒有其他皇后（程式以行為基礎，逐行試探每列和斜線上是否有皇后）。然後設計輸出函式show( )和print( )分別輸出正確解法的排列形式和棋盤擺放形式。在輸出棋盤的步驟中，設計乙個遞迴函式go( )實現棋盤的輸出。

3、程式的流程圖如下圖所示：

三、詳細設計和編碼

1、首先定義整型陣列queen[i]表示皇后的位置，i的取值由0到7表示八個皇后。然後定義乙個整型變數count來統計所有正確解法的個數。

2、因為每行只能擺放乙個皇后，所以在皇后不在同一行的基礎上，設計檢測函式檢測皇后的同列和同斜線上是否存在其他皇后。檢測是否同列的時候，定義兩個變數i和j表示兩個皇后所在的行數，則用queen[i]和queen[j]表示它們所在的列數，通過驗證queen[i]和queen[j]是否相等確定兩個皇后是否處於同一列上。檢測同斜線的時候，用到了求絕對值的函式abs( )函式，用abs(p[j]-p[i])==j-i是否相等來驗證任意兩個皇后是否在同一斜線上。

int judge(int *p, int j檢測皇后是否在同列或者同一斜線上

return 1;

}int check(int queen, int i) //檢測棋盤布局是否合法

return 1;

}3、設計輸出函式輸出八皇后問題的正確解法，首先編寫show（）函式輸出排列形式，為了方便，將正確解法的判定條件編寫在輸出函式中，用多個for迴圈條件語句篩選可行方案，執行之後輸出所有正確方法的排列形式和正確解法的個數。然後編寫print( )函式輸出棋盤形式，按行掃瞄，用for迴圈條件語句判定條件之後，皇后輸出「q」，非皇后位置輸出「+」，在遞迴函式go( )中呼叫print( )函式可以完整的輸出所有正確解法的棋盤形式。

void show(int queen)

printf("\nthere is %d answer\n",amount);

void print(int queen輸出皇后在棋盤上的擺放形式

printf("press anykey to show next answer:");

getchar接收字元

}4、編寫程式主函式，在main( )中呼叫各個功能函式實現八皇后問題的要求，其中運用getchar( )函式接收字元，設定按任意鍵繼續的功能。

5、注：本次課程設計主要運用visual c++6.0的編譯環境，無法使用清屏函式，在turboc的編譯環境中，使用clrscr( )清屏函式可以實現動態的輸出皇后在棋盤上的擺放形式。

詳細**如下：

void print(int queen動態輸出棋盤擺放形式

printf("q皇后

for(j=7;j>queen[i];j--)

printf每行中皇后後面的棋盤

printf("\n");

} clrscr();

}四、上機除錯

本次課程設計中遇到了許多的困難，產生了不少的問題。

1、剛開始使用結構體表示皇后的位置，構造了較多的變數，程式設計中產生了許多的錯誤，判斷同斜線情況不太方便，演算法效能也不少很好。後來想到運用陣列來表示皇后的位置，不但資料結構簡單，而且較容易的表示處皇后的位置，容易分析皇后同列、同斜線的情況（用到abs( )函式），所以建立整型陣列來表示皇后在棋盤上的位置。

2、動態輸出棋盤擺放形式的時候，自動輸出的速度太快，無法觀察清楚，後來只好運用getchar( )函式接受乙個空的字元手動控制棋盤的輸出。

五、測試結果及其分析

程式執行結果如下各圖所示：

分析：本次課程設計完成之後，仍覺得有些不足之處，例如無法讓電腦自動輸出動態的擺放皇后過程，必須手動操作完成。演算法的時間複雜度也不是很好。

各函式的時間複雜度如下：

int judge(int *p, int j時間複雜度為o(n)

int check(int queen, int i) 時間複雜度為o(n2)

void show(int queen時間複雜度為o(n9)

void print(int queen時間複雜度為o(n2)

void go(int queen, int i) 時間複雜度為o(n)

圖2 程式執行結果部分截圖(1)

圖3 程式執行結果部分截圖(2)

圖4 程式執行結果部分截圖(3)

圖5 程式執行結構部分截圖(4)

六、使用者使用說明

執行.exe程式按照提示，按回車輸出兩種結果。

七、參考文獻

【1】王崑崙李紅. 資料結構與演算法. 中國鐵道出版社. 2023年6月第一版.

【2】何欽銘顏暉. c語言程式設計. 高等教育出版社. 2023年4月第一版.

八、附錄

#include <>

int count=0定義乙個整型變數count來統計正確解法的個數

int queen[8定義陣列表示皇后所處的位置（queen[3]=2表示皇后在第三行和第二列上）

八皇后問題課程設計報告

資料結構課程設計八皇后問題

資料結構課程設計回溯法解決8皇后n皇后問題

車廂排程問題課程設計報告

八皇后問題課程設計報告

資料結構課程設計 八皇后問題

資料結構課程設計回溯法解決8皇后n皇后問題

車廂排程問題 課程設計報告

相關推薦

資料結構課程設計八皇后問題

車廂排程問題課程設計報告