#include <stdio.h>
#include <stdlib.h>
#define n_base 8
#define n_offset 2
#define N n_base + 2*n_offset

typedef enum {
    false, true
} bool;

typedef struct {
    int x;
    int y;
} point_t;

void initMap(int map[N][N]);
void searchPath(int map[N][N]);
void princ_molt(int pos, int map[N][N], int val[8][2], int n_choise, bool *start, point_t *currPos, point_t *newPos);
void delMove(int map[N][N], point_t *currPos, int *to_del);
bool setMove(int map[N][N], point_t *currPos, point_t *newPos);
bool checkMove(int map[N][N], point_t *currPos, point_t *newPos);
bool isFree(int map[N][N], point_t *currPos, point_t *newPos);

int main() {
    int map[N][N];

    /*init*/
    initMap(map);

    searchPath(map);

    return 0;
}

void initMap(int map[N][N]) {
    int i, j;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) {
            if (j < n_offset || j >(n_base + 1) || i < n_offset || i > (n_base + 1))
                map[i][j] = -2;
            else
                map[i][j] = 0;
        }
}

void searchPath(int map[N][N]) {
    /*1st column: y move.
      2nd column: x move.*/
    int val[8][2] = {
        {+2, +1},
        {+2, -1},
        {+1, +2},
        {+1, -2},
        {-2, +1},
        {-2, -1},
        {-1, +2},
        {-1, -2} };
    int n_choise = 8;
    point_t currPos, newPos;
    bool start = 1;

    currPos.x = 2;
    currPos.y = 2;
    newPos.x = 0;
    newPos.y = 0;

    map[currPos.y][currPos.x] = 1;

    princ_molt(0, map, val, n_choise, &start, &currPos, &newPos);
}

void princ_molt(int pos, int map[N][N], int val[8][2], int n_choise, bool *start, point_t *currPos, point_t *newPos) {
    int i, j;

    if (pos >= 62)
        printf( "%d ", pos);

    if (pos >= 63) {
        printf("\n\n");
        for (i = 2; i < 10; i++) {
            for (j = 2; j < 10; j++)
                printf("[ %d ] ", map[i][j]);
            printf("\n");
        }
        return;
    }

    if (*start)
        *start = false;

    for (i = 0; i < n_choise; i++) {
        newPos->x = val[i][1];
        newPos->y = val[i][0];
        if (isFree(map, currPos, newPos)) {
            if (setMove(map, currPos, newPos)) {
                princ_molt(pos + 1, map, val, n_choise, start, currPos, newPos);

                delMove(map, currPos, val[i]); //backtrack
            }
        }
    }

}

void delMove(int map[N][N], point_t *currPos, int *to_del) {

    map[currPos->y][currPos->x] = 0;
    currPos->y -= to_del[0];
    currPos->x -= to_del[1];
}

bool setMove(int map[N][N], point_t *currPos, point_t *newPos) {

    if (checkMove(map, currPos, newPos)) {
        map[currPos->y + newPos->y][currPos->x + newPos->x] = map[currPos->y][currPos->x] + 1;
        currPos->y += newPos->y;
        currPos->x += newPos->x;
        return true;
    }

    return false;
}

bool checkMove(int map[N][N], point_t *currPos, point_t *newPos) {
    return (map[currPos->y + newPos->y][currPos->x + newPos->x] == 0);
}

bool isFree(int map[N][N], point_t *currPos, point_t *newPos) {
    int x = currPos->x + newPos->x;
    int y = currPos->y + newPos->y;

    if ((y < 0 + n_offset || y >= N - n_offset) || (x < 0 + n_offset || x >= N - n_offset))
        return false;

    return true;
}