Minimum number of moves for a knight

Question

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 <stdio.h>

int minimum(int a, int b)
{
    /* Returns the minimum of two numbers */
    if (a <= b) {
        return a;
    } else {
        return b;
    }
}

int minmoves(int r1, int c1, int r2, int c2, int array[10][10], int n)
{
    int moves;

    /*
     * If the place is already occupied dont go to it otherwise it will
     * lead to a infinite loop so we return a large value so that the
     * knight does not take this path
     */
    if (array[r2][c2] == 1) {
        return 32764;
    }

    /* We cannot go outside the board */
    if ((r2 < 0) || (r2 > n - 1) || (c2 < 0) || (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;
}

Answer 1

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.

Answer 2

[Edit] Better idea: simplified search technique: O(r*c) complexity

Initialize all board locations to "Not Visited".
Append end point into a new queue
while (queue not empty) {
  pull location from queue.
  if (location == start) we are done.
  for each parent_square that can jump to this location:
    if board[parent_location] == "Not Visited"  (This is the key!)
      assign board[parent_location] = location
      append parent_location to queue
    }
  }
}

---

Rather than array[10][10], use the below. The margin [red] is a 2 wide edge about board that is pre-populated with 1 to indicate the knight can not go there. That eliminates the if (r2<0 || r2>(n-1) || c2<0 || c2 > (n - 1)) test. By using a power of 2 for the last dimension, code can often perform index calculations faster - even with extra [black] do nothing columns. By using unsigned char, the array is smaller and may cache better - YMMV. Using board rather than array is simply a better name.

#define BOARD_N 8
#define BOARD_N_MARGIN (2+8+2)
#define BOARD_N_MARGIN_POWER_2 16

unsigned char board[BOARD_N_MARGIN][BOARD_N_MARGIN_POWER_2];

Further: Use 1 dimension. Knight moves are then 1*BOARD_N_MARGIN_POWER_2 + 2, 1*BOARD_N_MARGIN_POWER_2 - 2, 2*BOARD_N_MARGIN_POWER_2 + 1, ... This further simplifies the "matrix" code. Example: test for end condition if (r1 == r2) && (c1 == c2) --> if (pos == end_pos) with pos being the same as the former (row+2)*BOARD_N_MARGIN_POWER_2 + (col+2).

Parity: Every knight moves is from a black square to white or visa-versa. So to go from pos1 to pos2, code can ascertain before searching begins if the count shall be odd or even. So each recursion call is foo_black() calling foo_white() calling fooblack()... This can make for 2 arrays, one black and one white and offers various simplifications. e.g. no need to check for pos2 attainment in one of the functions. If code does not use a 2-wide padded edge, then the 8x8 board can become two 32-bit integers (black_board, white_board) using only a bit to indicate visitation.

Pre-compute possible visits: Rather than moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 2, c2 + 1, array)); moves = minimum(moves, 1 + minmoves(r1, c1, r2 - 1, c2 - 2, array)); .... Pre-compute the "up-to 8" places for each of the 64-squares that a knight may next jump. E.g. from the corer square, a knight may only jump to 2 locations. This speeds up by not doing worthless -off board jumps and allows for an 8x8 model hinted in the preceding paragraph.

Answer 3

Maybe try combining the two 'if' statements that both end up returning 32764.

Also, you might gain slightly more efficiency making the line ' if((r1==r2)&&(c1==c2))' into an 'else if...' statement and combining it with the statements above. Not too sure what it will do in execution time, but it will shorten the line count a bit.

Another thing might b to reorder the if statement that I mentioned at the beginning of my post. While C does not always have the same execution order between compilers, you might find putting the various items you are testing for in order of least complexity/most common will mean that it uses less time and/or less processing cycles to make a determination if it is indeed going to hit one of those items. If it does not match any, then it would have anyways needed to be checked anyways and that cannot really be reduced.