// Задача о ходе коня, Coded by Decker ;))

#include <stdio.h>
#define size 8

int arr[size][size], row[size*size], col[size*size];
int ktmov1[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int ktmov2[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int i, j, move_num, d; 

int check(int i, int j) {
register int a, b, e, sum = 0; 

if ( i < 0 || i > (size-1) || j < 0 || j > (size-1) ) return 0;
if ( arr[i][j] == 1 ) return 0; 

for ( a = 0 ; a <= 7 ; a++ ) {
b = i + ktmov1[a]; e = j + ktmov2[a];
if ( b < 0 || b > (size-1) || e < 0 || e > (size-1) ) continue; 
if ( arr[b][e] == 1 ) continue; 
sum++;	
}

if ((sum == 0) && (arr[i][j]==0)) sum = 1; // последний ход

return sum;
}

main() {
	
i=0; j=0; 
addknight( );

}

addknight( ) {

register int a, b, e;
register int mina, min;

arr[i][j] = 1; row[move_num] = i; col[move_num] = j; move_num++;

if ( move_num > size*size-1 ) {
//if (i==7 && j==7) {
writeboard( size*size-1 ); 
printf("i = %d, j = %d\n",i,j);
exit ( 0 );
//}
}

// printf("[%d] i = %d, j = %d\n",move_num,i,j);

min = 8; mina = 0;
for ( a = 0 ; a <= 7 ; a++ ) {
	b = i + ktmov1[a]; e = j + ktmov2[a];
	// printf("%d. [%d,%d] = %d\n",a, b,e,check(b,e));
	if ((check(b,e) > 0) && (check(b,e) < min)) { min = check(b,e); mina = a; }
}

for ( a = 0 ; a <= 7 ; a++ ) {
	b = i + ktmov1[a]; e = j + ktmov2[a];
	if (check(b,e) == min) {
		// printf("%d. [%d,%d] = %d\n",a, b,e,check(b,e));
		i = b; j = e; addknight();
	}
}

move_num-- ; arr[row[move_num]][col[move_num]] = 0; move_num--; i = row[move_num]; j = col[move_num]; move_num++; 

}

writeboard( int step ) {
int a,i,j;
int t[size][size];

for (i=0; i<=size-1; i++) {
for (j=0; j<=size-1; j++) {
	t[i][j] = 0;
}
}



for ( a = 0 ; a <= step ; a++ ) {
	// printf("%d. [%d,%d] = %d\n",a,col[a],row[a],a+1);
t[col[a]][row[a]] = a+1;
}


for (i=0; i<=size-1; i++) {
for (j=0; j<=size-1; j++) {
	printf ( "%5d;", t[i][j]  );
}
printf("\n");
}

printf("\n"); 

}