Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez

No es el mas efectivo pero es trabajo honesto :V

import math

MOVEMENTS = [
    (2, 1), (1, 2), (-2, 1), (-1, 2),
    (2, -1), (1, -2), (-2, -1), (-1, -2)
]


def distance_between_points(x1, y1, x2, y2):
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)


def move_point(x: int, y: int, search_point: tuple, previous_point, previous_distance=0):
    list_possible_moves = []
    for movement_index in range(0, len(MOVEMENTS)):
        next_x = x + MOVEMENTS[movement_index][0]
        next_y = y + MOVEMENTS[movement_index][1]
        distance = distance_between_points(next_x, next_y, search_point[0], search_point[1])
        if distance == 0:
            return None
        if (next_x >= search_point[0] and next_y >= search_point[1]) \
                or (distance > distance_between_points(0, 0, search_point[0], search_point[1])):
            continue

        list_possible_moves.append([next_x, next_y, previous_distance + distance, previous_point + [(next_x, next_y)]])
    list_possible_moves.sort(key=lambda x: x[2])
    return list_possible_moves


def horse_steps(x, y):
    initial = [[0, 0]]
    jumps = 1
    while jumps < 1000:
        jumps = jumps + 1
        next_step = []
        for step in initial:
            response = move_point(x=step[0], y=step[1], search_point=(x, y), previous_point=[(step[0], step[1])])
            if response is None:
                return jumps
            next_step = next_step + response
            if next_step is None:
                print('No more steps')
                break
            initial = next_step


if __name__ == '__main__':
    assert horse_steps(2, 1) == 2
    assert horse_steps(5, 5) == 5
    assert horse_steps(5, 0) == 4

código en Python: `from queue import Queue` `from typing import List` `class Solution:` ` def minimum_knight_moves(self, target: List[int]) -> int:` ` # The knight moves in 8 possible directions` ` directions = [` ` (2, 1), (2, -1), (-2, 1), (-2, -1),` ` (1, 2), (1, -2), (-1, 2), (-1, -2)` ` ]` ` queue = Queue()` ` queue.put((0, 0, 0)) # (current_x, current_y, step_count)` ` visited_positions = set()` ` visited_positions.add((0, 0))` ` target_x, target_y = abs(target[0]), abs(target[1])` ` # BFS algorithm` ` while not queue.empty():` ` # Dequeue the next position and step count to be processed` ` current_x, current_y, current_steps = queue.get()` ` # Check if we've reached the target position` ` if current_x == target_x and current_y == target_y:` ` return current_steps` ` # Explore all possible knight moves` ` for dx, dy in directions:` ` new_x = current_x + dx` ` new_y = current_y + dy` ` new_position = (abs(new_x), abs(new_y))` ` # Check if the new position has been visited` ` if new_position not in visited_positions:` ` visited_positions.add(new_position)` ` queue.put((new_x, new_y, current_steps + 1))` `# Example usage:` `solution = Solution()` `print(solution.minimum_knight_moves([2, 1])) # Output: 1` `print(solution.minimum_knight_moves([5, 5])) # Output: 4`

Esta es mi solución en java, no estoy seguro de si es la mas eficiente (ya que para cada nivel calcula todas las nuevas posiciones posibles posibles) pero funciona, ¿alguna recomendación? ```js public class MinimumKnightsMoves { public static void main(String[] args) { System.out.println("Welcome to Minimum knights moves!"); System.out.println("in here you can calculate the minimum moves a chess knight needs to move from x,y point to another coordinates in an infinite chess board."); System.out.print("please insert the x coordinate for the initial position: "); final int startX = scanner.nextInt(); System.out.print("please insert the y coordinate for the initial position: "); final int startY = scanner.nextInt(); System.out.println("now you need to insert the destination coordinates..."); System.out.print("insert the x destination coordinate: "); final int destinationX = scanner.nextInt(); System.out.print("insert the y destination coordinate: "); final int destinationY = scanner.nextInt(); System.out.printf("the minimum moves to move from [%d,%d] to [%d,%d] are: [%d]", startX, startY, destinationX, destinationY, calculateMoves(startX, startY, destinationX, destinationY)); } private static int calculateMoves(int startX, int startY, int destinationX, int destinationY) { int moves = 0; if(startX == destinationX && startY == destinationY){ return moves; } Queue<int[]> movements = getPossibleMovementsForKnight(startX, startY); while(!movements.isEmpty()){ moves++; Queue<int[]> newMovements = new LinkedList<>(); while(!movements.isEmpty()) { int[] actualMove = movements.poll(); if (actualMove[0] == destinationX && actualMove[1] == destinationY) { return moves; } newMovements.addAll(getPossibleMovementsForKnight(actualMove[0], actualMove[1])); } movements.addAll(newMovements); } return moves; } private static Queue<int[]> getPossibleMovementsForKnight(int startX, int startY) { System.out.printf("Possible movements for knight at [%d,%d] are: \n", startX, startY); Queue<int[]> moves = new LinkedList<>(); moves.add(new int[] {startX + 2, startY + 1}); System.out.printf("\t [%d,%d]\n", startX + 2, startY + 1); moves.add(new int[] {startX + 1, startY + 2}); System.out.printf("\t [%d,%d]\n", startX + 1, startY + 2); moves.add(new int[] {startX - 2, startY + 1}); System.out.printf("\t [%d,%d]\n", startX - 2, startY + 1); moves.add(new int[] {startX - 1, startY + 2}); System.out.printf("\t [%d,%d]\n", startX - 1, startY + 2); moves.add(new int[] {startX + 2, startY - 1}); System.out.printf("\t [%d,%d]\n", startX + 2, startY - 1); moves.add(new int[] {startX + 1, startY - 2}); System.out.printf("\t [%d,%d]\n", startX + 1, startY - 2); moves.add(new int[] {startX - 2, startY - 1}); System.out.printf("\t [%d,%d]\n", startX - 2, startY - 1); moves.add(new int[] {startX - 1, startY - 2}); System.out.printf("\t [%d,%d]\n", startX - 1, startY - 2); return moves; } } ```