#include<iostream>
#define N 4
using namespace std;

// defines a structure for chess moves
typedef struct chess_moves {
   // 'x' and 'y' coordinates on chess board
   int x,y;
}chess_moves;

// displays the knight tour solution
void printTour(int tour[N+1][N+1]) {
   int i,j;
   cout<<tour[N][N]<< " ";
  // for (i = 0; i < N+1; i++) {
   //   for (j = 0; j < N+1; j++) {
          //cout<<tour[i][j]<<"\t";
   //   }
    //  cout<<endl;
   //}
}

// check if the next move (as per knight's constraints) is possible
bool isMovePossible(chess_moves next_move, int tour[N+1][N+1]) {
   int i = next_move.x;
   int j = next_move.y;
   if ((i >= 0 && i <= (N+1)) && (j >= 0 && j <= (N+1)) && (tour[i][j] == 0))
      return true;
   return false;
}


// recursive function to find a knight tour
bool findTour(int tour[N+1][N+1], chess_moves move_KT[],
               chess_moves curr_move, int move_count) {
   int i;
   chess_moves next_move;
   if (move_count == (N+1)*(N+1)-1) {
      // Knight tour is completed i.e all cells on the
      // chess board has been visited by knight once 
      return true;   }

   // try out the possible moves starting from the current coordinate
    int temp = move_count;
   for (i = 0; i < 8; i++) {
      A:
       // get the next move
      next_move.x = curr_move.x + move_KT[i].x;
      next_move.y = curr_move.y + move_KT[i].y;

      if (isMovePossible(next_move, tour)) {
         // if the move is possible
         // increment the move count and store it in tour matrix
         //temp = move_count;
         if ((next_move.x == N) && (next_move.y == N))
         {
             //cout << next_move.x << " : " << next_move.y <<" : " << tour[next_move.x][next_move.y] << endl;
             if ((temp >= (move_count+1)))// || (tour[N][N] == 0))
             {    
                 cout <<  " Case ID  " << i <<" : " << tour[next_move.x][next_move.y] << endl;
                 //tour[N][N] = move_count+1;
                 temp = move_count +1;
             }
             //i = i+1;
             if(i<8)
                 goto A;
             else
             {
                 tour[N][N] = temp;
                 return true;
             }
         }
         else tour[next_move.x][next_move.y] = move_count+1;
         
         if (findTour(tour, move_KT, next_move, move_count+1) == true) {
            return true;
         }
         else {
            // this move was invalid, try out other possiblities 
            tour[next_move.x][next_move.y] = 0;
             
         }
         
      }
       
   }
   return false;
}

// wrapper function
void knightTour() {
   //const int N;
   // cin >> N;
   int tour[N+1][N+1],final[N][N];
   int i,j;

   // initialize tour matrix
   
//N = N+1;
   // all possible moves that knight can take
   //chess_moves move_KT[8] = { {2,1},{1,2},{-1,2},{-2,1},                             {-2,-1},{-1,-2},{1,-2},{2,-1} };
   for (int ith=1; ith<=N-5; ith++ )
    {
    for (int jth=1; jth<=N-5; jth++ )
    {
   for (i = 0; i <= N; i++) {
      for (j = 0; j <=N; j++) {
         tour[i][j] = 0;
      }
   }
    chess_moves move_KT[8] = { {ith,jth},{jth,ith},{-jth,ith},{-ith,jth},{-ith,-jth},{-jth,-ith},{jth,-ith},{jth,-ith} };


   // knight tour starts from coordinate (0,0)
   chess_moves curr_move = {0,0};

   // find a possible knight tour using a recursive function
   // starting from current move 
   if(findTour(tour, move_KT, curr_move, 0) == false) {
      //cout<<"\nKnight tour does not exist";
       cout<<ith << " : " << jth << " : " ;
       cout<<"-1 "<< endl;
       final[ith-1][jth-1] =-1;
   }
   else {
      cout<<ith << " : " << jth << " : " ;
      printTour(tour);
              cout << endl;
       final[ith-1][jth-1] = tour[N][N];

      //printTour(tour);
   }
}
       cout << endl;
}
    
        for (i = 0; i < N; i++) 
       {
           for (j = 0; j < N; j++)
           {
               if(((final[i][j]>final[j][i]) || (final[i][j]==-1))&&(final[i][j]!=-1))
                   cout << final[j][i] << " ";
               else 
                   cout << final[i][j] << " ";
           }
           cout << endl;
       }

}

// main
int main() {
   knightTour();
   cout<<endl;
   return 0;
}