Minimum Knight Moves
Asked at Databricks, Uber
Problem
Find the minimum number of moves for a chess knight to reach a target square on an infinite 2D board from (0, 0). Use BFS since all moves have equal cost. The infinite board means you cannot precompute a fixed grid.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Key insight: BFS on the infinite board. A knight has 8 possible moves: (+2,+1), (+2,-1), (-2,+1), (-2,-1), (+1,+2), (+1,-2), (-1,+2), (-1,-2). BFS guarantees the shortest path.
You cannot create an infinite grid. Use a hash set to store visited positions as tuples (x, y). This way, the space is proportional to the number of visited cells, not the board size.
Visual walkthrough for target (5, 5):
BFS from (0,0):
- Level 0: (0,0)
- Level 1: (2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)
- Level 2: explore each... eventually reach (5,5) at level 4
Knight path: (0,0) -> (1,2) -> (2,4) -> (4,5) -> (5,3) -> ...
Optimal: 4 moves for (5,5)
Optimization: the target is at most 300 away (per constraints). You only need to explore positions within a bounded region. Since a knight moves at most 2 squares per move, the BFS frontier grows roughly as a diamond shape. Prune positions that are too far from the target.
Symmetry optimization: the board is symmetric. The minimum moves to (x, y) is the same as to (|x|, |y|), (y, x), (-x, y), etc. You can always work in the first quadrant. Map the target to (|x|, |y|) first.
Edge cases: target (0, 0) requires 0 moves. Target (1, 0) or (0, 1) requires 3 moves (a knight cannot reach an adjacent square in fewer). Target (1, 1) also requires 2 moves.
Optimal Approach
BFS from (0, 0) toward (targetX, targetY). Use a hash set for visited positions.
- Start with queue = [(0, 0, 0)] (x, y, steps). Mark (0, 0) as visited.
- While queue is not empty:
- Dequeue (x, y, steps).
- If (x, y) == (targetX, targetY), return steps.
- For each of the 8 knight moves, compute new position (nx, ny).
- If (nx, ny) not visited, add to queue and mark visited.
- Return -1 (should never reach here for valid targets).
Optimization: use symmetry to map target to first quadrant. Only explore positions where |x| <= max+2 and |y| <= max+2.
Time: O(max^2) where max = max(|targetX|, |targetY|). Each cell is visited once. Space: O(max^2) for the visited set.
What Trips People Up in Real Interviews
Trying to use a fixed-size grid instead of a hash set. The board is infinite, so you cannot allocate a 2D array. Use a HashSet or Set with coordinate tuples as keys.
Forgetting that the board is infinite. You cannot precompute all distances. BFS explores outward from (0,0) until it reaches the target, expanding only the cells it visits.
Not pruning unreachable cells. The BFS will explore far beyond the target if you don't bound the search. Use symmetry (work in first quadrant) and limit exploration to a reasonable range.
Using A* or heuristic search when BFS is simpler. The knight has uniform move cost (each move costs 1), so BFS guarantees the shortest path. A* is overkill unless the board is extremely large.
Handling negative coordinates incorrectly. The board extends to negative coordinates. A knight at (0,0) can move to (-1,-2). Your hash set must support negative keys — tuples work naturally.
Solution Code
from collections import deque
def minKnightMoves(x, y):
if x == 0 and y == 0:
return 0
moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
queue = deque([(0, 0, 0)])
visited = {(0, 0)}
while queue:
cx, cy, dist = queue.popleft()
for dx, dy in moves:
nx, ny = cx + dx, cy + dy
if (nx, ny) == (x, y):
return dist + 1
if (nx, ny) not in visited:
visited.add((nx, ny))
queue.append((nx, ny, dist + 1))Frequently Asked Questions
What is the Minimum Knight Moves problem?
Find the minimum number of moves for a chess knight to reach a target square on an infinite 2D board from (0, 0). Use BFS since all moves have equal cost. The infinite board means you cannot precompute a fixed grid.
How do you solve Minimum Knight Moves?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Knight Moves?
Minimum Knight Moves is asked at Databricks, Uber. It is a medium difficulty problem.
What are common mistakes on Minimum Knight Moves?
- Trying to use a fixed-size grid instead of a `hash set`. The board is infinite, so you cannot allocate a 2D array. Use a `HashSet` or `Set` with coordinate tuples as keys.
- Forgetting that the board is infinite. You cannot precompute all distances. BFS explores outward from (0,0) until it reaches the target, expanding only the cells it visits.
- Not pruning unreachable cells. The BFS will explore far beyond the target if you don't bound the search. Use symmetry (work in first quadrant) and limit exploration to a reasonable range.
- Using A* or heuristic search when BFS is simpler. The knight has uniform move cost (each move costs 1), so BFS guarantees the shortest path. A* is overkill unless the board is extremely large.
- Handling negative coordinates incorrectly. The board extends to negative coordinates. A knight at (0,0) can move to (-1,-2). Your `hash set` must support negative keys — tuples work naturally.