#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define directions 8

class Step
{
	public:
		Step();		
		Step(int a,int b);
		void get(Step current, int* possibleSteps, int number);		
		int x; 
		int y; 	
};

Step::Step() {
    x=0;
    y=0;
}

Step::Step(int a, int b) {
    x=a;
    y=b;
}
 
int count(int* possibleSteps) {					//傳入紀錄可走方向的一維陣列
    int c, i;									//變數c用來接出路數量(初始值0)、變數i為8方向計數器
    for(c = 0, i = 0; i < directions; i++)		//檢查八個方向
	 if(possibleSteps[i]) {						//如果這個方向有值(值為1或0而已)
     	   c++;									//出路數就+1
    	   }									//結束小if迴圈
    return c;									//回傳出路數量
}												//count函式結束
 
void Step::get(Step current, int* possibleSteps, int number) {		//傳入現在座標，已經記錄好可走方向的一維陣列，第幾條出路(最少為1)
	const int idir[8]={-2,-1,1,2, 2, 1,-1,-2};  //能走的8個方向i值的變化
	const int jdir[8]={ 1, 2,2,1,-1,-2,-2,-1};  //能走的8個方向j值的變化
    int c=0, i=0;	
    for(c = 0, i = 0; i < directions; i++) if(possibleSteps[i]) {
        c++;
        if(c == number) {
            break;
        }
    }
	this->x=current.x+idir[i];
	this->y=current.y+jdir[i];
}
 
void travel(int n)
{
	const int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2},   {2, 1}, 	  
                      {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}; 	  //八個方向的移動
	int **board;  												  //將來要輸出在螢幕上的棋盤
	board=new int*[n];  										  //nXn陣列
	for(int x=0;x<n;x++)
	{
		board[x]=new int[n];
	}
	for(int x=0;x<n;x++)  							//將board初始化
	{
		for(int y=0;y<n;y++)
			board[x][y]=0;
	}
	board[0][0]=1;									//起點為(0,0)
	
	Step current=Step(0,0);							//現今騎士的座標
	int st;											//代表步數計數器*/
	for(st = 2; st <n*n+1; st++){					//走滿步(格)數就算完成*/ 
		int possibleSteps[directions]={0};			//一維陣列，8方向*/
		int k;										//變數k為8方向計數器
    	for(k = 0; k < directions; k++)				//run8個方向的for迴圈
    	{					
        	Step s = Step(current.x + dirs[k][0], current.y + dirs[k][1]);	//s代表往方向k後的座標位置     	
			if( s.x > -1 && s.x < n &&s.y > -1 && s.y < n)//決定下個位置可不可以走
			{
            	if(!board[s.x][s.y]) 					//而且這個位置沒有被佔據(值大於1即為被占據)
            	{						
            	possibleSteps[k] = 1;				//我們就把這個方向設定為1(值為1或0。1可以走，0不可以走)        	 	
				}
			}										//if迴圈結束     	 	
    	}											//for迴圈結束	

        int c = count(possibleSteps);				//c代表現在這個位置有幾個出路 

		if(c == 0){									/*沒有出路即為死路，跳出迴圈*/ 
			break;
		}
		
		if(c == 1) {								/*如果只有一條出路，下一步只有一個可能*/
          current.get(current, possibleSteps, 1);
      }	
      
        else {
			const int tdirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}; 											
			int minPossibleSteps[directions] = {0};  
    		Step s1=Step();
			s1.get(current, possibleSteps, 1);
				
    		int k;									 		
    		for(k = 0; k < directions; k++)
			{					
       			Step ss = Step(s1.x + tdirs[k][0], s1.y + tdirs[k][1]);	//s暫存第一條出路的下一個朝k方向移動後的座標 
        			if(ss.x > -1 && ss.x < n &&	ss.y > -1 && ss.y < n ) //檢查s朝k方向移動後是否在合理的位子
					{
						if(!board[ss.x][ss.y]) 
						{
            			minPossibleSteps[k] = 1;						//若合理，k方向就紀錄可以走 
        				}		
	   				}
			}
    		int minIndex,i;												//兩個變數，minIndex是最小出路陣列的索引值、i是計數器

			for(minIndex = 0, i = 1; i < count(possibleSteps); i++) 
			{ 
       			int nextPossibleSteps[directions] = {0};      			 //設一個歸零過的一維陣列(大小為8)暫存第2條以上出路的可走方向 
       			Step s2 = Step();
				s2.get(current, possibleSteps, i + 1);  				 //設s2來接下一個出路的座標。(get的第三個參數可以說是往第幾個出路移動) 	
				int k;											
    			for(k = 0; k < directions; k++) 						//將可走方向記錄到一維陣列裡
				{						 
       				Step sss = Step(s2.x + tdirs[k][0], s2.y + tdirs[k][1]); 	
       				if(sss.x > -1 && sss.x < n && sss.y > -1 && sss.y < n )
       				{
	    	   			if(!board[sss.x][sss.y]) 
						{
   		         		nextPossibleSteps[k] = 1;
        				}	
       				}       		
				}	
        			if(count(nextPossibleSteps) < count(minPossibleSteps)) 
					{
            			minIndex = i;										//i代表比第一個出路後的座標還擁有最少出路的第i個座標，索引值放進minIndex
            			int j;												//變數j作為計數器
            			for(j = 0; j < directions; j++) 
						{													//把該座標哪些方向可通洗進去minPossibleSteps[j]
             		 	  	minPossibleSteps[j] = nextPossibleSteps[j];
            			}
        			}
   			}											//end_for其他出路與決定要走哪個出路跑完  
	current.get(current, possibleSteps, minIndex+1);
    	}//end_else											
board[current.x][current.y] = st;						/*將當前步數位置設定到棋盤上*/

	}													/*結束for迴圈*/
		
    int b;												/*印出board*/
    for(b = 0; b < n; b++) {
        int j;
        for(j = 0; j < n; j++) {
            printf("%3d", board[b][j]);
        }
	      printf("\n");
  	  }
  	  
delete [] board;

}														/*結束travel函式*/	
 
int main() {
	
    travel(5);
    return 0;
}