//////////////////////////////////////////////////////////////////////////
/*                       騎士巡游問題                                   */
/////////////////////////////////////////////////////////////////////////

#include <stdio.h>
int f[11][11] ;                                /*定義一個矩陣來模擬棋盤*/
int adjm[121][121];/*標志矩陣，即對于上述棋盤，依次進行編號
		    1--121(行優先）可以從一個棋盤格i跳到棋盤格j時，adjm[i][j]=1*/

void creatadjm(void);                            /*創建標志矩陣函數聲明*/
void mark(int,int,int,int);                     /*將標志矩陣相應位置置1*/
void travel(int,int);                                    /*巡游函數聲明*/
int n,m;                                 /*定義矩陣大小及標志矩陣的大小*/


/******************************主函數***********************************/
int main()
{
    int i,j,k,l;
    printf("Please input size of the chessboard: ");  /*輸入矩陣的大小值*/
	scanf("%d",&n);
    m=n*n;
    creatadjm();                                         /*創建標志矩陣*/
	puts("The sign matrix is:");
    for(i=1;i<=m;i++)                                /*打印輸出標志矩陣*/
    {
        for(j=1;j<=m;j++) 
			printf("%2d",adjm[i][j]);
        printf("\n");
    }
    
    printf("Please input the knight's position (i,j): "); /*輸入騎士的初始位置*/
    scanf("%d %d",&i,&j);
    l=(i-1)*n+j;                   /*騎士當前位置對應的標志矩陣的橫坐標*/
    while ((i>0)||(j>0))                             /*對騎士位置的判斷*/
    {
        for(i=1;i<=n;i++)                              /*棋盤矩陣初始化*/
            for(j=1;j<=n;j++)
                f[i][j]=0;
        k=0;                                             /*所跳步數計數*/
        travel(l,k);                                /*從i,j出發開始巡游*/
        puts("The travel steps are:");
        for(i=1;i<=n;i++)                      /*巡游完成后輸出巡游過程*/
		{
            for(j=1;j<=n;j++) 
			    printf("%4d",f[i][j]);
            printf("\n");
		}
        
        printf("Please input the knight's position (i,j): ");/*為再次巡游輸入起始位置*/
	    scanf("%d %d",&i,&j);
        l=(i-1)*n+j;
    }
	puts("\n Press any key to quit... ");
	getch();
    return 0;
}



/*****************************創建標志矩陣子函數*************************/
void creatadjm()
{
    int i,j;
    for(i=1;i<=n;i++)                                   /*巡游矩陣初始化*/
        for(j=1;j<=n;j++)
            f[i][j]=0;
    for(i=1;i<=m;i++)                                   /*標志矩陣初始化*/
        for(j=1;j<=m;j++)
            adjm[i][j]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(f[i][j]==0)           /*對所有符合條件的標志矩陣種元素置1*/
			{
                f[i][j]=1;
                if((i+2<=n)&&(j+1<=n)) mark(i,j,i+2,j+1);
                if((i+2<=n)&&(j-1>=1)) mark(i,j,i+2,j-1);
                if((i-2>=1)&&(j+1<=n)) mark(i,j,i-2,j+1);
                if((i-2>=1)&&(j-1>=1)) mark(i,j,i-2,j-1);
                if((j+2<=n)&&(i+1<=n)) mark(i,j,i+1,j+2);
                if((j+2<=n)&&(i-1>=1)) mark(i,j,i-1,j+2);
                if((j-2>=1)&&(i+1<=n)) mark(i,j,i+1,j-2);
                if((j-2>=1)&&(i-1>=1)) mark(i,j,i-1,j-2);
			} 
    return;
}


/*********************************巡游子函數*******************************/
void travel(int p,int r)
{
    int i,j,q;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(f[i][j]>r) f[i][j]=0;              /*棋盤矩陣的置〉r時，置0*/
    r=r+1;                                                   /*跳步計數加1*/
    i=((p-1)/n)+1;                                  /*還原棋盤矩陣的橫坐標*/
    j=((p-1)%n)+1;                                  /*還原棋盤矩陣的縱坐標*/
    f[i][j]=r;                              /*將f[i][j]做為第r跳步的目的地*/
   


    for(q=1;q<=m;q++)           /*從所有可能的情況出發，開始進行試探式巡游*/
	{
        i=((q-1)/n)+1;
        j=((q-1)%n)+1;
        if((adjm[p][q]==1)&&(f[i][j]==0)) 
			travel(q,r);                                    /*遞歸調用自身*/
    }
    return;
}

/*************************賦值子函數***************************************/
void mark(int i1,int j1,int i2,int j2)
{
    adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
    adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
    return;
}