# [SOLVED] why two almost same implementation is having a big execution time difference?

## Issue

I am trying to solve the Knight Tour problem using bactracking as given on this site.

Implementation given on the site takes about 0.49 seconds on ideone.

``````int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N],
int yMove[N])
{
int k, next_x, next_y;
if (movei == N*N)
return true;

/* Try all next moves from the current coordinate x, y */
for (k = 0; k < 8; k++)
{
next_x = x + xMove[k];
next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol))
{
sol[next_x][next_y] = movei;
if (solveKTUtil(next_x, next_y, movei+1, sol, xMove, yMove) == true)
return true;
else
sol[next_x][next_y] = -1;// backtracking
}
}

return false;
}
``````

while one implemented by me which is almost same is showing time limit exceeded(more than 5 seconds) on ideone.

``````int generateMoves(int x, int y, int moveNum, int soln[][N], int xMoves[], int yMoves[])//making move number 'moveNum' from x and y.
{
if(moveNum == N*N){
return 1;
}
else{
int i, nextX, nextY;
for(i=0; i<8; ++i){
nextX = x + xMoves[i];
nextY = y + yMoves[i];

if(isSafe(nextX, nextY, soln)){
soln[nextX][nextY] = moveNum;
if( generateMoves(nextX, nextY, moveNum+1, soln, xMoves, yMoves) ){
return 1;
}
else{
soln[nextX][nextY] = -1;
}
}
}
return 0;
}
}
``````

what is executing for so long in my code?

## Solution

Changing xMoves/yMoves seems to work: ideone. It could just be the search order causing it to find a solution earlier.

There are too many possible 63, 62, 61 etc length tours that can’t reach the final remaining squares. A brute-force search would have to go through all of them in the worst-case. The algorithm that worked just got lucky by trying a sequence of moves that led to a solution early.