CODEWITHSUNDEEP
algorithmgraph-algorithmknights-tour
user1532587
user1532587

Reputation: 1023

Knight's tour, count steps that takes to go from A to B

A knight is located in position (a,b) and needs to take the king located in (c,d). How can I:

A: Visualize the tour

B: Calculate the min steps needed to go from (a,b) to (c,d)

The implementation I've found are basically a sequence of moves of a knight on a chessboard such that the knight visits every square only once, but I want to be more specific and step into a specific location.

What kind of algorithm or strategy should I look for?

I'm thinking in using python

Upvotes: 0

Views: 752

Answers (2)

Prashant Negi
Prashant Negi

Reputation: 348

The best way to find an accurate solution to the Knight's tour problem is using Backtracking algorithm. Look at all the possible steps you can choose from (a,b) choose the first one and move ahead till you find a dead end.

If a dead end happens move one step back and explore other options.

This is an example of DFS (Depth First Searh)

Upvotes: 0

Rishi
Rishi

Reputation: 1183

You could use BFS algorithm for achieving the above. Just cache the position visited so that you don't visit a position multiple times. Now whenever you visit the destination that would be the minimum number of steps taken as at every complete iteration you are exploring just 1 degree of separation.

Assuming N X M chessboard with Point representing each block on chess board and applying BFS on it.

class Point{
        int x;
        int y;
        int dist;
}

public int knight(int N, int M, int x1, int y1, int x2, int y2) {
           Point source = new Point(x1, y1);
           Point destination = new Point(x2, y2);

           Queue<Point> q = new LinkedList<>();
           q.add(source);
           Set<Point> hset = new HashSet<>();
           hset.add(source);
           int[][] dir = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};
           while(!q.isEmpty()){
               Point p = q.poll();

               if(p.equals(destination)){
                   return p.dist;
               }

               for(int[] d : dir){

                   int row = p.x + d[0];
                   int col = p.y + d[1];
                   Point temp = new Point(row, col);
                   if(row <= 0 || col <= 0 || row > N || col > M || hset.contains(temp)){
                       continue;
                   }
                   temp.dist = p.dist + 1;

                   q.add(temp);
                   hset.add(temp);

               }

           }

           return -1;   //unreachable point from source position
}

Visualizing a tour would be much simpler, just use ArrayList, etc. for storing the path traversed. Another approach could be to use Dijkstra's algorithm for the above.

Upvotes: 1

Related Questions