1.内容:设计一个国际象棋的马踏遍棋盘的演示程序

2.需求分析

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

#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]<<'\\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;

}