CODEWITHSUNDEEP
javabacktrackingknights-tour
user3423663
user3423663

Reputation: 1

Knight tour (backtrack)

I am trying to solve Knight's tour problem with 8*8 chessboard. But my backtrack is going in infinite loop. My Logic function is as follows:-

N is 8.

  boolean algo(int x,int y,int no_of_moves,int sol[][]){

        if(no_of_moves==N*N){
            return true;
        }

        int nextx;
        int nexty;
        for(int i=0;i<8;i++){

            nextx=x+move_x[i];
            nexty=y+move_y[i];

            if(is_valid(nextx,nexty)){
                sol[nextx][nexty]=no_of_moves;

                if(algo(nextx,nexty,no_of_moves+1,sol)){
                    return true;
                }
                else
                    sol[nextx][nexty]=-1;

            }
        }
        return false;  
    }

sol [][] stores the moves made by the knight.

the array move_x and move_y stores the values to be added to x and y to get next position of knight.

 int move_x[]={  2, 1, -1, -2, -2, -1,  1,  2 };
    int move_y[]={  1, 2,  2,  1, -1, -2, -2, -1 };

I started by passing x as 0, y as 0, no_of_moves as 1, and all values in sol[][] as -1 except sol[0][0] as 0.

And is_valid() checks if the nextx, and nexty is inside the chessboard and not visited yet.

boolean is_valid(int xnext,int ynext)
    {
        if(xnext>=0 && xnext<N && ynext>=0 && ynext<N && sol[xnext][ynext]==-1)
        { 
            return true;
        }
        else 
        {
            return false; 
        }
    }

Upvotes: 0

Views: 470

Answers (2)

Murilo Perrone
Murilo Perrone

Reputation: 504

I see you are using brute force there, but that isn't enough to solve this problem in reasonable time. Without optimisations, complexity will be O(N^(N*N)) (with N being the board dimension). Thus it may really take an eternity of time to find the first solution. That's why you thought it was on an infinite loop.

The most efficient optimisation is Warnsdorff's rule, which was first published in 1823. It's a kind of simple heuristic rule which allows you to find a solution on the first try (immediately).

Upvotes: 0

NPE
NPE

Reputation: 500227

I don't see anything wrong with the code. I suspect that it doesn't go into an infinite loop, but into one that takes a long time.

See if it works on a 5x5 board (animation).

Upvotes: 0

Related Questions