-
馬踏棋盤
鎖定
- 中文名
- 馬踏棋盤
- 外文名
- Knight's tour problem
- 別 名
-
騎士周遊
馬步遍歷 - 所屬學科
- 計算機算法
馬踏棋盤需求分析
將馬隨機放在國際象棋的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("馬兒從這個初始位置不能踏遍棋盤\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);
}