八皇后問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告八八皇皇后后問問題題設(shè)計(jì)任務(wù)書課題名稱八皇后設(shè)計(jì)目的1. 調(diào)研并熟悉八皇后的根本功能、數(shù)據(jù)流程與工作規(guī)程；2. 學(xué)習(xí)八皇后相關(guān)的算法和基于 VC+集成環(huán)境的編程技術(shù)；3. 通過實(shí)際編程加深對根底知識的理解，提高實(shí)踐能力；4. 學(xué)習(xí)開發(fā)資料的收集與整理，學(xué)會撰寫課程設(shè)計(jì)報(bào)告。實(shí)驗(yàn)環(huán)境1. 微型電子計(jì)算機(jī)PC；2. 安裝 Windows 2000 以上操作系統(tǒng)，Visual C+6.0 開發(fā)工具。任務(wù)要求1. 利用課余時(shí)間去圖書館或上網(wǎng)查閱課題相關(guān)資料，深入理解課題含義及設(shè)計(jì)要求，注意材料收集與整理；2. 在第 16 周末之前完成預(yù)設(shè)計(jì)，并請指導(dǎo)教師審查，通

2、過前方可進(jìn)行下一步工作；3. 本課題要求至少用三種方法解決八皇后問題，輸入棋盤的階層，然后顯示共有多少種布局方案，并顯示每一種方案的具體情況。4. 結(jié)束后，及時(shí)提交設(shè)計(jì)報(bào)告含紙質(zhì)稿、電子稿，要求格式標(biāo)準(zhǔn)、內(nèi)容完整、結(jié)論正確，正文字?jǐn)?shù)不少于 3000 字不含代碼。工作進(jìn)度方案序號起止日期工 作 內(nèi) 容1在預(yù)設(shè)計(jì)的根底上，進(jìn)一步查閱資料，完善設(shè)計(jì)方案，形成書面材料。2設(shè)計(jì)總體方案，構(gòu)建、繪制流程框圖，編寫代碼，上機(jī)調(diào)試。3測試程序，優(yōu)化代碼，增強(qiáng)功能，撰寫設(shè)計(jì)報(bào)告。4提交軟件代碼、設(shè)計(jì)報(bào)告，參加辯論，根據(jù)教師反響意見，修改、完善設(shè)計(jì)報(bào)告。指導(dǎo)教師簽章： 2013 年 5 月 15 日 摘要： 眾所

3、周知的八皇后問題是一個非常古老的問題，具體如下：在 8*8 的國際象棋棋盤上放置了八個皇后，要求沒有一個皇后能吃掉另一個皇后，即任意兩個皇后都不處于棋盤的同一行、同一列或同一對角線上,這是做出這個課題的根底。要求編寫實(shí)現(xiàn)八皇后問題的遞歸解法或非遞歸解法，對于任意給定的一個初始位置，輸出八皇后問題的一個布局。本次設(shè)計(jì)旨在學(xué)習(xí)各種算法，訓(xùn)練對根底知識和根本方法的綜合運(yùn)用及變通能力，增強(qiáng)對算法的理解能力，提高軟件設(shè)計(jì)能力。在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。 要求熟練運(yùn)用 C+語言、根本算法的根底知識，獨(dú)立編制一個具有中等難度的、解決實(shí)際應(yīng)用問題的應(yīng)用程序。通過對題意的分析與計(jì)算，用遞歸

4、法回溯法及枚舉法解決八皇后是比較適合的。遞歸是一種比較簡單的且比較古老的算法。回溯法是遞歸法的升華，在用來求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而枚舉法，更是一種根底易懂簡潔的方法。把它們綜合起來，就構(gòu)成了今天的算法。不管用什么法做這個課題，重要的就是先搞清楚哪個位置是合法的放皇后的位置，哪個不能，要先判斷，后放置。關(guān)鍵詞：八皇后；遞歸法；回溯法；數(shù)組. 1 1 課題綜述課題綜述1.11.1 八皇后問題概述八皇后問題概述八皇后問題是一個古老而著名的問題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯 1850 提出；在 88 格的國際象棋上擺放八皇后，使其不能互相攻擊，即任意兩

5、個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認(rèn)為有 76 種方案。1854 年在柏林的象棋雜志上不同的作者發(fā)表了 40 種不同的解，后人有人用圖論的方法解出 92 宗結(jié)果。雖然問題的關(guān)鍵在于如何判定某個皇后所在的行、列、斜線是否有別的皇后；可以從矩陣的特點(diǎn)上找到規(guī)律，如果在同一行，那么行號相同；如果在同一列上，那么列號相同；如果同在“/斜線上的行列值之和相同；如果在對角線上，那么行列號之和或之差相等，逐個紀(jì)錄符合題意的情況,最終得出解。(如圖 1-1，是八皇后問題的一個實(shí)例圖) 圖 1-1 八皇后棋盤實(shí)例1.21.2 預(yù)期目標(biāo)預(yù)期目標(biāo)運(yùn)用 C+程序設(shè)計(jì)的編程思想編寫代碼，實(shí)

6、現(xiàn)八皇后問題的所有92 種擺放情況。要求在 DOS 界面上顯示出每一種方式。1 1 面對的問題面對的問題需要用三種方法解決八皇后問題，在這里需要查閱大量資料并多加練習(xí)，才能成功編寫程序。主要要解決下面的問題：沖突：包括列、行、兩條對角線；1. 列：規(guī)定每一列放一個皇后，就不會造成列上的沖突；2. 行：當(dāng)?shù)?i 行被某個皇后占據(jù)時(shí)，該行所有空格就都不能放置其他皇后；3. 對角線：對角線有兩個方向，在同一對角線上的所有點(diǎn)都不能有沖突。2 2 需求分析需求分析2.12.1 涉及到的知識根底涉及到的知識根底 類類.1.1 類定義.2.2 類函數(shù)定義 函數(shù).1.1 函數(shù)的定義.2.2 函數(shù)調(diào)用 選擇結(jié)構(gòu)

7、選擇結(jié)構(gòu).1.1 用 if 語句實(shí)現(xiàn)選擇結(jié)構(gòu)設(shè)計(jì).2.2 if 語句嵌套.3.3 while 和 do-while 語句 循環(huán)結(jié)構(gòu).1.1 for 語句.2.2 Break 語句 字符串處理函數(shù)字符串處理函數(shù)3 3 模塊及算法設(shè)計(jì)模塊及算法設(shè)計(jì)3.13.1 算法描述算法描述 遞歸法 回溯法3.23.2詳細(xì)流程圖詳細(xì)流程圖數(shù)據(jù)初始化從當(dāng)前點(diǎn)當(dāng)前方向開始，判斷能否向前走結(jié)束程序向前走一步入棧是否已到達(dá)目標(biāo)位置輸出結(jié)果新位置作為當(dāng)前點(diǎn)方向數(shù)加 1方向數(shù)是否超界退回一步退棧是否已經(jīng)回到起點(diǎn)能否否否是是是否 圖 3-3 解決八皇后問題的根本流程圖八皇后問題是在限制條件下的排序問題#include/數(shù)據(jù)流

8、輸入/輸出#include/參數(shù)化輸入/輸出#include/定義雜項(xiàng)函數(shù)及內(nèi)存分配函數(shù)#include/定義輸入/輸出函數(shù)static char Queen88; static int a8; /數(shù)組ai：ai表示第i個皇后放置的列,i的范圍：-8static int b15; /主對角線數(shù)組static int c15; /從對角線數(shù)組，根據(jù)程序的運(yùn)行，去決定主從對角線是否放入皇后static int iQueenNum=0; /記錄總的棋盤狀態(tài)數(shù)static int iNum=1;void iQueen(int i); /參數(shù)i代表行void measure1()int iLine; /

9、橫行int iColumn; /縱行 for(iLine=0;iLine8;iLine+) aiLine=0; /列標(biāo)記初始化，表示無列沖突 for(iColumn=0;iColumn8;iColumn+) QueeniLineiColumn=*; for(iLine=0;iLine15;iLine+) /主、從對角線標(biāo)記初始化，表示沒有沖突biLine=ciLine=0; iQueen(0);void iQueen(int i) /i為當(dāng)前處理的行int iColumn;for(iColumn=0;iColumn8;iColumn+) if(aiColumn=0&bi-iColumn

10、+7=0&ci+iColumn=0) /如果無沖突 QueeniiColumn=; /放皇后aiColumn=1; /標(biāo)記，下一次該列上不能放皇后 bi-iColumn+7=1; /標(biāo)記，下一次該主對角線上不能放皇后 ci+iColumn=1; /標(biāo)記，下一次該從對角線上不能放皇后if(i7)iQueen(i+1); /如果行還沒有遍歷(沿著某條搜索路線，依次對樹中每個結(jié)點(diǎn)均做一次且僅做一次訪問)完，進(jìn)入下一行else /否那么輸出 int iLine; /輸出棋盤狀態(tài)int iColumn;cout(遞歸法)皇后擺放方式的第iNum種情況為：endl; for(iLine=0;iLi

11、ne8;iLine+) for(iColumn=0;iColumn8;iColumn+) coutsetw(2)QueeniLineiColumn;coutendl; coutiNum: ;for(iLine=0;iLine8;iLine+) for(iColumn=0;iColumn8;iColumn+) if(QueeniLineiColumn=)cout(iLine+1,iColumn+1); coutnul); /從程序里調(diào)用pause命令,一個結(jié)果一個結(jié)果地看iNum+;coutendl;/如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，那么回溯，重新標(biāo)記QueeniiCol

12、umn=*; aiColumn=0; bi-iColumn+7=0; ci+iColumn=0; / if ends5 5 程序調(diào)試分析程序調(diào)試分析1)運(yùn)行時(shí)有些函數(shù)的頭文件未定義，導(dǎo)致無法進(jìn)行編譯；而且在調(diào)試時(shí)有些頭文件的使用范疇弄混淆了；2)開始編第一種方法遞歸回溯時(shí)，for與if的循環(huán)嵌套未能很好掌握，導(dǎo)致幾次調(diào)試都出現(xiàn)比較嚴(yán)重的錯誤；且在運(yùn)用該方法時(shí)，未能將八皇后問題的具體思路搞清，沒有考慮“如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求的問題；3)在統(tǒng)計(jì)方法的個數(shù)時(shí)，未將累加的那個整型變量進(jìn)行初始化，導(dǎo)致無法顯示，八皇后擺放的是“第X種情況，也無法統(tǒng)計(jì)出八皇后的排列方式是否一定是92種情況。5)未用setw( )函數(shù)時(shí)，顯示的結(jié)果相當(dāng)難看，所定義的標(biāo)志符都緊靠在一起；多加了一個換行符后，各種情況的間距增大，閱讀時(shí)舒服多了；6)如果將92種情形全部打印，那么前面的幾十種情況將無法顯示出，要想看到前面的狀態(tài)，必須添加一個控制語句，使其能一個一個的輸出。6 6 運(yùn)行與測試運(yùn)行與測試開始運(yùn)行界面，按enter后如圖 6-1所示圖 6-1 遞歸回溯法界面這是把皇后第一種方法運(yùn)行后顯示的界面，其中*是棋盤中棋子的位置，是棋盤中皇后的位置，坐標(biāo)表示在當(dāng)前情況下皇后所處位置總總 結(jié)結(jié)通過這次的課程設(shè)計(jì)，讓我了解了八皇后這一經(jīng)典的問題。同時(shí)讓我更好地掌握了