#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;
}
