馬踏棋盤(pán)問(wèn)題摘要：馬踏棋盤(pán)就是在國(guó)際象棋8X8棋盤(pán)上面，按照國(guó)際象棋規(guī)則中馬的行進(jìn)規(guī)則，實(shí)現(xiàn)從任意初始位置，每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部64個(gè)方格。理解棧的 “后進(jìn)先出”的特性以及學(xué)會(huì)使用回溯。關(guān)鍵字：馬踏棋盤(pán)、遞歸、棧、回溯1引言馬踏棋盤(pán)就是在國(guó)際象棋8X8棋盤(pán)上面，按照國(guó)際象棋規(guī)則中馬的行進(jìn)規(guī)則，實(shí)現(xiàn)從任意初始位置，每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部64個(gè)方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2.64依次填入一個(gè)8X8的方陣，并輸出它的行走路線。輸入：任意一個(gè)起始位置；輸出：無(wú)重復(fù)踏遍棋盤(pán)的結(jié)果，以數(shù)字1-64表示行走路線。2需求分析（1）需要輸出一個(gè)8X8的棋盤(pán)，可以采用二維數(shù)組的方法實(shí)現(xiàn)。（2）輸入馬的起始位置，必須保證輸入的數(shù)字在規(guī)定范圍內(nèi)，即0<=X<=7,0<=Y<=7。（3）保證馬能走遍整個(gè)棋盤(pán)，并且不重復(fù)。（4）在棋盤(pán)上輸出馬的行走路線,標(biāo)記好數(shù)字1、2、3直到64。3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)采用棧數(shù)組為存儲(chǔ)結(jié)構(gòu)。#define maxsize 100struct int i; int j;int director;stackmaxsize;4算法設(shè)計(jì)4.1 馬的起始坐標(biāo)void location(int x,int y) /馬的位置坐標(biāo)的初始化top+;stacktop.i=x; /起始位置的橫坐標(biāo)進(jìn)棧stacktop.j=y; /起始位置的豎坐標(biāo)進(jìn)棧stacktop.director=-1;axy=top+1; /標(biāo)記棋盤(pán)Try(x,y); /探尋的馬的行走路線4.2 路徑探尋函數(shù)void Try(int i,int j) int count,find,min,director; int i1,j1,h,k,s; int b8=-2,-2,-1,1,2,2,1,-1,c8=1,-1,-2,-2,-1,1,2,2; /存儲(chǔ)馬各個(gè)出口相對(duì)當(dāng)前位置行、列坐標(biāo)的增量數(shù)組 int b28,b18; for(h=0;h<=7;h+) /用數(shù)組b18記錄當(dāng)前位置的下一個(gè)位置的可行路徑的條數(shù) count=0; i=stacktop.i+ch; j=stacktop.j+bh; if(i>=0&&i<=7&&j>=0&&j<=7&&aij=0) /如果找到下一個(gè)位置 for(k=0;k<=7;k+) i1=i+ck; j1=j+bk;if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&ai1j1=0) /如果找到下一個(gè)位置 count+; /記錄條數(shù)b1h=count; /將條數(shù)存入b18中 for(h=0;h<=7;h+) /根據(jù)可行路徑條數(shù)的大小，從小到大排序，并放入數(shù)組b28中 min=9; for(k=0;k<=7;k+) if(min>b1k) min=b1k; b2h=k; s=k; b1s=9; find=0; director=stacktop.director; for(h=director+1;h<=7;h+)/向8個(gè)方向進(jìn)行尋找i=stacktop.i+cb2h;j=stacktop.j+bb2h;if(i>=0&&i<=7&&j>=0&&j<=7&&aij=0)stacktop.director=h; /存儲(chǔ)棧的尋找方向top+; /進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-1;/重新初始化下一棧的方向 aij=top+1; find=1; /找到下一位置 break; if(find!=1)astacktop.istacktop.j=0; /清除棋盤(pán)的標(biāo)記 top-; /退棧 if(top<63)Try(i,j); /遞歸4.3輸出函數(shù)void display()int i,j;for(i=0;i<=7;i+) for(j=0;j<=7;j+) printf("t%d ",aij); /輸出馬的行走路線 printf("nn");printf("n");5.程序?qū)崿F(xiàn)5.1 主函數(shù)void main()int i,j,x,y;for(i=0;i<=7;i+) /棋盤(pán)的初始化for(j=0;j<=7;j+)aij=0;printf("輸入X Y (0=<X<=7,0=<Y<=7)n");scanf("%d%d",&x,&y);if(x>=0&&x<=7&&y>=0&&y<=7) /判斷輸入的起始位子是否正確location(x,y); display();else printf("錯(cuò)誤n");5.2運(yùn)行結(jié)果（1）當(dāng)輸入不符合要求時(shí) （2）正確輸入時(shí)5.3 算法分析（1）馬的起始坐標(biāo) 一開(kāi)始先建立一個(gè)棧數(shù)組，里面包括橫坐標(biāo)和豎坐標(biāo)還有方向。輸入馬的起始位置，進(jìn)入坐標(biāo)起始化函數(shù)，讓輸入的橫坐標(biāo)和豎坐標(biāo)進(jìn)棧，并初始化方向，并且標(biāo)記棋盤(pán)，指示此位置已走過(guò)，此時(shí)的位置是棧的第一個(gè)元素，進(jìn)入路徑探尋函數(shù)。（2）路徑探尋函數(shù) 路徑探尋函數(shù)中有兩個(gè)分別存儲(chǔ)馬各個(gè)出口相對(duì)當(dāng)前位置行、列坐標(biāo)的增量數(shù)組。要使馬走遍所有的棋盤(pán)，必須要有一定的行走規(guī)律。我使用的是記錄當(dāng)前位置的下一個(gè)位置的可行路徑的條數(shù)，并對(duì)它們進(jìn)行排序，按從小到大的順序存儲(chǔ)在一個(gè)一維數(shù)組中。開(kāi)始進(jìn)行探尋，分別向8個(gè)方向探尋，如果找到一個(gè)方向可行，則存儲(chǔ)棧的尋找方向，再進(jìn)棧，重新初始化棧的尋找方向，并用二維數(shù)組標(biāo)記此位置，再使用遞歸進(jìn)入下一次新的探尋。如果在某一次探尋中，沒(méi)能找到方向，則清除該位置的標(biāo)記，并退棧，再次遞歸，回到上次的尋找方向（之前已經(jīng)存儲(chǔ)過(guò)棧的尋找方向），跳過(guò)已經(jīng)尋找過(guò)的方向，再進(jìn)行探尋，直到全部棋盤(pán)都被走遍。（3）輸出函數(shù) 當(dāng)馬走遍所有的棋盤(pán)時(shí)，輸出馬的行走路線，因?yàn)橹耙呀?jīng)把馬的行走路線記錄在二維數(shù)組中了，所以此時(shí)只需把二維數(shù)組中的標(biāo)記輸出即可。6.設(shè)計(jì)體會(huì) 本次課程設(shè)計(jì)讓我學(xué)會(huì)了很多東西，使得我對(duì)于棧的理解更深入了，使用更加熟練。是此之前，我對(duì)于回溯并不是特別了解，但是這次設(shè)計(jì)讓我學(xué)會(huì)了回溯的基本概念以及基礎(chǔ)的用法。當(dāng)一件事情有很多種方法進(jìn)行時(shí)，我們要將所有的方法集合起來(lái)形成一個(gè)集合，再用一定的規(guī)律去調(diào)用這個(gè)集合內(nèi)的方法。剛開(kāi)始的時(shí)候，我并不能讓馬走遍所有的棋盤(pán)，但當(dāng)我知道了回溯的思想之后，我修正了我的算法，最終使馬走遍所有的棋盤(pán)。我還考慮了遞歸與非遞歸的問(wèn)題，在試驗(yàn)了兩種方法之后，發(fā)現(xiàn)兩種都可以，在時(shí)間的復(fù)雜度上也沒(méi)有太大的差別（顯示棋盤(pán)的時(shí)間上），但我還是使用的是遞歸的方法來(lái)完成本次設(shè)計(jì)。參考文獻(xiàn)：1 嚴(yán)蔚敏、吳偉民編著數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）北京：清華大學(xué)出版社，2 譚浩強(qiáng)主編C程序設(shè)計(jì)（第三版）北京：清華大學(xué)出版，20053 張蕊、呂濤主編C程序設(shè)計(jì)教程. 華中科技大學(xué)出版，2012