chess_horse.c

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

int n;
int **chess_desk = NULL;

struct dir_t {
    int x;
    int y;
} dirs[8] = {
{  1,  2},
{ -1,  2},
{ -2,  1},
{ -2, -1},
{ -1, -2},
{  1, -2},
{  2, -1},
{  2,  1},
//------------
//{  1,  2},
//{ -1,  2},
//{  1, -2},
//{ -1, -2},
//{  2,  1},
//{ -2,  1},
//{  2, -1},
//{ -2, -1},
};


// Initialize (chess_desk)
void init (int n)
{
    int i = 0;
    chess_desk = (int **)malloc(n * sizeof(int *));
    for (; i < n; i++) {
        chess_desk[i] = calloc(n, sizeof(int));
    }
}

// Free (chess_desk)
void free_matrix ()
{
    int i = 0;
    for (; i < n; i++) {
        free(chess_desk[i]);
    }
    free(chess_desk);
}


// Return number of not visited neighbors
int number_of_free (int x, int y)
{
    if (x < 0 || y < 0 || x >= n || y >= n)
        return -1;
    if (0 != chess_desk[x][y])
        return -1;
    int i = 0;
    int xi = 0, yi = 0;
    int result = 0;
    for (i = 0; i < n; i++) {
        xi = x + dirs[i].x;
        yi = y + dirs[i].y;
        if (xi < 0 || yi < 0 || xi >= n || yi >= n) {
            // nothing to do here
        } else if (0 == chess_desk[xi][yi]) {
            result += 1;
        }
    }
    return result;
}


// Making one step. Returns number of chosen direction
int make_choice (int x, int y)
{
    int i = 0;
    int choice = -1;
    int n_ch = 100;
    int temp;
    for (i = 0; i < 8; i++) {
        temp = number_of_free(x + dirs[i].x, y + dirs[i].y);
        if (-1 == temp) {
            // nothing to do here
            continue;
        } else if (temp < n_ch) {
            choice = i;
            n_ch = temp;
        }
    }
    return choice;
}

int main(void)
{
    int i = 1;
    int x = 0, st_x = 0;
    int y = 0, st_y = 0;
    int choice;
    int size = 0;

    scanf("%d", &n);
    size = n * n;

    // double circle for start position
    do {
        st_x = 1;
        do {
            i = 1;
            x = st_x;
            y = st_y;

            init (n);
            chess_desk[x][y] = 1;

            // double sircle for each step
            do {
                printf("log: x = %d, y = %d\n", x + 1, y + 1);
                choice = make_choice(x, y);
                if (-1 == choice) {
                    break;
                }
                x += dirs[choice].x;
                y += dirs[choice].y;
                chess_desk[x][y] = 1;
                i += 1;
            } while (i < size);

            printf("Build complited.\n");
            printf("Status: %s\n", (i == size ? "SUCCESS" : "FAIL"));

            free_matrix();

            st_x += 1;
        } while (i < size && st_x < n);
        st_y += 1;
    } while (i < size && st_y < n);

    return 0;
}