马踏棋盘问题

#include

usingnamespacestd;

structinfo{intx,y,out;};

constintdx[8]={-2,-2,-1,-1,1,1,2,2};

constintdy[8]={-1,1,-2,2,-2,2,-1,1};

constintR=8,C=8;

intboard[R][C];

intoutlet(intx,inty)

{

intct=0;

for(inti=0;i<8;++i)

if(x+dx[i]=R||y+dy[i]>=C||board[x+dx[i]][y+dy[i]])continue;

else++ct;

returnct;

}//计算(x,y)的出口数

voidsort(info*p,intn)

{

for(inti=n-1;i>0;--i)

if(p[i].out<p[i-1].out)swap(p[i],p[i-1]);

elsebreak;

}//按出口数由小到大排序

boolsearch(intx,inty,intstep)

{

if(board[x][y])returnfalse;

if(step==R*C)

{

board[x][y]=step;

returntrue;

}

else

{

board[x][y]=step;

inti,j;infodir[8];

for(i=j=0;i<8;++i)

if(x+dx[i]=R||y+dy[i]>=C||board[x+dx[i]][y+dy[i]])continue;

else

{

dir[j].x=x+dx[i];dir[j].y=y+dy[i];

dir[j].out=outlet(dir[j].x,dir[j].y);

sort(dir,++j);

}

for(i=0;i<j;++i)

if(search(dir[i].x,dir[i].y,step+1))returntrue;

board[x][y]=0;

returnfalse;

}

}//求解

intmain()

{

inti,j,m,n;

for(i=0;i<R;++i)

for(j=0;j<C;++j)

{

memset(board,0,R*C*sizeof(int));

if(search(i,j,1))

{

printf(startat(%d,%d):\n,i+1,j+1);

for(m=0;m<R;++m)

{

for(n=0;n<C;++n)

printf(%4d,board[m][n]);

printf(\n\n);

}

}

else

printf(startat(%d,%d)hasnosolve!\n,i+1,j+1);

}

system(pause);

return0;

}