Knight's tour- given n moves, in how many options can a knight move from (1,1) to (8,8) in n moves?

Question

I've been trying to improve my recursion skills in C and I came across this question. I've tried to solve it, yet the code doesn't seem to work properly. For example, there are 108 options for the knight to move from (1,1) to (8,8) in 6 moves and in my code the result is completely different. The question asks how many ways are there to move a knight from (1,1) to (8,8) in n moves(n given from the user) in 8x8 board. here's my code:

#include <stdio.h>
#define SIZE 8
//x,y coordinates of the knight.
int knightsTour(int x, int y, int num);
void main() {
int n;
int result;
    do {
        scanf(" %d", &n);
        result = knightsTour(1,1,n);
        printf("%d\n", result);
    } while (n > 0);
}
int knightsTour(int x,int y,int num) {
int result = 0;
int i, j;
if (num == 0) {
    return 0;
}
if (((x > 8) || (y > 8))||((x == 8) && (y == 8))) {
    return 0;
}
for (i = 1; i <= SIZE; i++) {
    for (j = 1; j <= SIZE; j++) {
        if ((i != y) && (j != x) && ((i != y + j) && (j != x + i)) && ((i != y + j) && (j != x - i))
            && ((i != y - j) && (j != x + i)) && ((i != y - j) && (j != x - i))) {
            result += knightsTour(i, j, num - 1) + 1;
        }
    }
}
return result;
}

Answer 1

Your code has several problems:

• You add one to the results unconditionally when you call your recursivev function. You should only count paths that land on h8 after 6 moves, for which you can check only after you have jumped to the new position.
• When you want to find possible moves, it is wasteful to check all squares on the board. You know the rank and file of the knight, so you also know the eight possible moves. You must take care not to jump off the board. It is easier to verify that rank and file are valid at the beginning of the function.

One approach would be the following recursive method:

• Are rank and file valid? If not, return 0.
• Have we reached the desired number of moves? If so, return 1 if the current square is h8, and 0 otherwise.
• Return the sum of the number of valid moves the knight can make with one fewer move for the eight possible moves from the current positions. You don't need to check here, because the validity of a move will be checked at the beginning of the function.

Putting this together:

#include <stdio.h>

#define SIZE 8

int knightsTour(int x, int y, int num)
{
    if (x < 1 || x > SIZE) return 0;
    if (y < 1 || y > SIZE) return 0;

    if (num == 0) return (x == SIZE && y == SIZE);

    return knightsTour(x + 2, y + 1, num - 1)
         + knightsTour(x + 1, y + 2, num - 1)
         + knightsTour(x - 1, y + 2, num - 1)
         + knightsTour(x - 2, y + 1, num - 1)
         + knightsTour(x - 2, y - 1, num - 1)
         + knightsTour(x - 1, y - 2, num - 1)
         + knightsTour(x + 1, y - 2, num - 1)
         + knightsTour(x + 2, y - 1, num - 1);
}

int main(void)
{
    int result = knightsTour(1, 1, 6);

    printf("%d\n", result);
    return 0;
}

This code is straightforward and it determines the 108 possible moves.