馬走日演算法

① . 編寫程序求解騎士巡遊問題：在n行n列的棋盤上（如n=5），假設一位騎士（按象棋中「馬走日」的行走法）從

這個是我之前做的演算法，但然我也是參考了網上提供的思想來做的。這個思想很廣泛。把你輸入的一個點為第一步，接著搜他可走8個方向中每一個可走的點，並記錄這樣可走的點的位置。再把這些記錄的點再搜他可走的8個方向，但這些只要記錄8個方向中可走方向的數目。接著就走方向最少的一條路。這樣難走的路在前面已經走了，後面的路就好走很多了，一般都能找到方向。當然還有遞歸這種演算法，但高維度的遞歸是沒有意議的，電腦是算不出來的或著用很長時間才能算出來。下面是我的演算法

#include<iostream>
using namespace std;
//定義棋盤的大小
#define N 8
#define LOSE 0
#define SUCCEED 1

void printknightgo(); //輸出結果
int knightgo(int x,int y); //運算走法

int chessboard[8][8] = { 0 }; //建立棋盤

void main(){

int x,y;
cout<<"請輸入坐標"<<endl;
cin>>x>>y; //輸入坐標
if(knightgo(x,y)){ //開始運算走法，如果成功則返回成功，否則返回失敗
cout<<"成功完成"<<endl;

}
else{
cout<<"失敗"<<endl;

}
printknightgo(); //輸出結果
}

//輸出結果的演算法
void printknightgo(){
for(int i = 0;i < N; i++){
for(int j = 0;j < N;j++){
cout<<chessboard[i][j]<<"\t";
}
cout<<endl;
}
}

int knightgo(int x,int y){
chessboard[x][y] = 1;//將第一步標為1
int step;//走的步數
int nextx[8] = {-1,1,-2,2,-2,2,-1,1};//走的X的步法
int nexty[8] = {2,2,1,1,-1,-1,-2,-2};//走的Y的步法
int recordNextx[8]={0};//記住下步可走X的位置，並用count來記數
int recordNexty[8]={0};//記住下步可走Y的位置，並用count來記數
int tempx,tempy;//用於臨時記住X和Y
int i,j;//臨時計數變數
int count = 0;//記住可循環的個數
int exist[8]={0};//第2次找8個方向每個可走的記錄
for(int step = 2;step <=N*N;step++){//把輸進來或循環的位置，找下一個能走的位置,並記住這些位置和可走的個數
for(i = 0;i < 8;i++){ //把上次記錄重置0;
recordNextx[i] = 0;
recordNexty[i] = 0;
exist[i] = 0;
}

count = 0;
for(i = 0;i < 8;i++){//第一次循環，找可走的個位置，並記錄可走方向的個數
tempx = x + nextx[i];//tempx為臨時記錄X
tempy = y + nexty[i];//tempy為臨時記錄Y
if(chessboard[tempx][tempy] == 0 && tempx >= 0 && tempx < N && tempy >= 0 && tempy < N){//當這個位置沒走過和不走出盤外時，才能記錄
recordNextx[count] = tempx;
recordNexty[count] = tempy;//記錄可走方向的x,y坐標
count++; //記錄可以走的方向的個數
}
}

//把記住的位置,找他們的下個能走位置的個數,就是重復上面循環，只需記錄可走方向的個數

if(count == 0){//如果沒有出路則返回失敗
return LOSE;
}

else {//如果只有一條路，則走這一條路
if(count == 1){
x = recordNextx[0];//因為可走方向只有一個，所記錄中就有recordNext(x,y)[0];
y = recordNexty[0];
chessboard[x][y] = step; //把第幾步寫入這個棋盤的位置
}

else{//有多條路可以走的話
for(j = 0;j < count;j++){//第一個點記錄的可走的方向，並找出們下一個方向可以走的的方向的個數
for(i = 0;i < 8;i++){//找第2個點8個方向可走的方向
tempx = recordNextx[j] + nextx[i];
tempy = recordNexty[j] + nexty[i];
if(chessboard[tempx][tempy] == 0 && tempx >= 0 && tempx < N && tempy >= 0 && tempy < N){//當這個位置沒走過和不走出盤外時，才能記錄
exist[j]++;//記錄第2個點可走方向的個數
}
}
}
//找最方向個數最小的一條路
int min = exist[0];
int last = 0;//用於記住，recordNext(x,y)中可走方向中，能走方向數目最小的一個方向
for(i = 1;i < count;i++){//找出方向數目最小的數和方向
if(exist[i]<min){
min = exist[i];
last = i;
}
}

x = recordNextx[last];//將這個方向給x,y;
y = recordNexty[last];
chessboard[x][y] = step; //將這個步數寫出這個棋盤
}

}
}

return SUCCEED;
}

② c++騎士巡遊「馬走日」問題，已用函數實現，求大神把函數封裝成類實現，一定得有類

//下面就是用類實現的該問題，你自己參考一下。
#include<iostream>
#include<iomanip>//I/O流控制頭文件,setw()的頭文件,setw(n)設域寬為n個字元
#defineN12//定義一個宏並賦初值
usingnamespacestd;
classxiangqi
{
private:
intb[N][N];//定義全局性的二維數組保存步數
boola[N][N];//記錄某一點是否已經走過
intnum;//=0;//記錄方案數
intdx[9];//={0,1,1,-1,-1,2,2,-2,-2};
intdy[9];//={0,2,-2,2,-2,1,-1,1,-1};//提供每一步的走法
public:
xiangqi()//構造函數，初始化數據
{
num=0;
dx[0]=0;
dx[1]=dx[2]=1;
dx[3]=dx[4]=-1;
dx[5]=dx[6]=2;
dx[7]=dx[8]=-2;
dy[0]=0;
dy[1]=2;
dy[2]=-2;
dy[3]=2;
dy[4]=-2;
dy[5]=1;
dy[6]=-1;
dy[7]=1;
dy[8]=-1;
}
voidsolve(inti,intj,intk,bool&ok,intn)//計算走法
{
intm,x1,y1,n1,n2;
boolt1,t2;//布爾變數
for(m=1;m<=8;m++)
{
x1=i+dx[m];
y1=j+dy[m];
t1=((x1>=0)&&(x1<n));//判斷x是否在棋盤內
t2=((y1>=0)&&(y1<n));//判斷y是否在棋盤內
if((t1==true)&&(t2==true)&&(a[x1][y1]==true))
{
a[x1][y1]=false;//記錄該點已經走過
b[x1][y1]=k;
if(k<n*n)
{
solve(x1,y1,k+1,ok,n);
}
else
{
num++;//方案數加一
ok=true;
cout<<"方案"<<num<<":"<<endl;
for(n1=0;n1<n;n1++)
{
for(n2=0;n2<n;n2++)
{
cout<<setw(4)<<b[n1][n2];//依次輸出經過每一點時的步數
}
cout<<endl;
}//return;
}
a[x1][y1]=true;
}
}
}
voidsetA(inti,intj,boolvalue)//數據訪問介面
{
a[i][j]=value;
}
voidsetB(inti,intj,intvalue)//數據訪問介面
{
b[i][j]=value;
}
};
intmain()
{
xiangqiqi;
inti,j,row,col,n;
boolok=false;
cout<<"請輸入n：";
cin>>n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
qi.setA(i,j,true);
}

cout<<"請輸入起始位置的坐標:";
cin>>row>>col;
//b[row-1][col-1]=1;//設置起始點
qi.setB(row-1,col-1,1);
//a[row-1][col-1]=false;
qi.setA(row-1,col-1,false);
qi.solve(row-1,col-1,2,ok,n);
//solve(row-1,col-1,2,ok,n);//調用函數計算結果
if(!ok)
cout<<"從點("<<row<<","<<col<<")出發無法遍訪棋盤的每一個位置"<<endl;
return0;
}

③ 國際象棋軟體和象棋軟體哪個的演算法要復雜些

國際象棋要復雜,看規則多少
象棋：

第一章 行棋規定

第1條 棋盤和棋子
1.1象棋盤由九道直線和十道橫線交叉組成。棋盤上共有九十個交叉點，象棋子就擺在和活動在這些交叉點上。
棋盤中間沒有劃通直線的地方，叫做「河界」；劃有斜交叉線的地方，叫做「九宮」。
九道直線，紅棋方面從右到左用中文數字一至九來代表；黑棋方面用阿拉伯數字1至9來代表。
1.2 棋子共有三十二個，分為紅、黑兩組，每組共十六個，各分七種，其名稱和數目如下： 象棋的擺法
紅棋子：帥一個，車、馬、炮、相、士各兩個，兵五個。
黑棋子：將一個，車、馬、炮、象、士各兩個，卒五個。
1.3 對局開始前，雙方棋子在棋盤上的擺法見右圖（印刷體棋圖規定：紅方棋子在下，用陽文；黑方棋子在上，用陰文）。
1.4 比賽用的標准棋盤，應每格都為正方形，每方格長寬均應為3.2至4.6cm。每個平面圓形棋子直徑應為2.7至3.2cm，大小與棋盤合適配套。棋盤和棋子底色，均應為白色或淺色。棋盤上直線和橫線應為紅色或深色，四周應有適當空白面積。棋子面色分為紅黑兩組，字體和圓框應當醒目。
演示比賽用的大棋盤為直式，紅方在下，黑方在上。棋盤和棋子大小，應配合場所相應增大。
第2條 走棋和吃子
2.1 對局時，由執紅棋的一方先走，雙方輪流各走一著，直至分出勝、負、和，對局即終了。
輪到走棋的一方，將某個棋子從一個交叉點走到另一個交叉點，或者吃掉對方的棋子而佔領其交叉點，都算走了一著。
雙方各走一著，稱為一個回合。
2.2 各種棋子的走法如下：
帥（將）每一著只許走一步，前進、後退、橫走都可以，但不能走出「九宮」。將和帥不準在同一直線上直接對面，如一方已先佔據，另一方必須迴避。
士每一著只許沿「九宮」斜線走一步，可進可退。
相（象）不能越過「河界」，每一著斜走兩步，可進可退，即俗稱「相（象）走田字」。當田字中心有別的棋子時，俗稱「塞（相）象眼」，則不許走過去。
馬每著走一直（或一橫）一斜，可進可退，即俗稱「馬走日字」。如果在要去的方向有別的棋子擋住。俗稱「蹩馬腿」，則不許走過去。
車每一著可以直進、直退、橫走，不限步數。
炮在不吃子的時候，走法同車一樣。
兵（卒）在沒有過「河界」前，每著只許向前直走一步；過「河界」後，每著可向前直走或橫走一步，但不能後退。
2.3 走一著棋時，如果己方棋子能夠走到的位置有對方棋子存在，就可以把對方棋子吃掉而佔領那個位置。只有炮吃子時必須隔一個棋子（無論是哪一方的）跳吃，即俗稱「炮打隔子」。
除帥（將）外其他棋子都可以聽任對方吃，或主動送吃。吃子的一方，必須立即把被吃掉的棋子從棋盤上拿走。
第3條 將死和困斃
3.1 一方的棋子攻擊對方的帥（將），並在下一著要把它吃掉，稱為「照將」，或簡稱「將」。「照將」不必聲明。
被「照將」的一方必須立即「應將」，即用自己的著法去化解被「將」的狀態。
如果被「照將」而無法「應將」，就算被「將死」。
3.2 輪到走棋的一方，無子可走，就算被「困斃」。
第4條 勝、負、和
4.1 對局時一方出現下列情況之一，為輸棋（負），對方取勝；
4.1.1 帥（將）被對方「將死」。
4.1.2 走棋後形成帥（將）直接對面。
4.1.3 被「困斃」。
4.1.4 在規定的時限內未走滿規定的著數。
4. 1.5 超過了比賽規定的遲到判負時限。
4. 1.6 走棋違反行棋規定。
4.1.7 走棋違反禁例，應變著而不變。
4.1.8 在同一棋局中，三次「犯規」。
4.1.9 自己宣布認輸。
4.1.10 在對局中拒絕遵守本規則或嚴重違反紀律。
4.2 出現下列情況之一，為和棋：
4.2.1 雙方均無可能取勝的簡單局勢。
4.2.2 一方提議作和，另一方表示同意。
4.2.3 雙方走棋出現循環反復三次，符合「棋例」中「不變作和」的有關規定。
4.2.4 符合自然限著的回合規定，即在連續60個回合中（也可根據比賽等級酌減），雙方都沒有吃過一個棋子。

國際象棋：
國際象棋由黑白兩棋組成，執白先行，國際象棋的對局目的是把對方的王將死。
比賽規定：
一方的王受到對方棋子攻擊時，成為王被照將，攻擊方稱為"將軍"，此時被攻擊方必須立即"應將"，如果無法避開將軍，王即被將死。除"將死"外，還有"超時判負"與"和局"。出現以下情況，算和局：
一方輪走時，提議作和，對方同意；
雙方都無法將死對方王時，判和；
一方連續不斷將軍，對方王卻無法避開將軍時，成為"長將和"；
輪到一方走棋，王沒有被將軍，但卻沒有任何棋子可以移動，成為"逼和"；
對局中同一局面出現三次，而且每次都是同一方走的，判為和局。
棋盤和棋子
國際象棋棋盤是個正方形，由橫縱各8格、顏色一深一淺交錯排列的64個小方格組成。深色格稱黑格，淺色格稱白格，棋子就放在這些格子中移動。棋子共三十二個，分為黑白兩組，各十六個，由對弈雙方各執一組，兵種是一樣的，分為六種： 王(1)、後(1)、車(2)、象(2)、馬(2)、兵(8)。
中文全稱 國王 皇後 城堡 主教 騎士 兵卒
英文全稱 King Queen Rook Bishop Knight Pawn
中文簡稱 王 後 車 象 馬 兵
英文簡稱 K Q R B N P
在正式比賽中，國際象棋棋子採用立體棋子，非正式比賽中可以採用平面圖案的棋子。
布子規則：

對於初學者，擺棋時記住：王對王，後對後；白後站白格，黑後站黑格。黑王站白格，白王站黑格。
注意：比賽時為了便於記憶和記錄，布置棋盤時總是讓自己的右下角是白色格。
走子規則：
· 王：橫、直、斜都可以走，但每次限走一步。
(1)除易位時外,王可走到未被對方棋子攻擊的任何相鄰格子.
(2)易位是由王已方任何一個車一起進行仍被視作王的一著的走法,其進行方式如下:王從原始位置向任何一位的方向橫移兩格,然後那人橫越過王而置於王剛經過的格子.
(3)如果一方先觸摸車一起然後再觸摸王,那麼他不能用那個車進行易位,這種情況須按以下A和B條處理
A:除上述上,如果行棋方有意識地觸摸了同一方的一個或更多的棋子,他觸動或吃掉所觸措的第一個可以走動或可以被吃的棋子;或者一個已方的棋子和 個對方的棋子,他用前者吃掉後者;如果這種吃法不合規則,如果無法確定先觸摸哪一個棋子,則以已方棋子作為已被觸摸的棋子.
B:如果所觸摸的已方棋子均沒有合乎規則的著法(或者對所觸摸的對方棋子均沒有合乎規則的吃法),行棋方有權走任何合乎規則的著法.
(4)如果一方在准備易位時觸摸了王,或者同時觸摸了王和車,然後發現易位不合規則,他可以選擇走王或者向另一翼易位,前提是向那一翼易位是合乎規則的,如果王沒有合乎規則的走法,該方有權造反走任何規則的著法.
(5)不符合規則的易位: 王已經移動過,或者 用來易位的車已經移動過.
(6)下列情況暫不能易位: 王的原始格子或者將要越過的格子或者將要佔據的格子正受到對方棋子的攻擊,或者王和用來易位的車之間尚有別的棋子
· 後：橫、直、斜都可以走，步數不受限制，但不能越子。它是國際象棋中威力最大的子。
· 車：橫、豎均可以走，步數不受限制，不能斜走。一般情況下不能越子。
· 象：只能斜走。格數不限，不能越子。每方有兩象，一個占白格，一個占黑格。
· 馬：每步棋先橫走或直走一格，然後再斜走一格（每次斜走六個正方格子），可以越子，沒有"中國象棋"中"蹩馬腿"的限制。
· 兵：只能向前直走，每著只能走一格。但走第一步時，可以最多直進兩格。兵的吃子方法與行棋方向不一樣，它是直進斜吃，即如果兵的斜進一格內有對方棋子，就可以吃掉它而占據該格。
特殊著法：
除了上面所有棋子的一般著法外，國際象棋中存在下面三種特殊著法：
· 吃過路兵：如果對方的兵第一次行棋且直進兩格，剛好形成本方有兵與其橫向緊貼並列，則本方的兵可以立即斜進，把對方的兵吃掉。這個動作必須立刻進行，緩著後無效。 記錄時記為 「en passant」 或 「en pt」， 法語中表示 「路過」。
·兵的升變：任何一個兵直進達到對方底線時，即可升變為除"王"和"兵"以外的任何一種棋子，不能不升變。一般情況下升變成為「後」因為「後」威力最大；在特殊情況下也可升變為「車」、「馬」、「象」 。
·王車易位：每局棋中，雙方各有一次機會，讓王朝車的方向移動兩格，然後車越過王，放在與王緊鄰的一格上。王車易位根據左右分為"長易位"和"短易位"。
在下面四種情況下，王車易位不允許：
王或車已經移動過；
王和車之間有其他棋子阻隔；
王正被對方"將軍"；
王經過或達到的位置受對方棋子的攻擊。
勝、負、和：
· 國際象棋的對局目的是把對方的王將死。比賽規定：一方的王受到對方棋子攻擊時，成為王被照將，攻擊方稱為「將軍」，此時被攻擊方必須立即「應將」，如果無法避開將軍，王即被將死。除「將死」外，還有「超時判負」與「和局」。出現以下情況，算和局：
·一方輪走時，提議作和，對方同意；
·雙方都無法將死對方王時，判和；
· 一方連續不斷將軍，對方王卻無法避開將軍時，成為「長將和」；
·輪到一方走棋，王沒有被將軍，但卻無路可走，成為「逼和」；
· 對局中同一局面出現三次，而且每次都是同一方走的，並且沒有任何可走棋步的差別，判為和局。
·雙方在連續50回合內都沒有吃掉對方任何一子的，判為和局。
（說明：「沒有任何可走棋步的差別」主要指過路兵和易位，我記得見過一個NB的排局有一方就是在3次重復但對方車、王有移動後贏的～～～）

④ 一個演算法問題

貪心法：選擇下一個馬的點的規則是：
所有能到達的點中，其它格子能踩到的最少的點。

這樣貪心就可以。

這是一種方法，至於有解或無解的討論……偶給忘了。。你搜一下吧。是一個很簡單的條件。（印象中是基於奇偶的）

另外一種方法就是分治法，把一個格子遞歸地分成更小的格子，生成路徑後相連。

貪心的比較簡單，如果沒有記錯，那書也沒寫錯，答案就是上面的那句話。

⑤ 中國象棋跳馬路線設計程序

是不是這題．
騎士游歷
【題目描述】
設有一個n*m的棋盤(2<=n<=50,2<=m<=50),如下圖,在棋盤上任一點有一個中國象棋馬,
馬走的規則為:
1.馬走日字 2.馬只能向右走
任務:當N,M 給出之後,同時給出馬起始的位置和終點的位置,試找出從起點到終點的所有路徑的數目.
例如:(N=10,M=10),(1,5)(起點),(3,5)(終點)
輸出:2(即由(1,5)到(3,5)共有2條路徑)
輸入格式:n,m,x1,y1,x2,y2(分別表示n,m,起點坐標,終點坐標)
輸出格式:路徑數目(若不存在從起點到終點的路徑,輸出0)
【樣例輸入1】
10 10 1 5 3 5
【樣例輸出1】
2

程序：
const max=10;
dx:array[1..4] of longint=(1,2,1,2);
dy:array[1..4] of longint=(2,1,-2,-1);
var n,m,x1,x2,y1,y2,i,j,sum:longint;
board:array[-1..max+2,-1..max+2] of longint;
dir:array[0..max*max] of longint;
procere print;
begin
if sum>0 then writeln(sum) else writeln(0);
end;
procere search(dep,x,y:longint);
var i:longint;
begin
if (x=x2) and (y=y2) then inc(sum) else
for i:=1 to 4 do
if (x+dx[i]<=x2) and (y+dy[i]>=1) and (y+dy[i]<=m)
then
begin
search(dep+1,x+dx[i],y+dy[i]);
end;
end;
begin
readln(n,m,x1,y1,x2,y2);sum:=0;
search(1,x1,y1);print;
end.