Minimum Knight Moves - Leetcode Solution

The Minimum Knight Moves problem on Leetcode asks us to find the minimum number of steps a chess knight needs to take in order to move from the origin (0,0) to a given target location (x,y) on an 8x8 chessboard. The knight can move two squares in one direction and one square in the other, either vertically or horizontally.

To solve this problem, we can use a breadth-first search algorithm. We will start from the origin, and we will enqueue all possible moves that the knight can make from the current position. We will keep track of the number of steps taken to reach that position and mark it as visited to avoid revisiting it again. We will continue this process until we reach the target position or visit all possible positions on the board.

Here is the Python code for the Minimum Knight Moves problem on Leetcode:

from collections import deque

def minKnightMoves(x: int, y: int) -> int:
    # Define the possible moves of a knight
    moves = [(-2,-1),(-2,1),(2,-1),(2,1),(-1,-2),(-1,2),(1,-2),(1,2)]
    # Initialize the queue with the origin and mark it as visited
    queue = deque([(0,0,0)])
    visited = {(0,0)}
    while queue:
        # Dequeue the next position and number of steps taken to reach that position
        curr_x, curr_y, curr_steps = queue.popleft()
        if curr_x == x and curr_y == y:
            # We have reached the target position, return the number of steps taken
            return curr_steps
        # Enqueue all possible moves
        for dx, dy in moves:
            next_x, next_y = curr_x + dx, curr_y + dy
            if (next_x,next_y) not in visited and -2 <= next_x <= x+2 and -2 <= next_y <= y+2:
                # Add the next position and number of steps taken to reach that position to the queue
                queue.append((next_x, next_y, curr_steps+1))
                visited.add((next_x,next_y))

In this solution, we use a set called "visited" to keep track of the positions that have been visited. We also add an extra border of two squares on each side of the board to handle edge cases where the target position is at the edge of the board or outside the board.

The time complexity of this solution is O(xy), where x and y are the coordinates of the target position. The space complexity is also O(xy) to store the visited positions.

1