马踏棋盘

编辑:上层网互动百科 时间:2020-02-28 14:46:59
编辑 锁定
本词条缺少名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
一个国际象棋的马踏遍棋盘的演示程序相关的c代码。
中文名
马踏棋盘
内    容
国际象棋的马踏遍棋盘的演示程序
类    型
8×8棋盘
要    求
每个方格只进入一次

马踏棋盘需求分析

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

马踏棋盘核心代码(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("马儿从这个初始位置不能踏遍棋盘\n");
printf("请按任意键推出本程序\n");
getchar();
exit(OVERFLOW);
}
for(j=0;j<8;j++){
printf("\n");
for(k=0;k<8;k++)
printf("%3d",Board[j][k]);
}// for
}//函数结束
void main(){
int k,j;
PosType t;
char a,b;
printf("请输入马儿的初始位置\n");
fflush(stdin);
scanf("%c%d,%d%c",&a,&k,&j,&b);
t.i=k;
t.j=j;
printf("马儿走的路线为\n");
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]<<'\t';
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 ;
}
词条标签:
计算机学