Last Updated: 20 Aug, 2021
Minimum Knight Moves
Hard
Asked in companies
You are given an infinite chessboard (ie: the x-coordinates and y-coordinates can be anything between -infinity to +infinity).
You have a knight placed at coordinates ‘(0, 0)’. Find the minimum number of steps needed to move the knight to ‘(X, Y)’.
The knight has 8 possible moves, each move is two units in a cardinal direction, then one unit in an orthogonal direction.
For example :
As depicted in the photo below, the knight currently at (0, 0) can move to any of the 8 positions: (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2).
Example :
If X = 1 and Y = -1, then we need to find out the minimum number of steps to move the knight from (0, 0) to (1, -1).
We need at least 2 steps to move the knight to the desired position.
First move: (0, 0) -> (2, 1)
Second move: (2,1) -> (1, -1)
Here we can see that there are many ways, but we need at least 2 steps. Therefore we will return the value 2.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first and only line of each test case contains two integers ‘X’ and ‘Y’, denoting the x-coordinate and y-coordinate of the final position of the knight.
Output Format :
For each test case, print the minimum number of steps needed.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
-100 <= X, Y <= 100
Time limit: 1 sec
Approaches
There is symmetry because of how the knight moves, this leads us to the conclusion that the steps required to reach (x, y), (-x, y), (y, -x) and (-x, -y) are the same. We can narrow down our search space to just the first quadrant (ie: the final target position now becomes (abs(x), abs(y)).
One of the most intuitive ways to solve this is by using breadth-first search (bfs). We can simulate the moves, simply start by pushing position (0, 0) into a bfs-queue. Also maintain a hash-map to store the visited positions on the chessboard as this hash-map will store the minimum moves to reach that particular position. Similar to the standard bfs approach, start exploring the next positions that can be reached and push them into the bfs-queue if they are still unexplored. Finally when we reach the target position return the value of minimum moves.
Important: Are you getting TLE even after doing everything right? Probably you are visiting many unwanted coordinates causing increased execution time. Think of how can you prune the search?
If we are going 2 units beyond the x-coordinate/ y-coordinate then we no longer need to search beyond that, surely a shorter path will exist in some other way. So don't push coordinates into bfs-queue if they are violating this.
The steps are as follows :
- Take the absolute value of x-coordinate and y-coordinate to narrow down the search to the 1st quadrant.
- Initialize queue for the bfs-traversal, and also declare a container vis to store the positions already visited.
- Declare an array “moves” so that you can easily stimulate and check for the next positions.
- Push (0, 0) into q and set the mark (0, 0) as visited.
- Apply standard bfs, run the while loop till the q is non-empty or the target position is not reached.
- Each time, push the elements that will be visited in the next move into q and also mark them as visited in vis.
- Remember: you need to apply pruning to avoid visiting the unwanted coordinates to save the run-time.
- Finally, return the minimum steps to reach the target position.
There is symmetry because of how the knight moves, this leads us to the conclusion that the steps required to reach (x, y), (-x, y), (y, -x) and (-x, -y) are the same. We can narrow down our search space to just the first quadrant (ie: the final target position now becomes (abs(x), abs(y)).
The depth-first search algorithm prioritizes depth over breadth during the exploration process. How does this help us?
We can start from the target position (X, Y) and move backwards to reach origin (0, 0) and we are sure that this now lies in the first quadrant for sure due to symmetry. Instead of exploring all the knight moves, we can just consider the 2 moves that will help us to reach the origin, the first move is decreasing the current x-coordinate by 2 units and y-coordinate by 1 unit, and the second move is decreasing the x-coordinate by 1 unit and y-coordinate by 2 units, (Keep in mind to use the symmetry to our advantage in each step, ie: if the target position was (0,100) then a single step will obviously move us to the second quadrant, but using the logic of symmetry we can again just continue our path considering only the absolute values of x-coordinates and y-coordinates to stay in the first quadrant).
We should terminate and return the value if we reach the origin (0, 0).
We should also terminate our search if we reach (1, 1) (0, 2), (2, 0) and add 2 to the count of steps. This is because it is not possible to reach origin from just the 2 moves we are considering if we are currently at any of the 3 mentioned positions, hence we are handling the case separately (try referring to sample input 1 for better clarification).
The steps are as follows :
- Initialize a hash-map to store the positions already visited.
- Call the dfs function passing the absolute values of x-coordinate and y-coordinate of the target position.
- Base condition to end the dfs is when we reach (0, 0), (1, 1), (0, 2), (2, 0).
- Call the dfs function recursively for absolute values of (curX - 2, curY - 1) and (curX - 1, curY - 2). The steps to reach (curX, curY) is the minimum of the value returned by above 2 recursive calls plus 1.
- Finally, return the minimum steps to reach the target position.
Answer for few values in the first quadrant is given below, Now try to figure out the pattern:
It is intuitive that there will be a symmetry about the y = x diagonal, and the above photo confirms it. For the given target position we can consider the absolute values of the coordinates due to symmetry across all 4 quadrants and we can also swap X and Y if X > Y (because of symmetry across the diagonal).
Now try looking for the pattern about Y = 2 * X in the vertical direction, even now if you are not able to figure out the pattern refer to the image below showing the patterns in the first half of the first quadrant.
The steps are as follows :
- Take absolute values of x-coordinate and y-coordinate of target position, and swap them if X > Y.
- Based on the patterns found:
- Handle border cases for (0, 1) and (1, 1) separately.
- If Y > =2*X (all the squares above bold line in blue colour), return (Y + 1) / 2 + (Y / 2 - X) % 2
- Else, return (X + Y) / 3 + (X + Y) % 3