Given a chess board, find the shortest distance (minimum number of steps) taken by a Knight to reach given destination from given source.
For example,
Input: N = 8 (8 x 8 board), Source = (7, 0) Destination = (0, 7)
Output: Minimum number of steps required is 6
Explanation: The Knight’s movement can be demonstrated in figure below
The idea is to use Breadth First Search (BFS) as it is a Shortest Path problem. Below is the complete algorithm.
1. Create an empty queue and enqueue source cell having
distance 0 from source (itself)
2. do till queue is not empty
a) Pop next unvisited node from queue
b) If the popped node is destination node, return its distance
c) else we mark current node as visited and for each of 8 possible
movements for a knight, we enqueue each valid movement into the
queue with +1 distance (min distance of given node from source
= min distance of parent from source + 1)
A knight can move in 8 possible directions from a given cell as illustrated in below figure –
We can find all the possible locations the Knight can move to from the given location by using the array that stores the relative position of Knight movement from any location. For example, if the current location is (x, y), we can move to (x + row[k], y + col[k]) for 0 <= k <=7 using below array.
row[] = [ 2, 2, -2, -2, 1, 1, -1, -1 ]
col[] = [ -1, 1, 1, -1, 2, -2, 2, -2 ]
So, from position (x, y) Knight’s can move to:
(x + 2, y – 1)
(x + 2, y + 1)
(x – 2, y + 1)
(x – 2, y – 1)
(x + 1, y + 2)
(x + 1, y – 2)
(x – 1, y + 2)
(x – 1, y – 2)
Note that in BFS, all cells having shortest path as 1 are visited first, followed by their adjacent cells having shortest path as 1 + 1 = 2 and so on.. so if we reach any node in BFS, its shortest path = shortest path of parent + 1. So, the first occurrence of the destination cell gives us the result and we can stop our search there. It is not possible that the shortest path exists from some other cell for which we haven’t reached the given node yet. If any such path was possible, we would have already explored it.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include <iostream> #include <map> #include <queue> #include <climits> using namespace std; #define N 8 // Below arrays details all 8 possible movements // for a knight int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 }; int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 }; // Check if (x, y) is valid chess board coordinates // Note that a knight cannot go out of the chessboard bool valid(int x, int y) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } // queue node used in BFS struct Node { // (x, y) represents chess board coordinates // dist represent its minimum distance from the source int x, y, dist; // Node constructor Node(int x, int y, int dist = 0): x(x), y(y), dist(dist) {} // As we are using struct as a key in a std::map, // we need to overload < operator // Alternatively we can use std::pair<int, int> as a key // to store coordinates of the matrix in the map bool operator<(const Node& o) const { return x < o.x || (x == o.x && y < o.y); } }; // Find minimum number of steps taken by the knight // from source to reach destination using BFS int BFS(Node src, Node dest) { // map to check if matrix cell is visited before or not map<Node, bool> visited; // create a queue and enqueue first node queue<Node> q; q.push(src); // run till queue is not empty while (!q.empty()) { // pop front node from queue and process it Node node = q.front(); q.pop(); int x = node.x; int y = node.y; int dist = node.dist; // if destination is reached, return distance if (x == dest.x && y == dest.y) return dist; // Skip if location is visited before if (!visited.count(node)) { // mark current node as visited visited[node] = true; // check for all 8 possible movements for a knight // and enqueue each valid movement into the queue for (int i = 0; i < 8; ++i) { // Get the new valid position of Knight from current // position on chessboard and enqueue it in the // queue with +1 distance int x1 = x + row[i]; int y1 = y + col[i]; if (valid(x1, y1)) q.push({x1, y1, dist + 1}); } } } // return INFINITY if path is not possible return INT_MAX; } // main function int main() { // source coordinates Node src = {0, 7}; // destination coordinates Node dest = {7, 0}; cout << "Minimum number of steps required is " << BFS(src, dest); return 0; } |
Output:
Minimum number of steps required is 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
import java.util.*; // queue node used in BFS class Node { // (x, y) represents chess board coordinates // dist represent its minimum distance from the source int x, y, dist; public Node(int x, int y) { this.x = x; this.y = y; } public Node(int x, int y, int dist) { this.x = x; this.y = y; this.dist = dist; } // As we are using class object as a key in a HashMap // we need to implement hashCode() and equals() // -- below methods are generated by IntelliJ IDEA (Alt + Insert) -- @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Node node = (Node) o; if (x != node.x) return false; if (y != node.y) return false; return dist == node.dist; } @Override public int hashCode() { int result = x; result = 31 * result + y; result = 31 * result + dist; return result; } }; class ChessKnight { // Below arrays details all 8 possible movements // for a knight private static int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 }; private static int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 }; // Check if (x, y) is valid chess board coordinates // Note that a knight cannot go out of the chessboard private static boolean valid(int x, int y, int N) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } // Find minimum number of steps taken by the knight // from source to reach destination using BFS public static int BFS(Node src, Node dest, int N) { // map to check if matrix cell is visited before or not Map<Node, Boolean> visited = new HashMap<>(); // create a queue and enqueue first node Queue<Node> q = new ArrayDeque<>(); q.add(src); // run till queue is not empty while (!q.isEmpty()) { // pop front node from queue and process it Node node = q.poll(); int x = node.x; int y = node.y; int dist = node.dist; // if destination is reached, return distance if (x == dest.x && y == dest.y) return dist; // Skip if location is visited before if (visited.get(node) == null) { // mark current node as visited visited.put(node, true); // check for all 8 possible movements for a knight // and enqueue each valid movement into the queue for (int i = 0; i < 8; ++i) { // Get the new valid position of Knight from current // position on chessboard and enqueue it in the // queue with +1 distance int x1 = x + row[i]; int y1 = y + col[i]; if (valid(x1, y1, N)) q.add(new Node(x1, y1, dist + 1)); } } } // return INFINITY if path is not possible return Integer.MAX_VALUE; } public static void main(String[] args) { int N = 8; // source coordinates Node src = new Node(0, 7); // destination coordinates Node dest = new Node(7, 0); System.out.println("Minimum number of steps required is " + BFS(src, dest, N)); } } |
Output:
Minimum number of steps required is 6
Exercise: Extend the solution to print the paths as well.
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Can someone please explain this bunch
Pratik, thank you for sharing your concerns.
Since we’re using a Node object as a key in our std::map, we need to overload the operator< for Node type. Now map will perform a lexicographical comparison on two Node objects to define their position in the map. i.e. It will compare based on the first element x. If the values of the first elements are equal, it will then compare based on the second element y.
Hope you're clear now.
EDIT: We can also pass a comparison object to std::map or specialize std::less in the std namespace.
Great stuff! There is also a variation of this problem where you calculate the minimum number of moves to get to a position in an infinite coordinate plane using a formula in constant time (there is some hard coding involved for values within 4 spaces of the origin or so. Any plans to attack that one?
Thanks, I have found your website to be very useful… especially the codes are neat and well explained.
great!
“Exercise: Extend the solution to print the paths as well.”
What is the answer?
We can store complete path from source cell to destination in a vector. Please refer below program for similar implementation –
https://www.techiedelight.com/find-shortest-path-source-destination-matrix-satisfies-given-constraints/
Interesting that you kept track of visited/unvisited marks. I had used similar approach of using the closest point approach for moving the knight in the beginning. But as the knight reaches a proximity distance (which is very close to the target), I used a different set of algorithm.
Please look into my solution and let me know what you think:
http://sovitpoudel.com.np/2016/06/03/a-knights-watch/
Thanks!
if I want to solve in o(1) ?