Minimum Knight Moves
You are given an infinite chessboard and a knight that can move in its usual Lshaped pattern. You need to find the minimum number of moves the knight must make to reach the coordinates (x, y)
from the starting position (0, 0)
.
Solution
We can use a breadthfirst search (BFS) to find the shortest path from the starting position to the destination.
The idea is to start from (0, 0)
and iteratively explore the board using the 8 possible knight moves. We keep track of visited positions to avoid redundant work and use a queue to manage the exploration order.
Since the board is symmetric, we can consider only the positive quadrant of the board and mirror the target coordinates into that quadrant. This simplification reduces the search space.
Here’s the code:


This code uses BFS to systematically explore the possible moves and find the minimum number of steps to reach (x, y)
. The additional conditions (nx >= 2 and ny >= 2)
help reduce the search space by limiting exploration to relevant areas near the positive quadrant.
title: Minimum Knight Moves tags: bfs implicitgraph
In an infinite chess board with coordinates from infinity to +infinity, you have a knight at square [0, 0]. A knight has 8 possible moves it can make. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
Problem Definition
Define the Terms
Cardinal direction: The four cardinal directions are north, south, east and west.
Orthogonal direction: The directions that are right angle to each other.
You can move two units only in N,S,E,W
N  NE, NW
S  SE, SW
Every move in two units has two possible jumps up or down, left or right. 8 possible moves.
Define the Interface
Input: integer x and y
Output: integer
Identify Implicit Inputs
 Start from [0,0]
 board size: infinity to +infinity
 8 possible moves from any location
Define the Goal
Return the minimum number of steps needed to move the knight to the square [x, y]
Identify the Constraints
x + y <= 300
Determine the Scope
List assumptions: It is guaranteed the answer exists
Classify the Problem
Minimize: Optimize the number of moves to reach the target location.
We have 8 directions. Try all the possible 8 directions. How do you know which direction you should start exploring? We don’t know which first direction will lead the optimal solution. Do we need to try all possible 8 directions and pick the minimum number of moves?
 Find all possible solutions that lead to the final square.
 Pick the one with the minimal number of moves.
 We need an exhaustive search to find a path to the final location.
 Keep track of the number of moves.
BFS  Prune the visited path, what are the next available options? Break out of the exploration when we reach the final location. We don’t need to find all the possible ways to reach the final location. Whichever BFS traversal leads to the final location, immediately stop traversing and return the number of moves we have made so far.
DFS will also work if we keep track of stack length. Increment the counter by one whenever you change the cardinal direction.
Sometimes the graph is given implicitly, in this problem it is in the form of a grid where the vertices are the cells of the grid and the edges are the adjacent cells.
Time and Space Complexity
Time: O(V+E) Space: O(V+E)
Outline the Solution
Direction offsets: (2, 1), (2, 1), (2, 1), (2, 1), (1, 2), (1, 2), (1, 2), (1, 2)
array of possible positions, increment x by 2, y by 1 …
dx: (2, 2, 2, …) dy: (1, 1, 1, …)
counter is the traversal level at which we are currently
Initialize moves counter to 0
Push [0,0] to a queue
Iterate till we reach the final location (x, y) while true increment the moves counter found = false
for loop for processing all nodes at current level remove the position from the queue if the position == x, y found = true end current_level = queue.size for each of the 8 possible direction add the direction offsets to the current location end end if found break end end
Return the moves  1


You can simulate the movements since the limits are low. Is there a search algorithm applicable to this problem? Since we want the minimum number of moves, we can use Breadth First Search.