CODEWITHSUNDEEP
c++cperformanceexecution-timeknights-tour
Eight
Eight

Reputation: 4284

why two almost same implementation is having a big execution time difference?

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?

Upvotes: 0

Views: 279

Answers (2)

duleshi
duleshi

Reputation: 2004

Your post don't show the difference between your code and and the original one.
Infact, if you look at your code carefully, the only between yours and the right one is such: 

int xMoves[] = {  2, 1, -1, -2, -2, -1,  1,  2 };//{2, 2,  1,  1, -1, -1, -2, -2};  
int yMoves[] = {  1, 2,  2,  1, -1, -2, -2, -1 };//{1, -1, -2, 2, -2, 2, -1,  1};

The order is different. You draw the possible moves on a paper, and you can find that the right one has an anticlockwise order, while yours is totally in disorder.
That must be the reason caused your problem.

Upvotes: 1

fgb
fgb

Reputation: 18569

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.

Upvotes: 6

Related Questions