马走日算法

① . 编写程序求解骑士巡游问题：在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.