Code knight's tour using backtracking is not showing any output

Question

This code is not giving any output. It should output a matrix of 8X8 size.

#include <iostream>
#define N 8
using namespace std;

This function prints the matrix:

void print(int arr[][N]){
    int i, j;
    for (i = 0; i < N; i++){
        for (j = 0; j < N; j++)
            cout<<arr[i][j]<<" ";
    cout<<endl;
    }
}

This function checks limits of x and y and whether knight already visited that place or not.

bool safe(int x, int y, int arr[][N]){
    if(x>=0 && y>=0 && x<N && y<N && arr[x][y] == 0){
        return true;
    }
    return false;
}

This function do most of the things:

bool solveKT(int x, int y, int movei, int arr[][N], int xmove[], int ymove[] ){
    if(movei == (N*N)+1){
        return true;
    }

    for(int k=0 ; k<8 ; k++){
        int nextx = x + xmove[k];
        int nexty = y + ymove[k];

        if(safe(nextx, nexty, arr) == true){
            arr[nextx][nexty] = movei;
            if(solveKT(nextx, nexty, movei+1, arr, xmove, ymove) == true){
                return true;
            }
            arr[nextx][nexty] = 0; // backtrack
        }
    }
    return false;
}

This is just a driver function:

int main(){

    int arr[N][N]={0};
    int xmove[] = {1, 1,2, 2,-1,-1,-2,-2};
    int ymove[] = {2,-2,1,-1, 2,-2, 1,-1};
    arr[0][0] = 1;
    int movei = 2;
    bool a = solveKT(0, 0, movei, arr, xmove, ymove);
    if(a == true){
        print(arr);
    }
    else
        cout<<"no solution";

}

Answer 1

Replacing the following code:

if(movei == (N*N)+1){
    return true;
}

...with a hardcoded value...

if(movei == 62){
    return true;
}

...gave me a good result after 0.1 seconds. (A field with only three "zeroes" remaining.) So your overall algorithm works.

Hint for better looks of the output:

#include <iomanip>

cout << setw(3) << arr[i][j];

Bumping the 62 to 63 increased the runtime to 2.5 seconds, with only two zeroes on the field. Still waiting for the 64 run to finish.

Edit: Half an hour later, the 64 run still didn't finish. Point made.

Your problem is not the program, your problem is the algorithm. It has to go through trillions of moves to get a result. The complexity is killing you, as I guessed.