Last Updated: 31 Dec, 2020
Minimum steps taken by knight to reach target
Moderate
Asked in companies
You are given a 2D matrix of size N x N which is nothing but a square chessboard. Given the starting and target positions of the knight, you are supposed to return the minimum number of steps required by the knight to reach the target position from the given starting point.
Note :
Following is the possible movements of the knight from a particular position.
Input Format :
The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows.
The first line of each test case contains one integer ‘N’ representing the side of the square chessboard or 2D matrix.
The second line contains two integers ‘SX’ and ‘SY’ representing the starting position of the knight in the chessboard.
The third line contains two integers ‘TX’ and ‘TY’ representing the target position in the chessboard.
Output Format :
For each test case, return the minimum number of steps taken by the knight to reach the target position from the given starting position.
Note :
You do not need to print anything; It has already been taken care of.
Constraints :
1 ≤ T ≤ 50
1 ≤ N ≤ 100
1 ≤ SX,SY,TX,TY ≤ 100
Where ‘T’ is the number of test cases.
‘N’ is the side of the given chessboard or matrix.
‘SX’, ‘SY’, ‘TX’, ‘TY’ denotes the starting and target positions in the given chessboard.
Time Limit: 1 sec
Approaches
Our intuition is to think of all the positions knight can reach from the current position. This problem can be seen as the shortest path in an unweighted graph. Hence, we use BFS to solve this problem.
A knight can move to 8 positions from (x,y).
(x, y) ->
(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)
(x,y) will have an edge to the 8 neighbors defined above.
Steps are as follows :
- Try all 8 possible positions where a Knight can reach from its position.
- If a reachable position is not already visited and is inside the board, we push this state into the queue with a distance of 1 more than its parent state.
- Finally, we return the distance of the target position, when it gets pop out from the queue.
This approach considers the implementation of Breadth-First Search for searching through cells, where each cell contains its coordinate and distance from the starting node.
Take a close look at the positions of the knight and the target and how will it get affected in different cases:
First of all, let’s talk about the non-linear positions where the knight and the target cells are along different rows and columns (i.e. sx != tx & sy != ty). For example if (sx,sy) = (3,3) and (tx,ty) = (6,6) then only 2 steps are required to reach the target, which are: (3,3) -> (4,5) and (3,3) -> (5,4). So, using dynamic programming, minSteps{(3,3) to (6,6)} = 1 + [minSteps((4,5) to (6,6)) or minSteps((5,4) to (6,6))].
Secondly, if the positions are linear which means if the knight and the target cell are along either same row or columns. i.e. either kx = tx or ky = ty. For example (sx,ky) = (2,4) and (tx,ty) = (7,4) then there are in total 4 steps move towards the target, which are: (2,4) -> (4,5) and (2,4) -> (4,3), both these steps are equivalent and (2,4) -> (3,6) and (2,4) -> (3,2), both these steps are equivalent. So, using dynamic programming, minSteps((2,4) to (7,4)) = 1 + min[minSteps((2,4) to (4,5)) , minSteps((2,4) to (3,6))].
Corner Cases will be if either of the Knight or the target cell is at the corner position and [abs(sx-tx) , abs(sy-ty)] = [1,1]. Then the minimum steps to reach the target will be 4.
The steps are as follows:
- Firstly, constitute the solution for corner cases. i.e. when the knight or target is at 4 corners of the board and the difference in their positions are (1,1). The minimum number of moves from source to target is 4. These positions are depicted below:
- To define base cases:
- When the Knight and the target cell are at adjacent squares (along the same row/column), the minimum number of moves required to reach the destination is 3.
- When the Knight and the target cell are at adjacent squares but lie diagonally to each other, the minimum number of moves required to reach the destinations is 2.
- When Knight and the target cell are at positions as depicted in the image, the minimum number of moves required to reach the destination is 1.
- If the Knight and the target cell are in the same position, the minimum number of moves required is 0.
The Dynamic Programming Equation becomes:
- dp[abs(sx – tx)][abs(sy – ty)] = minimum number of steps to reach from knight’s position (sx,sy) to target position (tx,ty).
- dp[abs(sx – tx)][abs(sy – ty)] =dp[abs(sy – ty)][abs(sx – tx)].