//KNIGHT’S TOUR
// 課題用3×4
#include <stdio.h>

#define M 3
#define N 4

int array[M][N];
int count;

void print(void)
{
   int i,j;
   
   for(i=0;i<N;i++){
       for(j=0;j<M;j++){
           printf("%3d",array[j][i]);
       }
       printf("\n");
   }
   printf("\n");
}

void check(int x, int y, int cnt)
{
   if(x<0 || x>=M) return;
   if(y<0 || y>=N) return;
   if(array[x][y]) return;
   
   //printf("%d\n", cnt);
   array[x][y]=cnt;
   cnt++;
   
   if(cnt>M*N){
   		count++;
		printf("[%d]\n", count);
		print();
   }
   
   check(x+1, y+2, cnt);
   check(x+1, y-2, cnt);
   check(x-1, y+2, cnt);
   check(x-1, y-2, cnt);
   check(x+2, y+1, cnt);
   check(x+2, y-1, cnt);
   check(x-2, y+1, cnt);
   check(x-2, y-1, cnt);
   
   array[x][y]=0;    
}

int main(void)
{
   int i,j;
   for(i=0;i<N;i++) {
       for(j=0;j<M;j++) {
           array[j][i] = 0;
       }
   }
   
   count=0;
   check(0,0,1);
       
   return 0;
}