马踏棋盘游戏攻略

1、数据结构－－马踏棋盘问题

采用栈的结构(系统自带，递归就是百)，使用深度优先搜索的方法来处理。度
假设它现在正处在第（x,y）。

Procedure DFS(x,y)
Begin
for (x',y')∈{从(x,y)出发每一个只用走知一步就可以到道达的点} do
if not visited(x,y) then
begin
visited(x,y)<--TRUE
-1
if =1 then print
else DFS(x',y')
Visited(x,y)<--False
+1
end

值得一提的是：马每走一步，它所在的格子的颜色都专会发生变化，一些棋盘一只马属是可以遍历的，有的则不能。

2、急求数据结构（C语言版）马踏棋盘问题解决方案

#include<stdio.h>
#include<conio.h>

#define N 5
void main(){
int x,y;
void horse(int i,int j);
printf("Please input start position:");
scanf("%d%d",&x,&y);
horse(x-1,y-1);
}
void horse(int i,int j){
int a[N][N]={0},start=0,
h[]={1,2,2,1,-1,-2,-2,-1},
v[]={2,1,-1,-2,2,1,-1,-2},
save[N*N]={0},posnum=0,ti,tj,count=0;
int jump(int i,int j,int a[N][N]);
void outplan(int a[N][N]);
a[i][j]=posnum+1;
while(posnum>=0){
ti=i;tj=j;
for(start=save[posnum];start<8;++start){
ti+=h[start];tj+=v[start];
if(jump(ti,tj,a))
break;
ti-=h[start];tj-=v[start];
}
if(start<8){
save[posnum]=start;
a[ti][tj]=++posnum+1;
i=ti;j=tj;save[posnum]=0;
if(posnum==N*N-1){
//outplan(a);
count++;
}
}
else{
a[i][j]=0;
posnum--;
i-=h[save[posnum]];j-=v[save[posnum]];
save[posnum]++;
}
}
printf("%5d",count);
}
int jump(int i,int j,int a[N][N]){
if(i<N&&i>=0&&j<N&&j>=0&&a[i][j]==0)
return 1;
return 0;
}
void outplan(int a[N][N]){
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++)
printf("%3d",a[i][j]);
printf("\n");
}
printf("\n");
getchar();
}

3、求马踏棋盘C++算法程序

这个用贪心算法是最好的。 #include <iostream> using namespace std; #define X 8 #define Y 8 #define N 8 struct child { int x; int y; int wayout;//子节点访问次数 } node[N]; int chess[X][Y]; int addx[N]={-2,-1,1,2,2,1,-1,-2}; int addy[N]={1,2,2,1,-1,-2,-2,-1}; int way(int x,int y,int m,int n)//计算子节点出口多少 { int i; int tx; int ty; int count=-1; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]= =0)&&(chess[x][y]==0)&&((tx!=m)||(ty!=n)))//进行子节点出口的判定 { count++; } } return count; } int finalway(int x,int y)//完成最后节点的确定 { chess[x][y]=X*Y-1; int tx; int ty; int i; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]==0)& &((tx!=x)||(ty!=y)))//进行最后节点出口的判定 { chess[tx][ty]=X*Y; return 1; } } return 0; } void sort(child *point) { int i,j; struct child swap; for(i=0;i<N;i++)//采用冒泡排序 { for(j=0;j<N-1;j++) { if(point[j].wayout>point[j+1].wayout) { swap=point[j]; point[j]=point[j+1]; point[j+1]=swap; } } } } int TravelChessBoard(int x,int y,int tag) { int xx=x; int yy=y; int i; if(tag!=X*Y) { for(i=0;i<N;i++) { node[i].x=xx+addx[i]; node[i].y=yy+addy[i]; node[i].wayout=way(node[i].x,node[i].y,xx,yy); } sort(node); for(i=0;(node[i].wayout<0)&&(i<=N);i++);//去掉访问过的节点和没有出口的节点 if(i==N) return 0; for(;i<N;i++) { xx=node[i].x; yy=node[i].y; chess[xx][yy]=tag; if(TravelChessBoard(xx,yy,tag+1)==1) return 1; else chess[xx][yy]=0; } } else { if(finalway(xx,yy)) return 1; else { return 0; } } return 0; } int main() { int i,j; for(i=0;i<X;i++) { for(j=0;j<Y;j++) chess[i][j] = 0; } TravelChessBoard(2,0,1); for(i=0;i<X;i++) { for(j=0;j<Y;j++) { cout<<chess[i][j]<<'\t'; } cout<<endl; } return 1; }

4、求马踏棋盘的源代码

此程序为百度知道里面一个兄弟回答过的 十分经典

#include <stdio.h>
main()
{
int a[9][9],object[9][9],step[9][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},
{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};
int i,j,k,x,y,z,m,n,min;
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
a[i][j]=0; /* clear data in array */
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
for(k=1;k<=8;k++)
{
x=i;y=j;
x=x+step[k][1];
y=y+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
a[i][j]++ ; /* initilize array */
} /* start col and row;*/
printf("Please inpute start position x,y\n");
scanf("%d,%d",&m,&n);
for(z=1;z<=64;z++)
{
min =10;
object[m][n]=z;
a[m][n]=0;
for(k=1;k<=8;k++)
{
x=m+step[k][1];
y=n+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
if(a[x][y]!=0)
{
--a[x][y];
if(a[x][y]<min)
{
min=a[x][y];
i=x;
j=y;
}
}
}
m=i;n=j;
}
for(i=1;i<=8;i++)
{
for(j=1;j<=8;j++)
printf("%6d",object[i][j]);
printf("\n");
}
getch();
}

5、回溯算法马踏棋盘问题

//我并没有仔细研究这个算法，生硬Debug了一下，发现  a = x + Move[i][0];
  b = y + Move[i][1];//这两行在跳36步以后，导致H[a][b]越界，a和b都有40多。结合你贴的图第19步（28和8中间）被清零了，这是递归没有正确回溯造成的。
//基本上，全局变量能不用尽量不用，代码会很混乱，莫明其妙的问题多多。
//改巴改巴之后可以输出了，头几组结果好像还满正确。总的来说这个算法效率有点低，我对有生之年能看到全部输出不抱希望。

#include<stdio.h>
#include<stdlib.h>

int Move[8][2] = { 2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1 };
int H[8 + 4][8 + 4] = { 0 };
int cnt;

void Print()
{ 
    int i, j;
    for (i = 2; i < 10; i++) 
    {  
        for (j = 2; j < 10; j++)  
        {   
            printf("%4d", H[i][j]);  
        }  
        printf(" "); 
    } 
    printf(" ");
}

void hourse(int x, int y)
{ 
    int i, j, a, b, aa = x, bb = y;  // aa,bb用于保存最后的位置，回溯的起点
    for (i = 0; i < 8; i++) 
    {  
        a = x + Move[i][0];  
        b = y + Move[i][1];  
        if (H[a][b] == 0)  
        {   
            aa = a; bb = b;   
            H[a][b] = ++cnt;   
            if (cnt == 64)   
            {    
                Print();    
                //exit(0); // 基于这个算法的效率，为了把有限的生命投入到更有意义的事情，建议启用这行^^    
                H[a][b] = 0; //回溯    
                cnt--; //回溯    
                return; //回溯   
            }   
            else   
            {    
                hourse(a, b);    
                H[aa][bb] = 0;//回溯    
                cnt--;//回溯  
            }  
        } 
    }
}

int main(void)
{ 
    int i, j; 
    for (i = 0; i < 12; i++) 
    {  
        for (j = 0; j < 12; j++)  
        {   
            if (i <= 1 || j >= 10 || j <= 1 || i >= 10) 
                H[i][j] = -1;  
        } 
    } 
    for (i = 2; i < 10; i++) 
    { 
        for (j = 2; j < 10; j++)  
        {   
            cnt = 0;   
            H[i][j] = ++cnt;   
            hourse(i, j);   
            H[i][j] = 0; // 上一个起点置0，horse()只能回溯到第二步，其实我等了很久，并没有等到这行运行  
        } 
    } 
    return 0;
}

6、马踏棋盘的需求分析

将马随机放在国际象棋的Board[0～抄7][0～7]的某个方格中，马按走棋规则进行移动。，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出zhidao之。

7、算法马踏棋盘的问题

虽然我不知道你看的是什么算法，但是这问题应该是用的深度优先搜索算法。在走到死路后就需要回溯，回溯的时候肯定是要进行取消标记的操作的。

8、解释这段马踏棋盘 每步注释

LZ贴出来的代码已经把关键的点交代清楚了啊。额，好吧。再注释详细点。
#include<stdio.h>
int HTry1[8]={-2,-1,1,2,2,1,-1,-2,};
int HTry2[8]={1,2,2,1,-1,-2,-2,-1,};
int board[8][8]={{0}}; // 棋盘是 8*8的，初始化成0
int nexti[8],nextj[8],npos,s_row,s_col,step,outwrite=1;

/*（i，j）的马可以走到的新位置是在棋盘范围内的（i+HTry1[h]，j+HTry2[h]），其中h=0,1,…7。*/
int newposition(int i,int j,int a[8],int b[8])
{
// newposition的思路还是挺简单的，马每走一步的新位置最多只有8种情况而且是可预知的，
// 将这些位置预先储存到数组HTry1,HTry2中，两个数组分别代表横纵向的偏移格数。
// 实际可走的步数要除掉超出棋盘范围的和已经走过了不能重复走的。
int flag=0,h,i1,j1; // flag 记录实际下一步可选数目
for(h=0;h<8;h++)
{
i1=i+HTry1[h]; // (i, j) 加上偏移就是新位置(i1, j1)了
j1=j+HTry2[h];
if(i1>7 || i1<0 || j1>7 || j1<0) //（i1，j1）的位置不超出棋盘范围
continue;
else if(board[i1][j1]!=0) //新位置的值不为零
continue;
else // OK，是可选的了
{
a[flag]=HTry1[h]; // 记录下这个备选走法
b[flag]=HTry2[h];
++flag; // 可选数目增1
}
}
return(flag); // 返回可选数目，具体的可选走法内容由参数 a， b带回。
}

/*函数movenext在有多出口时，选择适当出口推进一步 */
int movenext(int *i,int *j,int a[],int b[])
{
// movenext是整个算法中最关键的，也是这里面写得最晦涩难理解的部分。要在多个可走的位置// 中选择一个试探，从代码来看，是采用了贪心策略，即每次都选最好的一步来走。

int temp,flag=8,a1[8],b1[8], // 各个变量的具体看代码中的夹注
nexti_like[8],nextj_like[8],
s_row_like,s_col_like,h,t;
for(h=0;h<npos;h++) // h用来将npos个可走位置选择遍历，逐个对比
{
// 每种h选择用newposition看下下步有多少种可走选择，记为temp
temp=newposition(*i+nexti[h],*j+nextj[h],a1,b1);
if(temp<flag) // 如果h选择的下下步选择数temp比目前最优情况flag还要少的话
// 这里的if条件有问题，假设刚好第一步是在棋盘中央，则对每个h选择，temp应该
// 全是8，则if条件对全部的h都不成立，结果会出错。将flag初始化成9(大于8)以上
// 可解决。
{
// 选h选择为新的当前最优选择
s_row_like=*i+nexti[h]; // 记录h选择的下一步位置
s_col_like=*j+nextj[h]; // 记录到(s_row_like,s_col_like)
flag=temp; // 记录h选择的下下步可走数，记为flag
for(t=0;t<flag;t++)
{
nexti_like[t]=a1[t]; // 记录newposition计算出来的
nextj_like[t]=b1[t]; // 下下步走法选择的具体内容
}
}
}
// 循环结束，最优结论已经得出了，选最优的一步走了
*i=s_row_like; // 将对应的下一步位置作为新的位置记到 (*i, *j)，
*j=s_col_like; // 注意这里i，j是用了指针了的，所以其结果是会传回去的，
// 要对应着看 main 中调用 movenext 的语句才清楚。
// 至于棋盘上的位置标记要等函数返回后才做。别扭！
for(h=0;h<flag;h++)
{
a[h]=nexti_like[h]; // 对应的下下步选择现在就是下一步的选择了
b[h]=nextj_like[h]; // 更新到参数 a, b 中带回。
// 从这里看，其他未选中的走法被直接弃掉没有保存，
// 所以也就无法回溯了。
}
return flag; // 返回是新的下一步的可选择数
}

void main()
{
int i,j;
printf(" 输入起始位置(row,col):");
scanf("%d,%d",&s_row,&s_col);/*输入起始位置*/
board[s_row][s_col]=1; // 将起始位置标记为1，即第1步，0则表示对应位置还没走过
npos=newposition(s_row,s_col,nexti,nextj); // 看下一步有哪几个位置可走
for(step=2;step<=64;step++) // 如果这个循环完成，说明成功遍历了棋盘 64 个位置
{
if(npos==0) // 下一步有0个位置可走，失败了
{
outwrite=0;
break;
}
else if(npos==1) // 下一步只有1个位置可走。走吧，不用多想了。
{
s_row+=nexti[0]; //nexti和nextj记录了下一步位置的纵横偏移
s_col+=nextj[0];
board[s_row][s_col]=step; // 对应位置标记上第step步
npos=newposition(s_row,s_col,nexti,nextj); //接着看下下步，循环
}
else
{
// 有多种走法，通过movenext函数来选择一步，并且看下下步，循环
npos=movenext(&s_row,&s_col,nexti,nextj);
board[s_row][s_col]=step; // 对应位置标记上第step步
}
}
if(outwrite==0) //是循环中途失败时跳出的吗？
printf("\n 没有解决方式\n");
else
{ // 不是循环中途跳出的，说明循环完成了，找到一个成功遍历的解法了。
printf("\n 解决方式之一 :\n");
// 把整个棋盘打印出来，对应位置的数表示走的步骤。
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
printf("%4d",board[i][j]);
printf("\n");
}
}
}

9、用回溯法求马踏棋盘问题是不是效率很低

虽然我不知道你看的是什么算法，但是这问题应该是用的深度优先搜索算法。在走到死路后就需要回溯，回溯的时候肯定是要进行取消标记的操作的。
这个用贪心算法是最好的。 #include <iostream> using namespace std; #define X 8 #define Y 8 #define N 8 struct child { int x; int y; int wayout;//子节点访问次数 } node[N]; int chess[X][Y]; int addx[N]={-2,-1,1,2,2,1,-1,-2}; int addy[N]={1,2,2,1,-1,-2,-2,-1}; int way(int x,int y,int m,int n)//计算子节点出口多少 { int i; int tx; int ty; int count=-1; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]= =0)&&(chess[x][y]==0)&&((tx!=m)||(ty!=n)))//进行子节点出口的判定 { count++; } } return count; } int finalway(int x,int y)//完成最后节点的确定 { chess[x][y]=X*Y-1; int tx; int ty; int i; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]==0)& &((tx!=x)||(ty!=y)))//进行最后节点出口的判定 { chess[tx][ty]=X*Y; return 1; } } return 0; } void sort(child *point) { int i,j; struct child swap; for(i=0;i<N;i++)//采用冒泡排序 { for(j=0;j<N-1;j++) { if(point[j].wayout>point[j+1].wayout) { swap=point[j]; point[j]=point[j+1]; point[j+1]=swap; } } } } int TravelChessBoard(int x,int y,int tag) { int xx=x; int yy=y; int i; if(tag!=X*Y) { for(i=0;i<N;i++) { node[i].x=xx+addx[i]; node[i].y=yy+addy[i]; node[i].wayout=way(node[i].x,node[i].y,xx,yy); } sort(node); for(i=0;(node[i].wayout<0)&&(i<=N);i++);//去掉访问过的节点和没有出口的节点 if(i==N) return 0; for(;i<N;i++) { xx=node[i].x; yy=node[i].y; chess[xx][yy]=tag; if(TravelChessBoard(xx,yy,tag+1)==1) return 1; else chess[xx][yy]=0; } } else { if(finalway(xx,yy)) return 1; else { return 0; } } return 0; } int main() { int i,j; for(i=0;i<X;i++) { for(j=0;j<Y;j++) chess[i][j] = 0; } TravelChessBoard(2,0,1); for(i=0;i<X;i++) { for(j=0;j<Y;j++) { cout<<chess[i][j]<<'\t'; } cout<<endl; } return 1; }