＋设为首页 ＋添加到收藏夹
在一本C语言书上看到一道练习题：8*8的国际象棋棋盘，马从某点开始走64步，每一步都不重复，编程找出这样的一条路线。我用回嗍法编了一下，效率太差，只能找出5*5，6*6，7*7的路线，8*8的太慢了。题目提示用二分法，有谁知道吗？！！
骑士漫游和八皇后
发表日期：2003年5月19日 作者：Redream 已经有274位读者读过此文
/******************************qishi *****************************/
#include <stdio.h>
#include <conio.h>
struct memory
{int sence[8][8] ;
int board[8][8] ;
int mem[8] ;
int last ;
} mem[64] ;
int h[8]={2,1,-1,-2,-2,-1,1,2} ;
int v[8]={-1,-2,-2,-1,1,2,2,1} ;
int board[8][8]={0} ;
int sence[8][8]={{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}} ;
int row, col,hty=0 ;
int comeon(void) ;
void goback(void) ;
int findmin(int[]) ;
void savemem(int) ;
void altsence(void) ;
void print() ;
void printmem(int) ;
/* PREPARE */
void prepare(void)
{int i, j, ha[8],va[8] ;
for(i=0; i<64; i++)
{ mem[i].last=-1 ;
for(j=0; j<8; j++)
mem[i].mem[j]=0 ;
}
printf("Input Begin Point :\n") ;
scanf("%d%d",row,col) ;
board[row][col]=1 ;
for(i=0; i<8; i++)
{ha[i]=row + h[i] ;
va[i]=col + v[i] ;
if( ha[i]>=0 && ha[i]<=7 && va[i]>=0 && va[i]<=7 )
sence[ha[i>[va[i>-- ;
}
savemem(0) ;
/*print(hty) ; */
hty++ ;
}
/* COMEON!! */
int comeon(void)
{int i, ha[8], va[8], b[8]={9,9,9,9,9,9,9,9}, info=0 ;
for(i=0; i<8; i++)
{ ha[i]=row+h[i] ;
va[i]=col+v[i] ;
if( ha[i]>=0 && ha[i]<=7 && va[i]>=0 && va[i]<=7 )
if( board[ha[i>[va[i>==0 && mem[hty].mem[i]!=1 )
b[i]=sence[ha[i>[va[i> ;
}
i=findmin(b) ;
if( b[i]!=9 ) ;
{row=ha[i] ;
col=va[i] ;
board[ha[i>[va[i>=1 ;
altsence() ;
savemem(i) ;
/*printmem(hty) ; */
hty++ ;
info=1 ;
}
return (info) ;
}
/* GOBACK~~ */
void goback(void)
{int i,j ;
hty--;
board[row][col]=0 ;
row = row - h[mem[hty].last] ;
col = col - v[mem[hty].last] ;
mem[hty].mem[mem[hty+1].last] = 1 ;
for(i=0; i<8; i++)
for(j=0; j<8; j++)
sence[i][j]=mem[hty].sence[i][j] ;
}
/* PRINT */
void print(void)
{int i;
for(i=0; i<64; i++)
{clrscr();
printmem(i) ;
getchar() ;
}
}
/* PRINTMEM */
void printmem(int ht)
{int i, j;
printf("No.%d Step;\n",ht) ;
for(i=0; i<8; i++)
{for(j=0; j<8; j++)
if( mem[ht].board[i][j]==0)
printf("O ") ;
else
printf("H ") ;
printf("\n") ;
}
}
/* ALTSENCE */
void altsence(void)
{int i, ha[8], va[8] ;
for(i=0; i<8; i++)
{ha[i]=row + h[i] ;
va[i]=col + v[i] ;
if( ha[i]>=0 && ha[i]<=7 && va[i]>=0 && va[i]<=7 )
sence[ha[i>[va[i>-- ;
}
}
/* SAVEMEM */
void savemem(int lt)
{int i,j ;
mem[hty].last=lt ;
for(i=0; i<8; i++)
for(j=0; j<8; j++)
{mem[hty].sence[i][j] = sence[i][j] ;
mem[hty].board[i][j] = board[i][j] ;
}
}
/* FINDMIN */
int findmin(int c[8])
{int i,j=0 ;
for(i=0; i<8; i++)
if( c[i] < c[j] )
j=i ;
return (j) ;
}
/* MAIN */
main()
{int i;
prepare() ;
i=comeon();
while( hty<64 )
{ if(i)
i=comeon() ;
else
{goback() ;
i=1;
}
}
print();
}
/*************************** 8 queen *********************************/
#include <stdio.h>
int col[8] , temp=0 ;
void qu(int n)
{
int pan(int) ;
void pri(void) ;
int t;
if(n==0)
t=4 ;
else
t=8 ;
for(col[n]=0; col[n]<t; col[n]++ )
{if(pan(n)) continue ;
if (n!=7)
qu(n+1);
else
pri() ;
}
}
void pri(void)
{
int i, j;
for (i=0; i<8; i++)
{for (j=0; j<8; j++)
{if( col[i]==j )
printf("Q ") ;
else
printf("X ") ;
}
printf("\n") ;
}
temp++ ;
printf("\n%d\n",temp) ;
getchar();
}
int pan(int t)
{
int i,n=0 ;
for(i=0; i<t; i++)
{if (col[i]==col[t])
{n=1; break;}
if( (col[t]+t) == (col[i]+i) )
{n=1; break;}
if( (col[t]-t) == (col[i]-i) )
{n=1; break;}
}
return(n);
}
main()
{
printf("\n") ;
qu(0);
printf("%dEnd\n",temp) ;
}
#include<stdio.h>
#include<stdlib.h>
#define n 6 /*方阵为n*n的*/
#define MAXNUM n*n /* 栈中最大元素个数 */
int direction[8][2]={-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1,2,1,1,2};/*相对于位置(i,j)八个方向的增量*/
int area[n][n]; /*n*n方阵*/
int inarea(int x,int y)/*坐标(x,y)在区域内*/
{
return x>=0&&x<n&&y>=0&&y<n;
}
struct Node
{
int x,y,d;
};
typedef struct Node DataType;
struct SeqStack /* 顺序栈类型定义 */
{ DataType s[MAXNUM];
int t; /* 指示栈顶位置 */
};
typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */
PSeqStack createEmptyStack_seq( void )
{ PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack==NULL)
printf("Out of space!! \n");
else
pastack->t=-1;
return (pastack);
}
int isEmptyStack_seq( PSeqStack pastack )
{
return ( pastack->t == -1 );
}
void push_seq( PSeqStack pastack, DataType x )
/* 在栈中压入一元素x */
{ if( pastack->t >= MAXNUM - 1 )
printf( "Overflow! \n" );
else
{ pastack->t = pastack->t + 1;
pastack->s[pastack->t] = x;
}
}
void pop_seq( PSeqStack pastack )
/* 删除栈顶元素 */
{ if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t = pastack->t - 1;
}
DataType top_seq( PSeqStack pastack )
/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
{
return (pastack->s[pastack->t]);
}
void path(int x0,int y0)/*初始位置为(x0,y0)*/
{
int i,j,k;
int g,h;
int step;/*所游历的区域数*/
PSeqStack st;
DataType element;
st = createEmptyStack_seq( );
area[x0][y0]=1;/*1表示此位置游历过*/
element.x = x0;
element.y = y0;
element.d = -1;
push_seq(st,element); /* 初始点进栈 */
step=1;
do
{
element=top_seq(st);
pop_seq(st);
i = element.x;
j = element.y;
k = element.d+1;
area[i][j]=1;
while (k<8&&step<n*n) /* 依次试探每个可能方向 */
{ g=i+direction[k][0];
h=j+direction[k][1];
if (inarea(g,h)==1&&area[g][h]==0)
{
area[g][h]=1;
step++;
element.x = i;
element.y = j;
element.d = k;
push_seq(st,element); /* 进栈 */
i=g; /* 下一点转换成当前点 */
j=h;
k=-1;
}
k++;
}
if(step<n*n)
{
area[i][j]=0;
step--;
}
}while(!isEmptyStack_seq(st)&&step<n*n);
if(step<n*n)
printf("cannot find the path !\n");
else
{
printf("the reverse path is :\n");
printf(" %d , %d\n",g,h);
while(!isEmptyStack_seq(st))
{
element=top_seq(st);
pop_seq(st);
printf(" %d , %d\n",element.x,element.y);
}
}
}
int main()
{
int x0,y0;
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
area[i][j]=0;/*初始化,0表示未游历过*/
printf("please input the position (x0,y0)\nx0=");
scanf("%d",&x0);
printf("y0=");
scanf("%d",&y0);
path(x0,y0);
return 0;
}
//kaode
