Why is the following Code for "A knight's tour" not working properly?

Question

I am using following code in Codeblocks IDE in C, trying to solve the Knight's tour problem using recursion and backtracking. But the thing is it goes on forever and doesn't give any output, though I think it is not a case of Infinite recursion.

#include <stdio.h>
#include <conio.h>
int board[8][8]= {{0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0}};
int i = 1;
int next(int a, int b);
int main()
{
    int  j, k;
    next(0,0);
    for(k = 0; k < 64; k++)
    {
        printf(" %d ", board[k/8][k%8]);
        if((i+1)%8==0)
            printf("\n");
    }
}
int next(int a, int b)
{
    if(i==64)
    {
        board[a][b]=64;
        return 1;
    }
    if((a<0||a>7||b<0||b>7))
        return 0;
    if(board[a][b]!=0)
        return 0;
        printf(" %d %d ", a, b);
         //getch();
    board[a][b]= i;
    if(next(a+2, b+1))
    {
        i++;
        return 1;
    }
    if(next(a+1, b+2))
    {
        i++;
        return 1;
    }
    if(next(a-1, b+2))
    {
        i++;
        return 1;
    }
    if(next(a+2, b-1))
    {
        i++;
        return 1;
    }
    if(next(a-2, b-1))
    {
        i++;
        return 1;
    }
    if(next(a-1, b-2))
    {
        i++;
        return 1;
    }
    if(next(a+1, b-2))
    {
        i++;
        return 1;
    }
    if(next(a-2, b+1))
    {
        i++;
        return 1;
    }
    board[a][b]=0;
    return 0;
}

Answer 1

Your main problem is that you use a global variable to keep track of the length of your tour and therefore the depth of your recursion. You only ever increment this variable.

The length of the path should be a variable for each recursive call and therefore should be local to the next function.

(By the way, i is a horrible name for a global variable. This becomes clear when you make it local: The loop to print the board is over k, but when you check whether to print a newline, you test i. Ouch!)

The test whether the board is full can happen in two ways: Check that the depth is 64 as first thing and just return; don't assign a value. (Even more so, because you haven't ensured that a and b are valid board coordinates.) The 64th jump can be illegal: A path that visits 64 squares has a length of 63, so the 64th jump just indicates that the board is full.

Another way is to check thet i + 1 is 64 after checking that the square is valid. This is equivalent to the first method and saves one call.

With these changes, your program becomes:

#include <stdio.h>

#define N 8
#define NN (N*N)

int board[N][N]= {{0}};

int next(int a, int b, int i);

int main()
{
    int k;

    if (next(0, 0, 0)) {
        for(k = 0; k < NN; k++) {
            if(k && k % N == 0) puts("");
            printf(" %2d", board[k / N][k % N]);
        }
        puts("");
    } else {
        puts("No solution.");
    }

    return 0;
}

int next(int a, int b, int i)
{
    if (a < 0 || a >= N) return 0;
    if (b < 0 || b >= N) return 0;
    if (board[a][b] != 0) return 0;

    i++;
    board[a][b] = i;
    if (i == NN) return 1;

    if (next(a + 2, b + 1, i)) return 1;
    if (next(a + 1, b + 2, i)) return 1;
    if (next(a - 1, b + 2, i)) return 1;
    if (next(a + 2, b - 1, i)) return 1;
    if (next(a - 2, b - 1, i)) return 1;
    if (next(a - 1, b - 2, i)) return 1;
    if (next(a + 1, b - 2, i)) return 1;
    if (next(a - 2, b + 1, i)) return 1;

    board[a][b] = 0;
    return 0;
}

(Pro tip: Test with N == 6 first; Brute-forcing an 8×8 board takes some time, around three minutes on my machine. The 4×4 doesn't have a solution.)