马踏棋盘程序设计

1、.问题描述设计一个国际象棋的马踏棋盘的演示程序。基本要求将马随机放在国际象棋8*8 的棋盘 Board88的某个方格中， 马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘全部的 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线， 将数字 1，2，3 .64 一次填入一个 8*8 的方阵 输出之测试数据可自行指定一个马的初始位置（i,j） ,0<=i,j<=7.。实现提示一般说来，当马位于位置（i,j）时，可以走到下列8 个位置之一（ i-2,j+1 ） ,(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1), (i+1,j-2),(

2、i-1,j-2),(i-2,j-1)但是，如果（ i ，j ）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。 8 个可能位置可以用一维数组 Htry10 7 和 HTry20.7 来表示：Htry101234567-2-11221-1-2Htry2012345671221-1-2-2-1位于（i,j ）的马可以走到新位置是在棋盘范围内的 （i+ Htry1h,j+ Htry2h ）,其中 h=0,1, .7.一需求分析1输入的形式和输入值的范围；分开输入马的初始行坐标X 和列坐标 Y，X 和 Y 的范围都是 0,7 。2输出的形式；一共提供了 2 种输出方式：（1）以数组下标

3、形式输入，代表起始位置，i 表示行标， j 表示列标。（2）以棋盘形式输出，每一格打印马走的步数，这种方式比较直观。3程序所能达到的功能；让马从任一起点出发都能够历遍整个8×8 的棋盘。;.二概要设计1设定栈的抽象数据类型定义：ADT Stack数据对象： D=ai|ai CharSet,i=1,2.,n数据关系 :R1=<ai-1,ai>|ai-1,ai D,i=2,.,n基本操作 :(这里仅列举本题中使用的操作)InitStack(&S)操作结果 :构建一个空栈。Push(&S,e)操作结果 :在栈顶插入新的元素。Pop（&S,&e ）

4、操作结果：将栈顶元素弹出。SetTop(S,& e)操作结果：将 e 设为栈顶元素。GetTop(S, &e)操作结果：将栈顶元素取出。StackEmpty(S)判断栈是否为空ADT Stack2本程序包含 2 个模块(1).主程序模块 :Void main()初始化棋盘；while(1) 接受命令；处理命令；执行 Path(x,y);(2).栈模块实现栈抽象数据类型3探讨每次选择位置的“最佳策略”思路1）先求出每个坐标点的权值，即是该坐标下一步有几个方向可以走2）权值越小 ,则被上一点选中的可能性就越大，下一个方向八个值的选择顺序保存 MAPXYK数组中， 0<=K&l

5、t;=7 ，例如 MAPXY0保存的是下一步优先选择走的方向，MAPXY7就是最后才走的。边界的点最先走，然后再走中间。4踏遍棋盘伪码算法：While （）;.若已经走了 64 步,则打印输出结果；否则 若该点所有方向已走完 出栈 若该点所有方向未走完 若该点未走过且在棋盘内入栈，已走步数加1否则 * 下一步方向加 1三详细设计1栈类型struct SElemTypeint a;int b;int di;/ 方向编号int flag8;/ 访问过的方向数;栈的顺序存储表示typedef struct SqStackSElemType *base;SElemType *top;int stack

6、size;栈基本操作：Status InitStack(SqStack *S) /* 构造一个空栈 S */(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base)exit(OVERFLOW); /*存储分配失败*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S);. /* 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE */ if(S.top=S.base

7、)return TRUE;elsereturn FALSE;Status GetTop(SqStack S,SElemType *e) /* 若栈不空，则用 e 返回 S 的栈顶元素， 并返回 OK ；否则返回 ERROR/ if(S.top>S.base)*e=*(S.top-1); return OK;elsereturn ERROR;Status SetTop(SqStack S,SElemType *e)if(S.top>S.base)*(S.top-1)=*e;return OK;elsereturn ERROR;Status Push(SqStack *S,SElemT

8、ype e) /* 插入元素 e 为新的栈顶元素 */if(*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */ (*S).base=(SElemType*)realloc(*S).base,(*S).stacksize+STACKINCRE MENT)*sizeof(SElemType);if(!(*S).base)exit(OVERFLOW); /*存储分配失败*/(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return O

9、K;Status Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK ；否则返回 ERROR */if(*S).top=(*S).base);.return ERROR;*e=*-(*S).top;return OK;2求最佳策略算法求各点权值 :可走的方向数越少 ,则被上一点选中的可能性越大int num(int x1,int y1)int count1=0;for(int j=0;j<8;j+)int x2=x1+Htry1j;int y2=y1+Htry2j;if(Pass(x2,y2)count1+;r

10、eturn count1;主要程序：#include <stdio.h>#include<malloc.h>#include<string.h>#define STACK_INIT_SIZE 10#define STACKINCREMENT 2int board88=0; /棋盘初始化int Htry18=-2,-1,1,2,2,1,-1,-2;int Htry28=1,2,2,1,-1,-2,-2,-1;struct SElemTypeint a;int b;int di;int flag8;typedef struct SqStackSElemType

11、*base;SElemType *top;int stacksize;void InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);.if(!S.base) exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack &S)if(S.base=S.top)return 1;elsereturn 0;void Push(SqStack &S,SElemType &e)if

12、(S.top-S.base>=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;int Pop(SqStack &S,SElemType &e)if(S.top=S.base) return 0;e=*-S.top;return 1;int Pass(int i,int j

13、)if(i>=0&&i<=7&&j>=0&&j<=7&&boardij=0)return 1;elsereturn 0;/ 判断该方向是否能够通过int num(int x1,int y1)int count1=0;for(int j=0;j<8;j+)int x2=x1+Htry1j;int y2=y1+Htry2j;if(Pass(x2,y2)count1+;.return count1;SElemType NextPos(SElemType e)int x1,y1;int i,j;int x=e

14、.a;int y=e.b;int p=0;int di_num=0;int di_min=8;for(i=0;i<8;i+)if(e.flagi!=0) continue;/判断该方向是否走过x1=x+Htry1i;y1=y+Htry2i;if(Pass(x1,y1)di_num=num(x1,y1);if(di_num<di_min)/ 判断该方向是否有最少的可通过方向e.a=x1;e.b=y1;di_min=di_num;p=i;e.flagp=1;return e;int search(int x,int y,SqStack &S)SElemType e,curpos

15、;int count=0;memset(curpos.flag,0,sizeof(curpos.flag);/ 将结构体中的flag 赋 0curpos.a=x;curpos.b=y;while(count<64)x=curpos.a;y=curpos.b;if(Pass(x,y) 若找到下一个点，则将该点压入栈中count+;./printf("count=%d n", count);boardxy=count;e.di=0;e=curpos;Push(S,e);curpos=NextPos(e);memset(curpos.flag,0,sizeof(curpos

16、.flag);elseif(!StackEmpty(S)Pop(S,e);elsereturn 0;count-;while(e.di=7&&!StackEmpty(S)若 8 个方向都不能通过，则从栈中弹出上一个点boarde.ae.b=0;Pop(S,e);count-;if(e.di<7) 若该点的还有方向没有访问过，则换下一个方向e.di+;Push(S,e);count+;curpos=NextPos(e);memset(curpos.flag,0,sizeof(curpos.flag);return 1;void display()/ 将马的轨迹输出int i,j;for(i=0;i<8;i+)for(j=0;j<8;j+)printf("%2d",boardij);printf("n");int main()/ 主函数int x,y;.SqStack S;InitStack(S);printf(" 输入马的初始位置：n");scanf("%d%d",&x,&y);s