C语言马踏棋盘

1. 求数据结构课程设计 马踏棋盘 c语言

没看见你说的是非递归的。

其实我也不懂，碰巧知道答案，在51CTO上下的。 不能插图。
9.3 马踏棋盘（1）
【题目要求】
国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。编写一个C程序，实现马踏棋盘操作，要求用1～64这64个数字标注马移动的路径，也就是按照求出的行走路线，将数字1，2，……64依次填入棋盘的方格中，并输出。
国际象棋中，"马"的移动规则如图9-4所示。

图9-4 "马"的移动规则
如图9-4所示，图中实心的圆圈代表"马"的位置，它下一步可移动到图中空心圆圈标注的8个位置上，该规则叫做"马走日"。但是如果"马"位于棋盘的边界附近，它下一步可移动到的位置就不一定有8个了，因为要保证"马"每一步都走在棋盘中。
【题目分析】
马踏棋盘的问题其实就是要将1，2，…，64填入到一个8*8的矩阵中，要求相邻的两个数按照"马"的移动规则放置在矩阵中。例如数字a放置在矩阵的(i,j)位置上，数字a+1只能放置在矩阵的(i-2,j+1)，(i-1,j+2)，(i+1,j+2)，(i+2,j+1)，(i+2,j-1)，(i+1,j-2)，(i-1,j-2)，(i-2,j-1)之中的一个位置上。将矩阵填满并输出。这样在矩阵中从1，2…遍历到64，就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵，在该矩阵中填有1，2…64这64个数字，相邻数字之间遵照"马走日"的规则。
解决马踏棋盘问题的一种比较容易理解的方法是应用递归的深度优先搜索的思想。因为"马"每走一步都是盲目的，它并不能判断当前的走步一定正确，而只能保证当前这步是可走的。"马"走的每一步棋都是从它当前位置出发，向下一步的8个位置中的1个行走（在它下一步有8个位置可走的情况下）。因此"马"当前所走的路径并不一定正确，因为它可能还有剩下的可选路径没有尝试，如图9-5所示。

图9-5 "马"的可选路径
如图9-5所示，假设最开始"马"位于棋盘的(0,0)的位置，接下来"马"有两处位置可走，即(1,2)和(2,1)。这时"马"是无法确定走2的位置最终是正确的，还是走3的位置最终是正确的。因此"马"只能任意先从一个路径走下去（例如从2的位置）。如果这条路是正确的，那当然是幸运的，如果不正确，则"马"要退回到第一步，继续从3的位置走下去。以后"马"走的每一步行走都遵循这个规则。这个过程就是一种深度搜索的过程，同时也是一种具有重复性操作的递归过程。可以用一棵"探索树"来描述该深度优先搜索过程，如图9-6所示。

图9-6 深度优先搜索过程
"马"的行走过程实际上就是一个深度探索的过程。如图9-6所示，"探索树"的根结点为"马"在棋盘中的初始位置（这里用4*4的棋盘示意）。接下来"马"有两种行走方式，于是根结点派生出两个分支。而再往下一步行走，根结点的两个孩子又能够分别派生出其他不同的"行走路线"分支，如此派生下去，就得到了"马"的所有可能的走步状态。可以想见，该探索树的叶子结点只可能有两种状态：一是该结点不能再派生出其他的"走步"分支了，也就是"马"走不通了；二是棋盘中的每个方格都被走到，即"马"踏遍棋盘。于是从该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过程。
如何才能通过搜索这棵探索树找到这条马踏棋盘的行走路径呢？可以采用深度优先搜索的方法以先序的方式访问树中的各个结点，直到访问到叶结点。如果叶结点是第二种情况的叶结点，则搜索过程可以结束，因为找到了马踏棋盘的行走路径；如果叶结点为第一种情况的叶结点，即走不通了，则需要返回到上一层的结点，顺着该结点的下一条分支继续进行深度优先搜索下去。
因此在设计"马踏棋盘"的算法时可以借鉴前面讲过的图的深度优先遍历算法和二叉树的先序遍历算法。但是在这里并不需要真正地构建这样一棵探索树，我们只需要借用探索树的思想。在实际的操作过程中，所谓的探索树实际就是深度优先搜索的探索路径，每个结点实际就是当前的棋盘状态，而所谓的叶结点要么就是在当前棋盘状态下，"马"无法再进行下一步行走；要么就是马踏棋盘成功。该算法描述可如下：
int TravelChess Board (int x,int y,int tag)
{
chess[x][y] = tag;
if(tag == 64) { return 1;}
找到"马"的下一个行走坐标（x1,y1），如果找到返回flag=1,否则返回flag=0；
while(flag ){
if(TravelChessBoard (x1,y1,tag+1))return 1; /*递归调用TravelChess ， 从x1,y1向下搜索；如果从 x1,y1往下马踏棋盘成功，返回1*/
else
继续找到"马"的下一个行走坐标（x1,y1），如果找到返回flag=1,否则返回flag=0；
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
9.3 马踏棋盘（2）
http://book.51cto.com 2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)
摘要：《妙趣横生的算法（C语言实现）》第9章综合题，，本章将列举一些经典的综合题编程实例。这些题目生动有趣，同时具有一定的难度，因此作者尽量做到讲解深入浅出，把问题讲透彻，讲清楚。同时希望读者能从中得到启发，启迪思维，提高自身的编程水平。本节为大家介绍马踏棋盘。
标签：妙趣横生 C语言实现 妙趣横生的算法（C语言实现）

Oracle帮您准确洞察各个物流环节
9.3 马踏棋盘（2）
该算法中通过函数TravelChess()递归地搜索"马"的每一种走法。其中参数x，y指定 "马" 当前走到棋盘中的位置，tag是标记变量，每走一个棋盘方格，tag自动增1，它标识着马踏棋盘的行走路线。
算法首先将当前"马"处在棋盘中的位置上添加标记tag，然后判断tag是否等于64，如果等于64，说明这是马踏棋盘的最后一步，因此搜索成功，程序应当结束，返回1。否则，找到"马"下一步可以走到的位置(x1,y1)，如果找到这个位置坐标，flag置1，否则flag置0。
下面在flag为1的条件下（即找到x1,y1），递归地调用函数TravelChess()。也就是从x1,y1指定的棋盘中的位置继续向下深度搜索。如果从x1,y1向下搜索成功，即程序一直执行下去，直到tag等于64返回1，那就说明"马"已经踏遍棋盘（马踏棋盘的过程是：先走到棋盘的(x,y）位置，再从(x1,y1)向下深度搜索，走遍全棋盘），于是搜索结束，返回1；否则继续找到"马"的下一个可以行走的坐标(x1,y1)，如果找到这个位置坐标，flag置1，并从(x1,y1)向下重复上述的递归搜索，否则flag置0，本次递归结束。
如果找遍当前位置(x,y)的下一个坐标(x1,y1)（一般情况是8种），但是从(x1,y1)向下继续深度优先搜索都不能成功地"马踏棋盘"（此时flag等于0），则表明当前所处的状态并不处于马踏棋盘的"行走路径"上，也就是说"马"本不应该走到(x,y)的位置上，因此将chess[x][y]置0，表明棋盘中该位置未被走过（擦掉足迹），同时返回0，程序退到上一层的探索状态。
这里应当知道，所谓当前位置(x,y)的下一个坐标(x1,y1)是指"马"下一步可以走到的地方，用坐标(x1,y1)返回。在探索树中它处在(x,y)所在的结点的子结点中，如图9-7所示。

图9-7 (x,y)的下一个坐标(x1,y1)
当前位置(x,y)的下一个坐标(x1,y1)的可选个数由当前棋盘的局面决定。一般情况下是有8种可走的位置（如图9-7所示），但是如果"马"位于棋盘的边缘（如图9-7所示的探索树的根结点）或者8个可选位置中有的已被"马"前面的足迹所占据，在这两种情况下(x1,y1)的可选个数就不是8个了。
上述搜索算法相当于先序遍历探索树，只不过它不一定是将探索树完整地遍历，而是当tag等于64时，也就是棋盘被全部"踏遍"时就停止继续搜索了。
下面给出完整的程序清单供读者参考。
程序清单9-3
/*--------------------------------- 9-3.c --------------------------*/
#include "stdio.h"
#define X 8
#define Y 8
int chess[X][Y];

int nextxy(int *x,int *y,int count) /*找到基于x、y位置的下一个可走的位置*/
{
switch(count)
{
case 0: if(*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0) {*x =*x+2;*y = *y-1;return 1; } break;
case 1: if(*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0) {*x = *x+2; *y = *y+1 ;
return 1;}break;
case 2: if(*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0) {*x = *x+1; *y = *y-2; return 1;} break;
case 3: if(*x+1<=X-1 && *y+2<=Y-1 &&chess[*x+1][*y+2]==0) {*x = *x+1; *y = *y+2;
return 1;}break;
case 4: if(*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0) {*x = *x-2; *y = *y-1; return 1;} break;
case 5: if(*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0){*x = *x-2; *y = *y+1; return 1;} break;
case 6:if(*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0) {*x = *x-1; *y = *y-2;return 1;}break;
case 7: if(*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0) {*x = *x-1; *y = *y+2;
return 1;}break;
default: break ;
}
return 0;
}

int TravelChessBoard(int x,int y,int tag) /*深度优先搜索地"马踏棋盘"*/
{
int xx1 = x, yy1 = y, flag = 0,a,b ,count = 0 ;
chess[x][y] = tag;
if(tag == X*Y) { return 1;}
flag = nextxy(&x1,&y1,count);
while(flag == 0 && count <7){
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
while(flag ){
if(TravelChessBoard(x1,y1,tag+1))return 1;
xx1 = x;yy1 = y;
countcount = count +1;
flag = nextxy(&x1,&y1,count); /*寻找下一个(x,y)*/
while(flag == 0 && count <7){ /*循环地寻找下一个(x,y)*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
main()
{
int i,j;
for(i=0;i<X;i++)
for(j=0;j<Y;j++)
chess[i][j] = 0;
if(TravelChessBoard(2,0,1)) {
for(i=0;i<X;i++) {
for(j=0;j<Y;j++)
printf("%d ",chess[i][j]);
printf("\n");
}
printf("The horse has travelled the chess borad\n");
}
else
printf("The horse cannot travel the chess board\n");
getche();
}
9.3 马踏棋盘（3）
http://book.51cto.com 2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)
摘要：《妙趣横生的算法（C语言实现）》第9章综合题，，本章将列举一些经典的综合题编程实例。这些题目生动有趣，同时具有一定的难度，因此作者尽量做到讲解深入浅出，把问题讲透彻，讲清楚。同时希望读者能从中得到启发，启迪思维，提高自身的编程水平。本节为大家介绍int nextxy(int *x,int *y,int count)。
标签：妙趣横生 C语言实现 妙趣横生的算法（C语言实现）

Oracle帮您准确洞察各个物流环节
9.3 马踏棋盘（3）
【程序说明】
本程序中应用二维数组chess[8][8]作为8*8的棋盘，"马"每走到棋盘的(i,j)处，就将当前的步数tag赋值给chess[i][j]。为了方便起见，将数组chess设置为外部变量。另外定义字符常量X，Y，它规定棋盘的大小。本程序清单中将X和Y都设置为8。
函数TravelChessBoard()是上述马踏棋盘算法的具体实现。本程序中初始的(x,y)位置为(2,0)，说明"马"从chess[8][8]的chess[2][0]位置开始进行"马踏棋盘"的。在函数TravelChessBoard()中要调用函数nextxy()。
int nextxy(int *x,int *y,int count)
函数nextxy()包含3个参数：x和y为传递下来的"马"当前踏到棋盘上的位置，它是指针变量。变量count的作用是标记调用nextxy()过程的次数，根据count值的不同，返回基于(x,y)的下一个不同的坐标，以此来避免返回同一个坐标，真正实现寻找"针对当前位置(x,y)的下一个位置"的目的。函数nextxy()的作用是找到"马"当前的位置(x,y)的下一个可以行走的位置，并通过指针修改x、y的内容，将下一个位置坐标用变量x、y返回。
"寻找(x,y)的下一个位置坐标"的操作通过代码：
xx1 = x; yy1 = y; /*将坐标(x1,y1)初始化为当前访问的坐标 (x,y)，因为(x,y)不能被改动*/
flag = nextxy(&x1,&y1,count); /*寻找(x,y)下一个位置坐标(x1,y1)*/
while(flag == 0 && count <7){ /*循环地寻找(x,y)的下一个坐标*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
实现。程序最开始将(x1,y1)初始化为当前坐标(x,y)，因为"马"的当前位置坐标(x,y)不能被轻易改动。然后将&x1、&y1作为函数nextxy的参数传递，并通过参数&x1和&y1返回当前坐标(x,y)的第count个下一个坐标(x1,y1)。只有当flag为1时，才表明找到了下一个坐标，于是循环可以停止。但是如果count的值超过了7，则说明无法找到(x,y)的下一个坐标，也就说明棋走不通了。所谓当前位置(x,y)的"下一个位置"，如图9-8所示。

（点击查看大图）图9-8 (x,y)的"下一个位置"示意
图中实心的圆圈的坐标为(x,y)，它周围的8个空心的圆圈1～8，为当前坐标(x,y)的可选的"下一个"坐标(x1,y1)。每次调用nextxy()都可能得到这8个坐标其中的一个，当参数count为i时，返回圆圈i所处的坐标。这样就保证了不返回同一个坐标。
如果像本程序这样将字符常量X和Y都设置为8，那么程序就执行8*8的马踏棋盘。但是这样一来会非常费时，实践证明应用本程序运算出8*8的马踏棋盘的结果要花几分钟的时间。因此读者在调试程序时可以通过设置X和Y的值减小棋盘的规格，从而更快地得到结果。
本程序的运行结果如图9-9所示。

（点击查看大图）图9-9 程序9-3的运行结果

2. 马踏棋盘程序解释

实现马走完8×8棋盘的路线；
分步解析：
（1）
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}};设定马可走的八个方向，第二维第一个是序号（没什么用），后两个分别得X坐标，Y坐标增量；
（2）
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 */
}
初始化整个棋盘，a[i][j]表示马在（i，j）上可走的方向个数；例如a[1][1]=2,说明马如果在(1,1)只能走（2，3）和（3，2）；这步为后面做铺垫；
（3）
for(z=1;z<=64;z++)
//标记棋盘的64个可达点，起点为1号，终点为64号，object[m][n]=z；

a[m][n]=0;//每走过一个点，就置该点为0，表示不能再走，（if(a[x][y]!=0) ）；
能走的话（a[i][j])!=0)就选一个小于min的点if(a[x][y]<min) 作为下一步棋； 之所以要选一个a[i][j]最小的点牵扯到一些算法，只有这样才能保证走遍所有点并且不重复。
最后打印，不用说了吧。
大概我想说的就这些。

3. 程序设计，马踏棋盘，求指教

#include<stdio.h>
#define MAXSIZE 100
#define N 8
int board[8][8]; //定义棋盘
int Htry1[8]={1,-1,-2,2,2,1,-1,-2};
/*存储马各个出口位置相对当前位置行下标的增量数组*/
int Htry2[8]={2,-2,1,1,-1,-2,2,-1};
/*存储马各个出口位置相对当前位置列下标的增量数组*/
struct Stack{ //定义栈类型
int i; //行坐标
int j; //列坐标

}stack[MAXSIZE]; //定义一个栈数组
int top=0; //栈指针

void InitLocation(int xi,int yi); //马儿在棋盘上的起始位置坐标
int TryPath(int i,int j); //马儿每个方向进行尝试，直到试完整个棋盘
void Display(); //输出马儿行走的路径

void InitLocation(int xi,int yi)
{
int x,y; //定义棋盘的横纵坐标变量
stack[top].i=xi; //将起始位置的横坐标进栈
stack[top].j=yi; //将起始位置的纵坐标进栈

board[xi][yi]=top+1; //标记棋盘
x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标
y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标
if(TryPath(x,y)) //调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0
Display(); //输出马儿的行走路径

}

int TryPath(int i,int j)
{
int find,number,min; //定义几个临时变量
int i1,j1,h,k,s; //定义几个临时变量
int a[8],b1[8],b2[8],d[8]; //定义几个临时数组
while(top>-1) //栈不空时循环
{
for(h=0;h<8;h++) //用数组a[8]记录当前位置的下一个位置的可行路径的条数
{
number=0;
i=stack[top].i+Htry1[h];
j=stack[top].j+Htry2[h];
b1[h]=i;
b2[h]=j;
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置
{
for(k=0;k<8;k++)
{
i1=b1[h]+Htry1[k];
j1=b2[h]+Htry2[k];
if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)
//如果找到下一位置
number++; //记录条数
}
a[h]=number; //将条数存入数组a[8]中
}
}
for(h=0;h<8;h++) //根据可行路径条数小到大按下表排序放入数组d[8]中
{
min=9;
for(k=0;k<8;k++)
if(min>a[k])
{
min=a[k];
d[h]=k; //将下表存入数组d[8]中
s=k;
}
a[s]=9;
}

if(top>=63) //如果走完整个棋盘返回1
return (1);
find=0; //表示没有找到下一个位置
for(h=0;h<8;h++) //向八个方向进行探寻
{
i=stack[top].i+Htry1[d[h]];
j=stack[top].j+Htry2[d[h]];
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置
{
find=1; //表示找到下一个位置
break;
}
}
if(find==1) //如果找到下一个位置进栈
{

top++; //栈指针前移进栈
stack[top].i=i;
stack[top].j=j;

board[i][j]=top+1; //标记棋盘
}
else //否则退栈
{
board[stack[top].i][stack[top].j]=0; //清除棋盘的标记
top--; //栈指针前移退栈
}
}
return (0);
}

void Display()
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("\t%d ",board[i][j]); //输出马儿在棋盘上走过的路径
printf("\n\n");
}
printf("\n");
}

void main()
{
int i,j;
int x,y;
for(i=0;i<N;i++) //初始化棋盘
for(j=0;j<N;j++)
board[i][j]=0;
for(;;)
{
printf("Please input importpoint(1<=x<=8 and 1<=y<=8)\n");
printf("Input x = ");
scanf("%d",&x); //输入起始位置的横坐标
printf("Input y = ");
scanf("%d",&y); //输入起始位置的纵坐标
if(x>=1&&x<=8&&y>=1&&y<=8)break;
printf("Your input is worng!!!\n");
}
printf("begin with %d board:\n\n", 8*(x-1)+y);
InitLocation(x-1,y-1); //调用起始坐标函数
}

4. 帮帮忙编程:马踏棋盘(用数据结构(C语言版))

#include <stdio.h>

int f[11][11] ;
int adjm[121][121];
long fgf;
void creatadjm(void);
void e(int,int,int,int);
void travel(int,int);

int n,m;

int main()
{
int i,j,k,l;
printf("Input n:");scanf("%d",&n);
m=n*n;
creatadjm();
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
printf("\n");
}
getchar();
printf("Input i,j:");
scanf("%d %d",&i,&j);
l=(i-1)*n+j;
while ((i>0)||(j>0))
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=0;
k=0;

travel(l,k);
printf("%d\n",fgf);fgf=0;

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) printf("%4d",f[i][j]);
printf("\n");
}
getchar();
printf("Input i,j:");scanf("%d %d",&i,&j);
l=(i-1)*n+j;
}
return 0;
}

void creatadjm()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
adjm[i][j]=0;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]==0)
{
f[i][j]=1;
if((i+2<=n)&&(j+1<=n)) e(i,j,i+2,j+1);
if((i+2<=n)&&(j-1>=1)) e(i,j,i+2,j-1);
if((i-2>=1)&&(j+1<=n)) e(i,j,i-2,j+1);
if((i-2>=1)&&(j-1>=1)) e(i,j,i-2,j-1);
if((j+2<=n)&&(i+1<=n)) e(i,j,i+1,j+2);
if((j+2<=n)&&(i-1>=1)) e(i,j,i-1,j+2);
if((j-2>=1)&&(i+1<=n)) e(i,j,i+1,j-2);
if((j-2>=1)&&(i-1>=1)) e(i,j,i-1,j-2);
}
return;
}

void travel(int p,int r)
{
int i,j,q;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]>r) f[i][j]=0;
r=r+1;
i=((p-1)/n)+1;
j=((p-1)%n)+1;

f[i][j]=r;

fgf++;
//if(r==25)printf("%d\n",p);
/*
printf("i=%d,j=%d,r=%d\n",i,j,r); getchar();
*/

for(q=1;q<=m;q++)
{
i=((q-1)/n)+1;
j=((q-1)%n)+1;
if((adjm[p][q]==1)&&(f[i][j]==0)) travel(q,r);
}
return;
}

void e(int i1,int j1,int i2,int j2)
{
adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
return;
}

5. 数据结构课程设计 用栈完成马踏棋盘的C语言的代码,急!急!

#include<string.h> #include<ctype.h> #include<stdio.h> #include<math.h> #include<process.h> #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int status; /* pointtype */ typedef struct PT{ int r; int c; }PTT,*LPT; /* stacktype */ typedef struct ST{ int step; int reach[8]; struct PT seat; }ST; struct SD{ ST *base; ST *top; int size; }SD; /* QUEUE */ typedef struct QT{ int r,c,n; }QT; typedef struct QN{ QT data; struct QN *next; }QN,*QNPtr; struct QD{ QNPtr front; QNPtr rear; }QD;

6. 急求数据结构（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();
}

7. 能给我一个马踏棋盘的c语言程序吗，要能运行的。

#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define M 8//宏定义棋盘大小#define SIZE 100int board[M][M];typedef struct direct { int r,c,pathnum ;}dir ;typedef struct nodetype { int r,c,pathnum ; //在棋盘中的位置坐标r,c及结点可走方向数目 pathnum struct nodetype*next,*prior ;}node ;//用来计算当前位置可走的方向数目int pathnum(int row,int cn){ int a,b,count=0 ; a=row ; b=cn ; //当前位置可选方向可以走通，则数目加一 if(a-2>=0&&b-1>=0&&board[a-2][b-1]==0)count++; if(a-2>=0&&b+1<M&&board[a-2][b+1]==0)count++; if(a+2<M&&b-1>=0&&board[a+2][b-1]==0)count++; if(a+2<M&&b+1<M&&board[a+2][b+1]==0)count++; if(a-1>=0&&b+2<M&&board[a-1][b+2]==0)count++; if(a-1>=0&&b-2>=0&&board[a-1][b-2]==0)count++; if(a+1<M&&b+2<M&&board[a+1][b+2]==0)count++; if(a+1<M&&b-2>=0&&board[a+1][b-2]==0)count++; return count ;}//寻找路径函数void findway(int m,int n){ dir f[8],path ; int i,j,k, stepnum ; stepnum=1 ; i=m ; j=n ; while(stepnum<M*M&&i<M&&j<M&&i>=0&&j>=0) { board[i][j]=stepnum ;printf("%d,%d,%d ",i,j,board[i][j]); //用来标志可走方向数的最小值 path.pathnum=8 ; //对方向数组赋初值 for(k=0;k<8;k++) { f[k].r=-1 ; f[k].c=-1 ; } //如果第一个方向可走，则将坐标及可选方向数赋给f[0]，以下同理 if(i-2>=0&&j-1>=0) { f[0].r=i-2 ; f[0].c=j-1 ; f[0].pathnum=pathnum(f[0].r,f[0].c); } if(i-2>=0&&j+1<M) { f[1].r=i-2 ; f[1].c=j+1 ; f[1].pathnum=pathnum(f[1].r,f[1].c); } if(i+2<M&&j-1>=0) { f[2].r=i+2 ; f[2].c=j-1 ; f[2].pathnum=pathnum(f[2].r,f[2].c); } if(i+2<M&&j+1<M) { f[3].r=i+2 ; f[3].c=j+1 ; f[3].pathnum=pathnum(f[3].r,f[3].c); } if(i-1>=0&&j+2<M) { f[4].r=i-1 ; f[4].c=j+2 ; f[4].pathnum=pathnum(f[4].r,f[4].c); } if(i-1>=0&&j-2>=0) { f[5].r=i-1 ; f[5].c=j-2 ; f[5].pathnum=pathnum(f[5].r,f[5].c); } if(i+1<M&&j-2>=0) { f[6].r=i+1 ; f[6].c=j-2 ; f[6].pathnum=pathnum(f[6].r,f[6].c); } if(i+1<M&&j+2<M) { f[7].r=i+1 ; f[7].c=j+2 ; f[7].pathnum=pathnum(f[7].r,f[7].c); } //寻找当前位置的八个方向中的可走方向数最少的方向作为新的方向 for(k=0;k<8;k++) if(f[k].r>=0&&f[k].c>=0&&f[k].pathnum<=path.pathnum&&board[f[k].r][f[k].c]==0&&f[k].pathnum>0) { path.pathnum=f[k].pathnum; path.r=f[k].r ; path.c=f[k].c ; } i=path.r ; j=path.c ; stepnum++; } board[i][j]=M*M-1 ; if(i-2>=0&&j-1>=0&&board[i-2][j-1]==0) { i=i-2 ; j=j-1 ; } else if(i-2>=0&&j+1<M&&board[i-2][j+1]==0) { i=i-2 ; j=j+1 ; } else if(i-1>=0&&j+2<M&&board[i-1][j+2]==0) { i=i-1 ; j=j+2 ; } else if(i+1<M&&j+2<M&&board[i+1][j+2]==0) { i=i+1 ; j=j+2 ; } else if(j+2<M&&i+1<=M&&board[i+2][j+1]==0) { i=i+2 ; j=j+1 ; } else if(i+2<M&&j-1>=0&&board[i+2][j-1]==0) { i=i+2 ; j=j-1 ; } else if(i+1<M&&j-2>=0&&board[i+1][j-2]==0) { i=i+1 ; j=j-2 ; } else if(i-1>=0&&j-2>=0&&board[i-1][j-2]==0) { i=i-1 ; j=j-2 ; } board[i][j]=M*M ;printf("%d,%d,%d",i,j,board[i][j]);}
void main(){ int r,c,i,j ; printf("请输入马在棋盘上的首位置\n"); scanf("%d,%d",&r,&c); findway(r,c); printf("\n"); //输出棋盘上的路径 for(i=0;i<M;i++) { for(j=0;j<M;j++) printf("%3d",board[i][j]); printf("\n"); }}

8. 马踏棋盘的算法

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

9. 数据结构中马踏棋盘问题，求c程序

1。建立无向图，应该是棋盘格数的方阵，比如64×64（国际象棋）或者90×90，初始化为全零.根据马的走法，对可以直达的两格建立一条边，就是对应位置为1。
2。然后指定一个出发点（当然也可以是从所有点出发一一去试），沿着这些边到达下一格，并记录已达到的格中。
3.如果不重复完成，则成功。如果无法继续走到未到达的格，只能到已到达的格子，则失败。
4.这个走棋的过程需要一种策略来遍历各种情况。比如我们可以规定如果有最多八种可能，则马先测试走那种，这个编写成递归就非常方便。

10. 马踏棋盘的核心代码（c语言）

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -2
#define OK 1
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
int Board[8][8]={0};
int HTry1[8]={2,-1,1,-2,2,1,-1,-2};
int HTry2[8]={1,2,2,1,-1,-2,-2,-1};
typedef struct{
int i;
int j;
}PosType;
typedef struct{
int ord;
PosType seat;
int di;
}SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack *s1){
(*s1).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*s1).base) exit(OVERFLOW);
(*s1).top=(*s1).base;
(*s1).stacksize=STACK_INIT_SIZE;
return(OK);
}
SElemType Pop(SqStack *s,SElemType e){
e=*--(*s).top;
return e;
}
int Push(SqStack *s1,SElemType e){
if((*s1).top-(*s1).base>=(*s1).stacksize){
(*s1).base=(SElemType *)realloc((*s1).base,
((*s1).stacksize+STACKINCREMENT)*sizeof
(SElemType));
if(!(*s1).base) exit(OVERFLOW);
(*s1).top=(*s1).base+(*s1).stacksize;
(*s1).stacksize+=STACKINCREMENT;
}
*(*s1).top++=e;
return OK;
}
int StackEmpty(SqStack *s){
if((*s).base==(*s).top)
return(1);
else
return(0);
}
int curstep=0;
int Pass(PosType s){
if((Board[s.i][s.j]==0)&&(s.i<=7)&&(s.i>=0)&&(s.j<=7)&&(s.j>=0))
return(1);
else
return(0);
}
PosType NextPos(PosType s,int i){
s.i=s.i+HTry1[i-1];
s.j=s.j+HTry2[i-1];
return(s);
}
void horsesteps(int Board[8][8],PosType start){
int k,j;
SqStack S;
SElemType e;
PosType curpos=start;
InitStack(&S);
do{
if(Pass(curpos)){
curstep++;
Board[curpos.i][curpos.j]=curstep;
e.seat=curpos;
e.ord=curstep;
e.di=1;
Push(&S,e);
if(curstep==64)
break;
else
curpos=NextPos(curpos,1);
}//if
else{
if(!StackEmpty(&S)){
Pop(&S,e);
if(e.di==8) Board[e.seat.i][e.seat.j]=0;
while(e.di==8&&!StackEmpty(&S)){
e=Pop(&S,e);
if(e.di==8) Board[e.seat.i][e.seat.j]=0;
curstep=e.ord;
}//while
if(e.di<8){
e.di++;
Push(&S,e);
curpos=NextPos(e.seat,e.di);
}//if
}//if
}//else
}while(!StackEmpty(&S));
if(StackEmpty(&S)){
printf(马儿从这个初始位置不能踏遍棋盘 );
printf(请按任意键推出本程序 );
getchar();
exit(OVERFLOW);
}
for(j=0;j<8;j++){
printf( );
for(k=0;k<8;k++)
printf(%3d,Board[j][k]);
}// for
}//函数结束
void main(){
int k,j;
PosType t;
char a,b;
printf(请输入马儿的初始位置 );
fflush(stdin);
scanf(%c%d,%d%c,&a,&k,&j,&b);
t.i=k;
t.j=j;
printf(马儿走的路线为 );
horsesteps(Board,t);
}
小弟只能写出自己的回溯法的算法，效率很低，有时要21分钟出结果 ，但思路是对的。
【原创】我给出我写的试探法代码
#include <iostream>
using namespace std;
typedef struct _point
{
int x;
int y;
}point;
class Horse
{
public:
Horse(int n);
~Horse();
void MoveNext(int hang,int lie);
void Print();
public:
int shu;
int qipan[20+1][20+1];
point pt[400+1];
int ci;
};
Horse::Horse(int n)
{
ci=0;
shu=n;
for(int i=1;i<=shu;i++)
for(int j=1;j<=shu;j++)
qipan[i][j]=0;
}
Horse::~Horse()
{
}
void Horse::Print()
{
if(pt[0].x==shu*shu)
{
ci++;
cout<<ci<< Yes!<<endl;
for(int i=1;i<=shu;i++)
for(int j=1;j<=shu;j++)
{
cout<<qipan[i][j]<<' ';
if(j==shu)
cout<<endl;
}
}
}
void Horse::MoveNext(int hang,int lie)
{
if(hang==1&&lie==1&&qipan[hang][lie]==0)
{
pt[0].x=1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
}
if(hang-1>0&&lie-2>0&&qipan[hang-1][lie-2]==0)
{
pt[0].x++;
hang=hang-1;
lie=lie-2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie); //返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+1<=shu&&lie-2>0&&qipan[hang+1][lie-2]==0)
{
pt[0].x++;
hang=hang+1;
lie=lie-2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang-2>0&&lie-1>0&&qipan[hang-2][lie-1]==0)
{
pt[0].x++;
hang=hang-2;
lie=lie-1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+2<=shu&&lie-1>0&&qipan[hang+2][lie-1]==0)
{
pt[0].x++;
hang=hang+2;
lie=lie-1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang-2>0&&lie+1<=shu&&qipan[hang-2][lie+1]==0)
{
pt[0].x++;
hang=hang-2;
lie=lie+1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+2<=shu&&lie+1<=shu&&qipan[hang+2][lie+1]==0)
{
pt[0].x++;
hang=hang+2;
lie=lie+1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang-1>0&&lie+2<=shu&&qipan[hang-1][lie+2]==0)
{
pt[0].x++;
hang=hang-1;
lie=lie+2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+1<=shu&&lie+2<=shu&&qipan[hang+1][lie+2]==0)
{
pt[0].x++;
hang=hang+1;
lie=lie+2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回点
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
Print();
{
qipan[hang][lie]=0;
pt[0].x--;
}
}
int main()
{
printf(Input the num:);
int n;
scanf(%d,&n);
Horse h(n);
h.MoveNext(1,1);
return 0;
}
翘了一学期的数据结构，赶工补作业中，我用的是贪心算法，速度不错，秒出。。
#include<iostream>
#define M 12
#define D 8
using namespace std;
int pathnum(int x,int y);
void initdata();
int pathnum(int x,int y);
void findway(int x , int y );
int board[M][M]={0,0};
int HTry1[D]={ -2, -1, 1, 2, 2, 1, -1, -2 };
int HTry2[D]={ 1, 2, 2, 1, -1, -2, -2, -1 };
void initdata()
{
int i , j;
for ( i=0 ; i<2 ; i++ )
{
for ( j=0;j<M;j++)
{
board[i][j]=1;
board[M-i-1][j]=1;
board[j][i]=1;
board[j][M-i-1]=1;
}
}
}
int main()
{
void findway(int x , int y );
int startx,starty,i,j;
cout<<请输入初始坐标值<<endl;
initdata();
cin>>startx>>starty;
findway(startx,starty);
for(i=2;i<M-2;i++)
{
//以图形方式显示行走步数
for(j=2;j<M-2;j++)
printf(%4d,board[i][j]);
cout<<endl<<endl;
}
return 0;
}
void findway(int x , int y )
{
x=x+1;
y=y+1;
int stepnum=1;
int num[D];
int i,min,minx,miny;
board[x][y]=stepnum;
for ( stepnum=2; stepnum<=(M-4)*(M-4) ;stepnum++ )
{
min=8;
for (i=0;i<D;i++)
{
if (board[x+HTry1[i] ][ y+HTry2[i] ] ==0)
{
num[i]=pathnum( x+HTry1[i] , y+HTry2[i] );
if (num[i]<min)
{
min=num[i];
minx = x+HTry1[i];
miny = y+HTry2[i];
}
}
}
x=minx;
y=miny;
board[x][y]=stepnum;
}
}
int pathnum(int x,int y)
{
//返回当前位置可走的方向数目
int count=0 ;
for (int i=0;i<D;i++)
{
if (board[ x+HTry1[i] ][ y+HTry2[i] ]==0)
{
count++;
}
}
return count ;
}