Backtracking solution to Knight's Tour problem

knightstour.c

// Backtracking solution to Knight's Tour problem http://en.wikipedia.org/wiki/Knights_tour
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
// Constraint: MAXX should be greater than or equal to MAXY
#define MAXX 5
#define MAXY 5
typedef enum {FALSE, TRUE} bool;
int n = 0;
bool treaded_blocks[MAXX][MAXY];

void moveKnight(int x, int y, char *history)
{
    char *current;
    char format[10];
    if( x < 0 || x >= MAXX || y < 0 || y >= MAXY || treaded_blocks[x][y])
    {
        return;
    }
    n++;
    treaded_blocks[x][y] = TRUE;
    current = (char *)malloc(sizeof(char) * strlen(history) + 10);
    //printf("At (%d,%d)\n", x, y);
    strcpy(current, history);
    sprintf(format, "(%d,%d)\t", x, y);
    strcat(current, format);
    moveKnight(x+2, y-1, current);
    moveKnight(x+2, y+1, current);
    moveKnight(x+1, y-2, current);
    moveKnight(x+1, y+2, current);
    moveKnight(x-1, y-2, current);
    moveKnight(x-1, y+2, current);
    moveKnight(x-2, y-1, current);
    moveKnight(x-2, y+1, current);
    if(n == MAXX * MAXY)
    {
        printf("%s\n", current);
    }
    n--;
    treaded_blocks[x][y] = FALSE;
}
int main()
{
    int i, j;
    for(i = 0; i < MAXX; i++)
        for(j = 0; j < MAXY; j++)
            treaded_blocks[i][j] = FALSE;
    for(i = 0; i < (MAXX + 1) / 2; i++)
        for(j = i; j < (MAXY + 1) / 2; j++)
            moveKnight(i,j,"");
    return 0;
}

Leave a comment
show me the output for this program.