Minimum number of moves for a knight

The problem is to find the minimum number of moves that a knight will take to go from one square to another on a 'n' cross 'n' chessboard. The code below is based on backtracking. It works well until n equals 5 but from n equals 6 the time limit is exceeded on ideone. How can I make the code more efficient?

#include 

int minimum(int a, int b)
{
    /* Returns the minimum of two numbers */
    if (a  n - 1) || (c2  n - 1)) {
        return 32764;
    }

    /* Condition to check if the path is complete */
    if ((r1 == r2) && (c1 == c2)) {
        return 0;
    }

    /* We add the point with coordinates r2, c2 to the path */
    array[r2][c2] = 1;

    /* All the possible moves that a knight can make */
    moves = 1 + minmoves(r1, c1, r2 - 2, c2 - 1, array);
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 2, c2 + 1, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 1, c2 - 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 1, c2 + 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 1, c2 - 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 1, c2 + 2, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 2, c2 - 1, array));
    moves = minimum(moves, 1 + minmoves(r1, c1, r2 + 2, c2 + 1, array));

    array[r2][c2] = 0;

    return moves;
}

int main()
{
    int r1, c1, r2, c2, x, i, j, n;
    int array[10][10];

    scanf("%d\n%d\n%d\n%d\n%d", &r1, &c1, &r2, &c2, &n);

    /* All the elements of array are initialised to zero */
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            array[i][j] = 0;
            printf("0 ");
        }
    }

    x = minmoves(r1, c1, r2, c2, array, n);

    printf("%d",x);
    return 0;
}

I will answer an isomorphous question of finding a minimal value in a binary tree. In your case, the tree is octal, but the same rules apply.

Consider that you have

typedef struct node {
     struct node *pLeft, *pRight;
     int value;
} node_t;

The tree is completely unsorted, and you need to find the minimal value. What you are doing is something like this:

int minval(node_t *pRoot)
{
    if (pRoot == NULL)
        return INT_MAX;

    int min = pRoot->value;

    min = minimum(min, minval(pRoot->pLeft));
    min = minimum(min, minval(pRoot->pRight));

    return min;
}

This is a recursive algorithm. It's elegant, nice, cool and bloody slow.

Recursion is slow because every time you call a function it has to do all sorts of staging (pass arguments, call function, allocate stack space), and then repeat all that on return (clean up stack, return from call, clean up arguments).

There are non recursive algorithms to most problems, but there's also a nice way to get rid of all the costly staging for calling a function. (inlining a function does that too, but it is not possible for recursive functions). Let us take a look at code that does exactly the same thing as above, but without recursion:

int minval(node_t *pRoot)
{
    if (pRoot == NULL)
        return INT_MAX;

    node_t *stack[100]; // At least max tree depth*2, in your case n*8
    int sp = 0;
    int min = INT_MAX; 

    stack[sp++] = pRoot;
    while (sp > 0)
    {
        node_t *p = stack[--sp];
        min = minimum(min, p->value);

        if (p->pLeft  != NULL) stack[sp++] = p->pLeft; 
        if (p->pRight != NULL) stack[sp++] = p->pRight;
    }

    return min;
}

Here we have a simulated program stack, but we don't do so much with it, we only add one pointer for every tree node, which in your case is 8^5, or 32768. Compared to that many function calls.

If you modify your program to not actually call the function recursively, you should gain a very significant speed boost. Using the template I provided, it shouldn't be a problem, you'll just have 8 things to put on the stack every iteration.

Fun fact: What you are doing is known as a preorder tree traversal, also known as a depth-first search. If you were to do a level order traversal (also known as a breadth-first search), the code would go faster. The difference is that DFS will look at all paths, while you can stop BFS early as soon as it finds one.

StackExchange Code Review Q#96269, answer score: 5