八皇后問題課程設計

1、<p><b>　　八皇后問題課程設計</b></p><p><b>　　1設計背景</b></p><p>　　1．1課程設計的目的</p><p>　　本課程設計的目的在于提高學生對數(shù)據(jù)結構和C++語言課程的運用能力，并能使學生加深對數(shù)據(jù)結構和編程工作的理解。書本知識轉(zhuǎn)化成個人能力，最終還是要靠不斷地付諸實

2、踐，課程設計恰為這種時間提供了一個很好的平臺。</p><p>　　1.2課程設計任務與要求</p><p>　　程序啟動后顯示一張8*8的棋盤，然后游戲者可以用坐標輸入方式在棋盤上布下棋子。如果布下的棋子合法，則增加10分并可以繼承布下一個棋子。如果布下的棋子不合法，給出游戲者的得分數(shù)。</p><p>　　若無錯誤布下8顆棋子，則給與滿分100分。（由于本學期我

3、們尚未學習圖形界面的有關類容，所以課程設計中的有關圖形界面的內(nèi)容進行了修改。）</p><p>　　游戲規(guī)則要求不能在同一行或同一列或同一條對角線上放置二個或二個以上的棋子，但每行都必須放置一個棋子。</p><p><b>　　2 程序的實現(xiàn)過程</b></p><p>　　2.1設計思想、算法及實現(xiàn)要點</p><p&g

4、t;　　程序編寫都是由簡單到復雜的，接到任務以后，就在腦子里有了一個大概的框架。一個while（1）的打循環(huán)里嵌套一個界面輸入程序，通過用戶不斷地輸入來控制游戲的循環(huán)的繼續(xù)和跳出，并且在設計一個自動跳出的判斷語句。這樣，玩家就能在循環(huán)體里不斷布棋，直到玩家想終止游戲或者游戲過關成功。</p><p>　　關于下棋系統(tǒng)，首先要處理的就是棋盤，我把棋盤用賦值為0或1的二維數(shù)組來模擬國際象棋棋盤。</p>

5、<p>　　0代表無棋子，1代表已下的棋子。這樣就比較方便我以后判斷棋盤橫豎斜有且只有一個棋子，只需將橫豎斜的元素累加，結果等于1即可。</p><p>　　由于沒有真正的圖形界面，下棋的方法就只能依靠用戶輸入橫豎坐標了，輸入坐標后，系統(tǒng)自動將該坐標位置的元素賦值為1。</p><p>　　關于打分細則，我的設計是給一個基準分20分，正確下一個棋就加10分，這樣，當游戲過關時恰

6、好是100分。</p><p>　　具體到實際編程時，又考慮到，游戲程序的可玩性問題，我又在之前的的簡單框架上補充了悔棋的功能，并且能一次性悔多步棋子，這樣，打分細則又改變了：</p><p>　　起評分20分下對一顆棋子獎勵10分，若要悔棋，悔棋一步扣除15分。由于棧的特點是先進后出，后進先出，正好符合后下的棋子先悔，先下的棋后悔，于是我就很自然的想到建立一個簡單棧來存儲每一步玩家所走的

7、棋子。棧的內(nèi)容很簡單，只有壓入和彈出的函數(shù)，沒有過多防范數(shù)組越界、溢出等錯誤的處理。出錯問題由程序員負責。</p><p>　　剩下的就簡單了，用一個int類型的數(shù)記錄悔棋次數(shù)，評分系統(tǒng)就做好了。</p><p><b>　　2.2 程序的函數(shù)</b></p><p>　　程序主要有這幾個函數(shù)構成void display()用來輸出模擬的八皇后

8、8*8棋盤； void display(int ,int)這是對上一個函數(shù)的重載，這樣就允許先將一個特定位置的元素賦值為1，然后在輸出；bool deal()對棋盤進行橫、豎、斜等方面的處理，將棋盤的橫、豎、斜三條線上元素求和，當這些和里面有值大于1時，說明至少有一對換后發(fā)生沖突，此時返回false,反之則返回true; v

9、oid Main()是整個游戲的核心函數(shù)，里面設計了一個while（k），k是走棋的個數(shù)，所以k>0,該循環(huán)通常情況下無法終止，所以提示用戶下棋的頁面會一直循環(huán)出現(xiàn)，知道玩家成功闖關或者玩家提示想終止程序。</p><p><b>　　2.3系統(tǒng)測試</b></p><p>　　系統(tǒng)測試的階段我主要做的就是進行錯誤處理的工作，比如：</p><

10、;p>　　如果玩家輸入了不存在的錯誤坐標，系統(tǒng)會提示：“坐標錯誤！請您輸入1~8整數(shù)?！比缓笙到y(tǒng)會讓玩家更改輸入坐標，如果輸入了如重復的坐標，系統(tǒng)將會提示：“輸入坐標重復，請重新輸入。”直到玩家輸入正確的坐標位置；在悔棋的時候，如果輸入的悔棋步數(shù)超過當前步數(shù)，系統(tǒng)也會提示用戶正確輸入。并且各種提示信息都伴隨一個喇叭發(fā)音，引起玩家注意。</p><p>　　為了使界面看起來更加簡潔，每一次更新棋盤元素并輸出棋

11、盤之前，我都用了一個system(“CLS”)；的語句，使得整個游戲過程不會很撩人。</p><p><b>　　3 操作說明</b></p><p>　　整個游戲操作，用戶只需用數(shù)字鍵輸入棋子的坐標或悔棋的步數(shù)，以及用N/Y鍵判斷是否悔棋。輸入錯誤數(shù)據(jù)都會有系統(tǒng)伴隨喇叭發(fā)音的提示，N/Y鍵也對大小寫進行了處理。玩家可以很輕松的進行游戲，不必擔心錯誤的輸入造成整個游戲

12、系統(tǒng)的崩潰。</p><p><b>　　4 總 結</b></p><p>　　通過這一個星期的編程，覺得自己對于對數(shù)據(jù)結構和C++的編程運用能力有了很大的提高，不僅對堆棧有了切身的體會，了解了它的方便與麻煩之處，也同時把C++語言重新溫習了一遍，鞏固了上學期所學的知識。</p><p>　　這次課程設計更令我意識到了數(shù)據(jù)結構這一課程的

13、重要性，一個好的算法可依然程序更加簡單明了高效，試想如果是在上個學期然我們來編寫相同的程序，估計那程序可以想象會有多么的凌亂無序低效。</p><p><b>　　參考文獻</b></p><p>　　嚴蔚敏,吳偉民.數(shù)據(jù)結構（C語言版）[M].北京:清華大學出版社.1997:44-58</p><p>　　H.M.Deitel,P.J.Dei

14、tel.C++程序設計教程（第4版）[M].北京：清華大學出版社.2004:1-792</p><p><b>　　附錄</b></p><p><b>　　源程序如下：</b></p><p>　　#include <iostream></p><p>　　using namespac

15、e std;</p><p>　　///////////////建立一個簡單的棧/////////////////////////////////////////////////</p><p>　　class Stack</p><p><b>　　{</b></p><p>　　int mark[8];</p&

16、gt;<p><b>　　int *top;</b></p><p>　　// int *base;</p><p><b>　　public:</b></p><p><b>　　Stack()</b></p><p><b>　　{</

17、b></p><p>　　for(int i(0);i<=7;i++)mark[i]=-1;</p><p><b>　　top=mark;</b></p><p><b>　　} </b></p><p>　　void push(int e){*++top=e;}//向棧壓入一個元

18、素 </p><p>　　int get(){</p><p><b>　　int temp;</b></p><p>　　temp=*top;</p><p>　　*top--=-1;</p><p>　　return temp;}//彈出棧的一個元素 </p><p>

19、<b>　　};</b></p><p>　　////////////////////////////將棋盤轉(zhuǎn)換為一個二維數(shù)組////////////////////////////</p><p>　　int A[][8]={{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},</p><p

20、>　　{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},</p><p>　　{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}};</p><p>　　/////////////////////////////////////////////////////////////////////////////

21、///</p><p>　　void display();//輸出模擬的八皇后棋盤 </p><p>　　void display(int ,int);//display函數(shù)的重載 </p><p>　　void Main();//主體函數(shù) </p><p>　　bool deal();//對棋盤進行橫、豎、斜等方面的處理</p>

22、<p>　　/////////////////////////主函數(shù)/////////////////////////////////////////////////</p><p>　　int main()</p><p><b>　　{ </b></p><p>　　display();</p><p&

23、gt;<b>　　Main();</b></p><p>　　system("pause");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　///////////////////////

24、////輸出象棋棋盤/////////////////////////////////////////</p><p>　　void display()</p><p><b>　　{</b></p><p>　　cout<<"當前八皇后棋盤：\n";</p><p>　　for(int

25、i=0;i<=63;++i)//用一維方法處理二維數(shù)組</p><p><b>　　{</b></p><p>　　cout<<A[i/8][i%8]<<' ';</p><p>　　if(i%8==7)cout<<endl;</p><p><b>　

26、　}</b></p><p><b>　　}</b></p><p>　　///////////////////////////display函數(shù)的重載 ///////////////////////////////////</p><p>　　void display(int a,int b)</p><p&g

27、t;<b>　　{</b></p><p>　　cout<<"當前八皇后棋盤：\n";</p><p>　　A[a][b]=1;</p><p>　　for(int i=0;i<=63;++i)//用一維方法處理二維數(shù)組 </p><p><b>　　{</b>

28、</p><p>　　cout<<A[i/8][i%8]<<' ';</p><p>　　if(i%8==7)cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p&

29、gt;　　//////////////////////////菜單函數(shù)//////////////////////////////////////////////</p><p>　　void Main()</p><p><b>　　{ </b></p><p>　　int k(1);//記錄當前的步數(shù) </p><p&g

30、t;　　int x,y,judge(0);//橫豎坐標及悔棋次數(shù) </p><p>　　Stack X,Y;//兩個棧分別記錄每次的橫豎坐標輸入 </p><p><b>　　while(k){</b></p><p>　　while(1){//坐標輸入及坐標輸入的錯誤處理 </p><p>　　co

31、ut<<"請輸入第"<<k<<"個皇后的坐標";</p><p>　　cin>>x>>y;</p><p>　　if((x<1||x>8)||(y<1||y>8))cout<<"\a坐標錯誤！請您輸入1~8整數(shù)。\n";</p&g

32、t;<p>　　if(A[y-1][x-1]==1)cout<<"輸入坐標重復，請重新輸入。\n";</p><p>　　else break;</p><p><b>　　}</b></p><p>　　X.push(x-1);</p><p>　　Y.push(y-1);

33、//橫縱坐標入棧 </p><p>　　system("CLS");//清屏，使界面更加簡潔。 </p><p>　　display(y-1,x-1);</p><p>　　if(!deal()){</p><p>　　cout<<"游戲結束\n"<<"總得分：&quo

34、t;<<10*k+20-15*judge<<endl</p><p>　　<<"是否悔棋(Y/N)? (每步悔棋將扣除15分)\n";</p><p><b>　　char j;</b></p><p><b>　　cin>>j;</b></p>

35、;<p>　　if(j=='y'||j=='Y'){//輸入悔棋步數(shù)及錯誤處理 </p><p>　　cout<<"悔棋幾步？\n";</p><p><b>　　int i;</b></p><p><b>　　wh

36、ile(i){</b></p><p><b>　　cin>>i;</b></p><p>　　if(i>k||k<1)cout<<"\a請輸入1~"<<k<<"的悔棋數(shù)：\n";</p><p>　　else break;</

37、p><p>　　} </p><p><b>　　k=k-i;</b></p><p>　　for(int a(0);a<i;++a)//悔棋的實現(xiàn)，將坐標置零 </p><p>　　A[Y.get()][X.get()]=0; </p><p>　　judge=judg

38、e+i; </p><p>　　system("CLS");</p><p>　　display();</p><p><b>　　}</b></p><p>　　else break;</p><p><b>　　};</b></p>&l

39、t;p><b>　　if(k==8){</b></p><p>　　cout<<"恭喜你過關，總得分："<<10*k+20-15*judge;</p><p><b>　　break;</b></p><p><b>　　}</b></p>

40、<p><b>　　k++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　////////////////////////對棋盤進行計算//////////////////////////////////////////&l

41、t;/p><p>　　bool deal()</p><p><b>　　{</b></p><p>　　int temp0[8]={0}/*橫排上元素之和*/,temp1[8]={0}/*豎直線上的元素之和*/,</p><p>　　temp2[15]={0}/*右斜線上的元素之和*/,temp3[15]={0}/*左斜線

42、上的元素之和*/;</p><p>　　//橫排上元素求和的實現(xiàn)</p><p>　　for(int i(0);i<=7;++i)</p><p>　　for(int j(0);j<=7;++j)</p><p>　　temp0[i]+=A[i][j];</p><p>　　//豎直線上求和計算的實現(xiàn) &l

43、t;/p><p>　　for(int i(0);i<=7;++i)</p><p>　　for(int j(0);j<=7;++j)</p><p>　　temp1[i]+=A[j][i];</p><p>　　//斜線上求和計算的實現(xiàn) </p><p>　　for(int i(0);i<=7;++i)&

44、lt;/p><p>　　for(int j(0);j<=7;++j)</p><p><b>　　{</b></p><p>　　//右斜線上求和計算的實現(xiàn) </p><p>　　if(j+i>=8);</p><p>　　else temp2[i]+= A[j+i][j];</p

45、><p>　　if(j>i||i>6);</p><p>　　else temp2[i+8]+=A[j][7-i+j]; </p><p>　　//左斜線上求和計算的實現(xiàn)</p><p><b>　　if(i<j);</b></p><p>

46、　　else temp3[i]+=A[i-j][j];</p><p>　　if(i+j+1>7);</p><p>　　else temp3[i+8]+=A[7-j][i+j+1]; </p><p><b>　　}</b></p><p>　　//如果橫、豎、斜排元素和有一個大于1，則當前

47、皇后至少于之前一個皇后有沖突，返回false. </p><p>　　for(int i(0);i<=14;++i) </p><p><b>　　{</b></p><p>　　if(temp0[i/2]>1||temp1[i/2]>1||temp2[i]>1||temp3[i]>1)</p>&l

48、t;p>　　return false;</p><p><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　//////////////////////////////////////////////////////