Minimum Knight Moves

You are given an infinite chessboard and a knight that can move in its usual L-shaped 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 breadth-first 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:

 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
from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        # Convert x and y to the positive quadrant
        x, y = abs(x), abs(y)

        # Define all 8 possible knight moves
        moves = [(2, 1), (1, 2), (2, -1), (-1, 2), (-2, 1), (1, -2), (-2, -1), (-1, -2)]

        # Use a queue for BFS
        queue = deque([(0, 0, 0)]) # (x, y, steps)

        # Use a set to keep track of visited positions
        visited = set([(0, 0)])

        # Start BFS
        while queue:
            cx, cy, steps = queue.popleft()

            # Check if we've reached the target
            if (cx, cy) == (x, y):
                return steps

            # Explore next positions
            for dx, dy in moves:
                nx, ny = cx + dx, cy + dy
                # Add conditions to reduce unnecessary exploration
                if (nx, ny) not in visited and nx >= -2 and ny >= -2:
                    visited.add((nx, ny))
                    queue.append((nx, ny, steps + 1))

        # The answer always exists, so this part will not be reached
        return -1

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 implicit-graph

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

 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
# @param {Integer} x
# @param {Integer} y
# @return {Integer}
def min_knight_moves(x, y)
  queue = [[0,0]]
  moves = 0
  set = Set.new
    
  offsets =  [[2, 1], [2, -1], [-2, 1], [-2, -1],
  [1, 2], [-1, 2], [1, -2], [-1, -2]]
  while true
    moves += 1
    found = false
          
    size = queue.size
    size.times do
      current = queue.shift    
      set.add(current)
          
      offsets.each do |offset|
        temp = current
            
        temp[0] = current[0] + offset[0]
        temp[1] = current[1] + offset[1]  
            
        if !set.include?(temp)
          if temp[0] == x and temp[1] == y 
            found = true

            return moves  
          end
        end 
        queue << temp
      end
    end
      
    if found
      break
    end
  end
   
  return moves
end

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.