馬踏棋盤

一個西洋棋的馬踏遍棋盤的演示程式相關的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 ;
}

相關詞條

熱門詞條

聯絡我們