#include <stdlib.h>
#include <stdio.h>

#define move_types 8
int possible_moves[move_types][2]  = {
        {-1, -2}, {-2, -1}, {-2,  1}, { 1, -2},
        {-1,  2}, { 2, -1}, { 1,  2}, { 2,  1}
};

int **desc_state;
int size_x, size_y;
int cur_x, cur_y;

int max_moves;
unsigned int back_ret;

int position_possible(int x, int y)
{
        return x >= 0 && y >= 0 && x < size_x && y < size_y;
}

int move_possible(int x, int y)
{
        return position_possible(x,y) && desc_state[x][y] == 0;
}

int find_path(int cur_x, int cur_y, int move_num)
{
        int i = 0;
        int next_x = 0, next_y = 0;
        desc_state[cur_x][cur_y] = move_num;

        if(move_num > max_moves)
                return 1;

        for(i = 0; i < move_types; ++i)
        {
                next_x = cur_x + possible_moves[i][0];
                next_y = cur_y + possible_moves[i][1];

                if(move_possible(next_x, next_y) && find_path(next_x, next_y, move_num + 1))
                        return 1;
        }

        desc_state[cur_x][cur_y] = 0;
        ++back_ret;
        --move_num;

        return 0;
}

void init(int **desc, int nrows, int ncols, int start_x, int start_y)
{
        int i = 0, j = 0;
        desc_state = desc;
        size_x = nrows;
        size_y = ncols;

        for(i = 0; i < size_x; ++i) {
                for(j = 0; j < size_y; ++j)
                        desc_state[i][j] = 0;
        }

        back_ret = 0;
        max_moves = size_x * size_y - 1;
}

void output_path()
{
        int i, j;
        for(i = 0; i < size_x; ++i) {
                for(j = 0; j < size_y; ++j)
                        printf("%02d ", desc_state[i][j]);

                printf("\n");
        }
}

int main()
{
        int i = 0;
        int nrows = 5;
        int ncols = 5;

        int **desc = NULL;
        int sx = 0;
        int sy = 0;

        desc = (int **)malloc(sizeof(int) * nrows);
        for(i = 0; i < nrows; ++i)
                desc[i] = (int *)malloc(sizeof(int) * ncols);

        init(desc, nrows, ncols, sx, sy);

        if(find_path(sx, sy, 1))
                output_path();
        else
                printf("path not found\n");

        for(i = 0; i < nrows; ++i)
                free(desc[i]);
        free(desc);

        system("PAUSE");
        return 0;
}