Minimum Knight Moves

XXX. Minimum Knight Moves to Target

Graph

BFS

Matrix

Problem Statement:

Given coordinates (x, y) on an infinite chessboard, find the minimum number of moves needed for a knight to reach the target from origin (0, 0).

• Knight moves in L-shape pattern
• Board is infinite in all directions
• Must find shortest path to target

Algorithm:

1. **Key Optimizations**:
   • Use symmetry by taking absolute values
   • Limit search space to quadrant near target
   • Allow slight negative values for optimal paths
2. **BFS Approach**:
   • Use queue for level-order traversal
   • Track visited positions to avoid cycles
   • Count moves at each level

Complexity:

Time Complexity: O(max(|x|, |y|)²), bounded by search area
Space Complexity: O(max(|x|, |y|)²) for visited set

Implementation:

Java Solution:

class Solution {
    // Eight possible knight moves
    private final int[][] dirs = new int[][] {
        {2,1}, {1,2}, {-1,2}, {-2,1},
        {-2,-1}, {-1,-2}, {1,-2}, {2,-1}
    };
    
    public int minKnightMoves(int x, int y) {
        // Use symmetry to reduce to first quadrant
        x = Math.abs(x);
        y = Math.abs(y);
        
        Queue queue = new LinkedList<>();
        queue.add(new int[] {0, 0});                 // Start from origin
        
        Set visited = new HashSet<>();       // Track visited positions
        visited.add("0,0");
        
        int moves = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.remove();
                int currX = curr[0], currY = curr[1];
                
                if (currX == x && currY == y)        // Found target
                    return moves;
                
                // Try all possible moves
                for (int[] d : dirs) {
                    int newX = currX + d[0];
                    int newY = currY + d[1];
                    String pos = newX + "," + newY;
                    // Allow slight negative values for optimal paths
                    if (!visited.contains(pos) && newX >= -1 && newY >= -1) {
                        queue.add(new int[] {newX, newY});
                        visited.add(pos);
                    }
                }
            }
            moves++;
        }
        return -1;
    }
}
                

Python Solution:

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        # Eight possible knight moves
        dirs = [(2,1), (1,2), (-1,2), (-2,1),
                (-2,-1), (-1,-2), (1,-2), (2,-1)]
        
        # Use symmetry to reduce to first quadrant
        x, y = abs(x), abs(y)
        
        queue = deque([(0, 0)])                    # Start from origin
        visited = {(0, 0)}                         # Track visited positions
        moves = 0
        
        while queue:
            for _ in range(len(queue)):
                curr_x, curr_y = queue.popleft()
                
                if (curr_x, curr_y) == (x, y):     # Found target
                    return moves
                
                # Try all possible moves
                for dx, dy in dirs:
                    new_x = curr_x + dx
                    new_y = curr_y + dy
                    # Allow slight negative values for optimal paths
                    if (new_x, new_y) not in visited and new_x >= -1 and new_y >= -1:
                        queue.append((new_x, new_y))
                        visited.add((new_x, new_y))
            moves += 1
            
        return -1
                

C++ Solution:

class Solution {
private:
    // Eight possible knight moves
    vector> dirs = {
        {2,1}, {1,2}, {-1,2}, {-2,1},
        {-2,-1}, {-1,-2}, {1,-2}, {2,-1}
    };
    
public:
    int minKnightMoves(int x, int y) {
        // Use symmetry to reduce to first quadrant
        x = abs(x);
        y = abs(y);
        
        queue> q;
        q.push({0, 0});                           // Start from origin
        
        set> visited;              // Track visited positions
        visited.insert({0, 0});
        
        int moves = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto [curr_x, curr_y] = q.front();
                q.pop();
                
                if (curr_x == x && curr_y == y)    // Found target
                    return moves;
                
                // Try all possible moves
                for (auto [dx, dy] : dirs) {
                    int new_x = curr_x + dx;
                    int new_y = curr_y + dy;
                    // Allow slight negative values for optimal paths
                    if (!visited.count({new_x, new_y}) && new_x >= -1 && new_y >= -1) {
                        q.push({new_x, new_y});
                        visited.insert({new_x, new_y});
                    }
                }
            }
            moves++;
        }
        return -1;
    }
};
                

Explanation:

• **Key Optimizations**:
  • Using absolute values reduces search space by 75%
  • Allowing -1 coordinates enables optimal paths near origin
  • Using BFS guarantees shortest path
• **Position Tracking**:
  • Java: String encoding for visited positions
  • Python: Tuple coordinates in set
  • C++: Pair of coordinates in set
• **Implementation Notes**:
  • Level-order BFS for move counting
  • Early return upon finding target
  • Boundary checks prevent infinite exploration