需求分析
將馬隨機放在西洋棋的Board[0～7][0～7]的某個方格中，馬按走棋規則進行移動。，走遍棋盤上全部64個方格。編制非遞歸程式，求出馬的行走路線，並按求出的行走路線，將數字1，2，…，64依次填入一個8×8的方陣，輸出之。核心代碼（c語言）
#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10
#defineOVERFLOW-2
#defineOK1
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
intBoard[8][8]={0};
intHTry1[8]={2,-1,1,-2,2,1,-1,-2};
intHTry2[8]={1,2,2,1,-1,-2,-2,-1};
typedefstruct{
inti;
intj;
}PosType;
typedefstruct{
intord;
PosTypeseat;
intdi;
}SElemType;
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
intInitStack(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);
}
SElemTypePop(SqStack*s,SElemTypee){
e=*--(*s).top;
returne;
}
intPush(SqStack*s1,SElemTypee){
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;
returnOK;
}
intStackEmpty(SqStack*s){
if((*s).base==(*s).top)
return(1);
else
return(0);
}
intcurstep=0;
intPass(PosTypes){
if((Board[s.i][s.j]==0)&&(s.i<=7)&&(s.i>=0)&&(s.j<=7)&&(s.j>=0))
return(1);
else
return(0);
}
PosTypeNextPos(PosTypes,inti){
s.i=s.i+HTry1[i-1];
s.j=s.j+HTry2[i-1];
return(s);
}
voidhorsesteps(intBoard[8][8],PosTypestart){
intk,j;
SqStackS;
SElemTypee;
PosTypecurpos=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
}//函式結束
voidmain(){
intk,j;
PosTypet;
chara,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>
usingnamespacestd;
typedefstruct_point
{
intx;
inty;
}point;
classHorse
{
public:
Horse(intn);
~Horse();
voidMoveNext(inthang,intlie);
voidPrint();
public:
intshu;
intqipan[20+1][20+1];
pointpt[400+1];
intci;
};
Horse::Horse(intn)
{
ci=0;
shu=n;
for(inti=1;i<=shu;i++)
for(intj=1;j<=shu;j++)
qipan[i][j]=0;
}
Horse::~Horse()
{
}
voidHorse::Print()
{
if(pt[0].x==shu*shu)
{
ci++;
cout<<ci<<"Yes!"<<endl;
for(inti=1;i<=shu;i++)
for(intj=1;j<=shu;j++)
{
cout<<qipan[i][j]<<'\t';
if(j==shu)
cout<<endl;
}
}
}
voidHorse::MoveNext(inthang,intlie)
{
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--;
}
}
intmain()
{
printf("Inputthenum:");
intn;
scanf("%d",&n);
Horseh(n);
h.MoveNext(1,1);
return0;
}
翹了一學期的數據結構，趕工補作業中，我用的是貪心算法，速度不錯，秒出。。
#include<iostream>
#defineM12
#defineD8
usingnamespacestd;
intpathnum(intx,inty);
voidinitdata();
intpathnum(intx,inty);
voidfindway(intx,inty);
intboard[M][M]={0,0};
intHTry1[D]={-2,-1,1,2,2,1,-1,-2};
intHTry2[D]={1,2,2,1,-1,-2,-2,-1};
voidinitdata()
{
inti,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;
}
}
}
intmain()
{
voidfindway(intx,inty);
intstartx,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;
}
return0;
}
voidfindway(intx,inty)
{
x=x+1;
y=y+1;
intstepnum=1;
intnum[D];
inti,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;
}
}
intpathnum(intx,inty)
{
//返回當前位置可走的方向數目
intcount=0;
for(inti=0;i<D;i++)
{
if(board[x+HTry1[i]][y+HTry2[i]]==0)
{
count++;
}
}
returncount;
}
