人工智能課程設(shè)計(jì)報(bào)告

1、人工智能課程設(shè)計(jì)報(bào)告設(shè)計(jì)三：八皇后學(xué)院：信息科學(xué)與工程學(xué)院班級(jí)：自動(dòng)化0703班姓名：宋金財(cái)學(xué)號(hào)：0901070305指導(dǎo)教師：陳白帆陳學(xué)2010年6月10日目錄一、概述1.1、 設(shè)計(jì)題目1.2、 系統(tǒng)主要內(nèi)容與功能二、設(shè)計(jì)流程及描述2.1、 設(shè)計(jì)流程圖2.2、 設(shè)計(jì)思路簡介三、運(yùn)行界面簡介3.1、 游戲模式界面演示3.2、 解答界面演示四、源程序代碼4.1、 游戲模式代碼4.2、 解答代碼五、課程設(shè)計(jì)體會(huì)5.1設(shè)計(jì)體會(huì)附錄參考文獻(xiàn)(一)概述設(shè)計(jì)題目：八皇后問題是一個(gè)古老而著名的問題,是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個(gè)皇后，使其

2、不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。系統(tǒng)主要內(nèi)容與功能設(shè)計(jì)內(nèi)容：在8*8的國際象棋棋盤上，放置8個(gè)皇后后，使8個(gè)棋子不能被相互對(duì)方吃掉。設(shè)計(jì)要求：(1)較好的人機(jī)操作界面，登陸界面應(yīng)有系統(tǒng)的各種功能信息。(2)能夠進(jìn)行基本的游戲操作，用不同的顏色在棋盤上表示能占用的格子和不能占用的。(3)當(dāng)程序出錯(cuò)后應(yīng)能可以重新開始進(jìn)行游戲(4)此系統(tǒng)應(yīng)包括答案解答功能，其中答案解答功能應(yīng)包括各種答案的游戲界面共有92種情況。(二)設(shè)計(jì)流程及描述2

3、.1設(shè)計(jì)流程圖:陽存中”九理圖算法基本流程圖主函數(shù):2 2設(shè)計(jì)思路簡介：由于這是一個(gè)平面上的棋子布局處理問題，因此我們可以將問題堪稱一個(gè)2維數(shù)組問題，不妨設(shè)這個(gè)8*8數(shù)組A，并假定第一行是為后一位置的位置，第二行為后衛(wèi)放置的位置，依次類推，8行分別存放8個(gè)后的位置，為了簡便處理，我們先將A（8,8）的初值設(shè)為1，一旦一個(gè)位置存放一個(gè)后，則其他后不能處于同一行，同一列，同一個(gè)斜線，將這些位置的數(shù)組元素的值設(shè)為0。2.1 在其中一個(gè)位置上有一后的數(shù)據(jù)處理設(shè)第m行，n列有一個(gè)后，則根據(jù)原則，分別從八個(gè)不同的方向?qū)?duì)應(yīng)的元素置為0。2.2 第K個(gè)后的位置設(shè)定假定前面:k-1個(gè)后的位置已經(jīng)確定，則第:K

4、個(gè)后只能放置在第K行中元素不為0的位置上。因此只需找到這個(gè)不為0的元素A（K,J），J就是第K個(gè)后的位置。2.3 最后一個(gè)后的位置確定如果第8行中有元素不為0，則表明你已經(jīng)找到了一種擺法，可以通過文本框text1輸將文本框的ScrollBar的屬性設(shè)為2-Vertivcal,Multiline屬性設(shè)為true。但是輸出后還要尋找是否有其它的擺法？如果第8行中元素均為0，則表明你的這種擺法不行，還得要嘗試其它的方法，看看是否能行？但是，如何嘗試其它的擺法呢？這就是問題的關(guān)鍵所在，需要我們回溯到以前的狀態(tài)，重新擺放！2.4 回溯處理回溯到以前的狀態(tài)可以用下面的算法來實(shí)現(xiàn)：（1） 尋找到第:個(gè)后的位

5、置。（2）將當(dāng)前數(shù)組6的值全部保存到另外一個(gè)數(shù)組"中，以便回溯時(shí)用到。（3）進(jìn)行%7%的數(shù)據(jù)處理。（4）尋找下一個(gè)后的位置。（5）不管是否找到正確擺放方法，都應(yīng)當(dāng)去嘗試其它方法。因此，必須再將B中的數(shù)據(jù)還原到數(shù)組A中進(jìn)行回溯處理。至此，八皇后問題的算法已基本解決，用戶可以從第一個(gè)后開始，通過多重循環(huán)逐個(gè)處理，完成設(shè)計(jì)，最終得到的92種不同的算法。2、 算法改進(jìn)由于通過多重循環(huán)進(jìn)行處理，8個(gè)后就需要8重循環(huán)處理，使得程序就顯得很長，效率不是很高，能否通過改進(jìn)程序來提高效率？值得我們?nèi)ヌ接憽?.1 對(duì)數(shù)據(jù)處理1.1的改進(jìn)根據(jù)問題的實(shí)際情況，由于后是按順序進(jìn)行處理的，因此當(dāng)你處理到第K個(gè)后

6、時(shí)，前面K-1個(gè)的位置已經(jīng)確立，也就是說前面K-1行數(shù)據(jù)已經(jīng)處理完畢，所以沒有必要在1.1中對(duì)向左上，向上，向右上三個(gè)方向的數(shù)據(jù)進(jìn)行處理，只需要處理1.1中其它5個(gè)方向即可。2.2 保存數(shù)據(jù)的改進(jìn)將數(shù)組A的當(dāng)前狀態(tài)存放到B數(shù)組中去，以便將來回溯時(shí)使用。由于回溯并不是回到初始狀態(tài)，因此沒有必要將整個(gè)數(shù)組全部保存，只需部分保存即可。例如，你在處理第K個(gè)后時(shí)，只要將第K行到第8行數(shù)組A中的數(shù)據(jù)保存?；厮輹r(shí)，只要將第K行之后的元素還原即可。2.3 多重循環(huán)的改進(jìn)2.4 個(gè)后，使用8重循環(huán)，而且處理的方法類同，使得我們的程序冗長，用戶可以使用遞歸算法來縮短程序的長度。算法如下：（ 1） 尋找第K個(gè)后（

7、2） 確定第K個(gè)后的位置（ 3） 保存K行之后的數(shù)（$7$）（ 4） 進(jìn)行第K個(gè)后位置確定后的數(shù)據(jù)處理（2.1）（ 5） K=K+1;（ 6） 如果K不大于8，重復(fù)（1），進(jìn)行遞歸處理。如果等于8，進(jìn)行（ 7） 處理（ 8） 如果找到擺法，在文本框中輸出。（ 9） K=K-1（ 10） 還原第K行后的數(shù)據(jù)，處理第K個(gè)后的其它擺法。3、 算法比較通過改進(jìn)程序算法，運(yùn)行效率明顯提高，其中實(shí)際運(yùn)算時(shí)間提高%50，程序長度縮短%40。三、運(yùn)行界面簡介游戲開始界面：,(2)游戲幫助信息此部分包括兩部分:(1)當(dāng)游戲失敗后可以進(jìn)行重新開始游戲游戲運(yùn)行界面：很明顯此游戲完成失??！成功的完成游戲！答案解答界面

8、：此部分包含兩個(gè)模塊：運(yùn)算和顯示模塊此為其計(jì)算的結(jié)果，共有92中不同的結(jié)果。選擇自己希望的答案組數(shù)以上為對(duì)應(yīng)的顯示的答案，從中可以看出游戲成功!四、源程序代碼4、 1、游戲模式代碼OptionExplicitDimSd(63)AsIntegerDimCntAsIntegerPrivateSubForm_Load()Me.Caption="八皇后游戲"Me.Width=5000Me.Height=5500DimmAsInteger,nAsIntegerWithPicture1(0).Left=500.Top=500.Width=500.Height=500.BackColor

9、=vbWhiteEndWith'初始化，載入8*8個(gè)格Form=0To7Forn=0To7Ifm=0Andn=0Thenn=1LoadPicture1(m*8+n)WithPicture1(m*8+n).Left=(n+1)*500.Top=(m+1)*500.Width=500.Height=500.BackColor=vbWhite.Visible=TrueEndWithNextNextEndSubPrivateSubhp_Click()MsgBox"請(qǐng)?jiān)谙旅?*8共64個(gè)方格中填入8個(gè)綠色方格"&vbCrLf&"要求這8個(gè)綠色方格兩兩

10、之間不能共行或共列,也不能共斜線"&vbCrLf&Space(60)&"-xinfresh編寫",vbInformation,"游戲幫助"EndSubPrivateSubPicture1_Click(IndexAsInteger)IfPicture1(Index).BackColor=vbWhiteThen'未用Picture1(Index).BackColor=vbGreen'該格標(biāo)綠，說明已選中Cnt=Cnt+1Form1.Caption=Left(Form1.Caption,5)&"

11、;已放入"&CStr(Cnt)&"個(gè)皇后"IfCnt=8ThenMsgBox"恭喜您成功完成！強(qiáng)人！",vbInformation,"強(qiáng)烈恭喜！"CallReSt_ClickExitSubEndIfElseIfPicture1(Index).BackColor=vbGreenThen'已選用，撤銷Picture1(Index).BackColor=vbWhite'該格標(biāo)白，說明未用Cnt=Cnt-1Form1.Caption=Left(Form1.Caption,5)&"已放

12、入"&CStr(Cnt)&"個(gè)皇后"ElseExitSubEndIfDimmAsInteger,nAsInteger,pAsInteger,qAsIntegerm=Index8'獲得當(dāng)前行n=IndexMod8'獲得當(dāng)前列DimfcAsColorConstantsDimtmpaddAsIntegerIfPicture1(Index).BackColor=vbWhiteThenfc=vbWhitetmpadd=-1EndIfIfPicture1(Index).BackColor=vbGreenThenfc=vbRedtmpadd=1E

13、ndIf'同行變色p=m-1DoWhilep>=0WithPicture1(p*8+n).BackColor=fcSd(p*8+n)=Sd(p*8+n)+tmpaddIfSd(p*8+n)>0Then.BackColor=vbRedElseIfSd(p*8+n)<0ThenSd(p*8+n)=0EndIfEndWithp=p-1Loopp=m+1DoWhilep<=7WithPicture1(p*8+n).BackColor=fcSd(p*8+n)=Sd(p*8+n)+tmpaddIfSd(p*8+n)>0Then.BackColor=vbRedElseI

14、fSd(p*8+n)<0ThenSd(p*8+n)=0EndIfEndWithp=p+1Loop'同列變色q=n-1DoWhileq>=0WithPicture1(m*8+q).BackColor=fcSd(m*8+q)=Sd(m*8+q)+tmpaddIfSd(m*8+q)>0Then.BackColor=vbRedElseIfSd(m*8+q)<0ThenSd(m*8+q)=0EndIfEndWithq=q-1Loopq=n+1DoWhileq<=7WithPicture1(m*8+q).BackColor=fcSd(m*8+q)=Sd(m*8+q)+

15、tmpaddIfSd(m*8+q)>0Then.BackColor=vbRedElseIfSd(m*8+q)<0ThenSd(m*8+q)=0EndIfEndWithq=q+1Loop'左斜變色p=m-1:q=n+1DoWhilep>=0Andq<=7WithPicture1(p*8+q).BackColor=fcSd(p*8+q)=Sd(p*8+q)+tmpaddIfSd(p*8+q)>0Then.BackColor=vbRedElseIfSd(p*8+q)<0ThenSd(p*8+q)=0EndIfEndWithp=p-1:q=q+1Loopp=

16、m+1:q=n-1DoWhilep<=7Andq>=0WithPicture1(p*8+q).BackColor=fcSd(p*8+q)=Sd(p*8+q)+tmpaddIfSd(p*8+q)>0Then.BackColor=vbRedElseIfSd(p*8+q)<0ThenSd(p*8+q)=0EndIfEndWithp=p+1:q=q-1Loop'左斜變色p=m-1:q=n-1DoWhilep>=0Andq>=0WithPicture1(p*8+q).BackColor=fcSd(p*8+q)=Sd(p*8+q)+tmpaddIfSd(p*8+

17、q)>0Then.BackColor=vbRedElseIfSd(p*8+q)<0ThenSd(p*8+q)=0EndIfEndWithp=p-1:q=q-1Loopp=m+1:q=n+1DoWhilep<=7Andq<=7WithPicture1(p*8+q).BackColor=fcSd(p*8+q)=Sd(p*8+q)+tmpaddIfSd(p*8+q)>0Then.BackColor=vbRedElseIfSd(p*8+q)<0ThenSd(p*8+q)=0EndIfEndWithp=p+1:q=q+1LoopEndSubPrivateSubReSt

18、_Click()DimmAsIntegerForm=0To63Picture1(m).BackColor=vbWhiteSd(m)=0NextCnt=0Form1.Caption=Left(Form1.Caption,5)&"已放入"&CStr(Cnt)&"個(gè)皇后"EndSub5、 2、解答代碼OptionExplicitDimCountAAsIntegerDimAnsw()AsIntegerPrivateSubForm_Load()Me.Caption="八皇后求解Me.Width=5000Me.Height=5500

19、DimmAsInteger,nAsIntegerWithPicture1(0).Left=500.Top=500.Width=500.Height=500.BackColor=vbWhiteEndWith'初始化，載入8*8個(gè)格Form=0To7Forn=0To7Ifm=0Andn=0Thenn=1LoadPicture1(m*8+n)WithPicture1(m*8+n).Left=(n+1)*500.Top=(m+1)*500.Width=500.Height=500.BackColor=vbWhite.Visible=TrueEndWithNextNextEndSubPrivat

20、eSubForm_Unload(CancelAsInteger)Close答案數(shù)據(jù).txt"EndSubPrivateSubPicture1_Click(IndexAsInteger)EndSubPrivateSubStart_Click()'以第0行起始，起始時(shí)皇后數(shù)Cnt為0DimCurRowAsIntegerDimCntAsIntegerDimkAsInteger,mAsInteger,nAsIntegerDimStas(7,7)AsBoolean'表示該位是否可用CurRow=0Cnt=0'初始化各格狀態(tài)，均為可用Form=0To7Forn=0To7S

21、tas(m,n)=TrueNextNextCallEp(Stas,CurRow,Cnt)ReDimAnsw(1,7,CountA-1)'讀入答案數(shù)據(jù)答案數(shù)據(jù).txt"ForInputAs#1Fork=0ToCountA-1Form=0To7Forn=0To1Input#1,Answ(n,m,k)NextNextNextMsgBox"共有"&CStr(CountA)&"組答案",vbInformation,"解題完成"EndSubPrivateSubEp(ByRefSts()AsBoolean,ByVa

22、lSubRowAsInteger,ByValSubCntAsInteger)DimmAsInteger,nAsInteger,kAsIntegerDimSubSts(7,7)AsBooleanFork=0To7IfSts(SubRow,k)ThenIfSubCnt+1=8ThenCallOts(Sts)'已填完八個(gè)皇后，輸出CountA=CountA+1ExitSubEndIfIfSubRow+1=8ThenExitSubEndIf'復(fù)制狀態(tài)數(shù)組Form=0To7Forn=0To7SubSts(m,n)=Sts(m,n)NextNextCallChgSt(SubSts,SubR

23、ow,k)放入皇后，依皇后位置調(diào)整狀態(tài)數(shù)組CallEp(SubSts,SubRow+1,SubCnt+1)EndIfNextEndSubPrivateSubChgSt(ByRefSbsts()AsBoolean,ByValRowAsInteger,ByValColAsInteger)'由皇后位置(Row,Col),改變狀態(tài)DimmAsInteger,nAsInteger'行變m=RowDoWhilem-1>=0m=m-1Sbsts(m,Col)=FalseLoopm=RowDoWhilem+1<=7m=m+1Sbsts(m,Col)=FalseLoop'列變

24、n=ColDoWhilen-1>=0n=n-1Sbsts(Row,n)=FalseLoopn=ColDoWhilen+1<=7n=n+1Sbsts(Row,n)=FalseLoop'左上右下斜m=Row:n=ColDoWhilem-1>=0Andn-1>=0m=m-1:n=n-1Sbsts(m,n)=FalseLoopm=Row:n=ColDoWhilem+1<=7Andn+1<=7m=m+1:n=n+1Sbsts(m,n)=FalseLoop'左下右上斜m=Row:n=ColDoWhilem-1>=0Andn+1<=7m=m-1

25、:n=n+1Sbsts(m,n)=FalseLoopm=Row:n=ColDoWhilem+1<=7Andn-1>=0m=m+1:n=n-1Sbsts(m,n)=FalseLoopEndSubPrivateSubOts(ByRefGetSts()AsBoolean)DimmAsInteger,nAsInteger答案數(shù)據(jù).txt"ForAppendAs#1Form=0To7Forn=0To7IfGetSts(m,n)ThenWrite#1,m,nEndIfNextNextClose#1EndSubPrivateSubSw_Click()DimkAsInteger,mAsI

26、nteger,nAsIntegerk=Val(InputBox("顯示第幾組答案?(192)","選擇答案號(hào)","1")Ifk<1Ork>92OrInt(k)<>kThenMsgBox"組號(hào)不對(duì)!",vbCritical,"Error"ExitSubEndIfForm=0To7Forn=0To7Picture1(m*8+n).BackColor=vbRedNextNextForn=0To7Picture1(Answ(0,n,k-1)*8+Answ(1,n,k-1).BackColor=vbGreenNextEndSub五、課程設(shè)計(jì)體會(huì)第一次接觸這個(gè)題目覺得很容易，可是當(dāng)自己真正去做的時(shí)候才知道有很多東西都有很大的問題，剛開始準(zhǔn)備用C語言寫的，后來選擇了VB,于是就花了2周時(shí)間去看了下VB的基本的編程方法，發(fā)現(xiàn)很容易上手，就慢慢的開始進(jìn)行了設(shè)計(jì)。但是可能是急于求成，在設(shè)計(jì)中程序一直無法運(yùn)行，后來才發(fā)現(xiàn)自己對(duì)算法并