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

Clase 23 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Qué es el problema "Knight's Move" y cómo se resuelve?

El problema "Knight's Move" se centra en determinar el número mínimo de saltos que un caballo de ajedrez necesita para moverse de una posición inicial a una de destino en un tablero de ajedrez infinito. Dado que el caballo tiene un modo particular de movimiento, entender cómo se mueve es clave para resolver este desafío.

¿Cómo se mueve el caballo en ajedrez?

El caballo tiene un movimiento único: puede ir dos casillas en una dirección y una casilla en una dirección perpendicular, formando una "L". Las ocho posiciones posibles a las que un caballo puede moverse desde una casilla podrían representarse como:

(+2, +1), (+2, -1)
(-2, +1), (-2, -1)
(+1, +2), (+1, -2)
(-1, +2), (-1, -2)

¿Cómo abordamos este problema?

Este problema puede ser tratado como un grafo donde cada casilla representa un "nodo" con conexiones a otras casillas alcanzables según el movimiento del caballo. El objetivo es determinar el número mínimo de saltos (pasos) para llegar a la posición deseada.

¿Qué es BFS y por qué es relevante aquí?

BFS, o búsqueda en anchura, es un algoritmo utilizado para explorar nodos y sus vecinos por niveles. En el contexto del problema, podemos usar BFS para asegurar que encontramos el camino más corto (mínimo número de saltos) debido a su naturaleza de explorar nodos más cercanos antes que más lejanos.

A continuación se presenta un seudocódigo simplificado de cómo podríamos implementar BFS para resolver el problema:

from collections import deque

def min_knight_moves(start, target):
    # Movimientos del caballo
    moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
    
    # Cola para BFS y HashSet para asegurar que no revisemos posiciones repetidas
    queue = deque([(start, 0)])
    visited = set()
    
    while queue:
        (x, y), steps = queue.popleft()
        
        # Verificar si llegamos al destino
        if (x, y) == target:
            return steps
        
        # Añadir a los siguientes posibles movimientos si no se han visitado
        for dx, dy in moves:
            new_pos = (x + dx, y + dy)
            
            if new_pos not in visited:
                visited.add(new_pos)
                queue.append((new_pos, steps + 1))

# Ejemplo de uso
start_pos = (0, 0)
target_pos = (4, 5)
print(min_knight_moves(start_pos, target_pos))

En este seudocódigo, mantenemos un conjunto visited para evitar procesar múltiples veces la misma posición, mejorando así la eficiencia.

Recomendaciones prácticas y consejos

Comprender el movimiento del caballo: Antes de implementar, asegúrate de tener claras las ocho posibles orientaciones del movimiento del caballo.
Utilizar estructuras adecuadas: Las estructuras de datos como deque y set son cruciales para una correcta y eficiente implementación de BFS.
Optimización: Aunque BFS es efectivo, siempre es bueno estar abierto a nuevas ideas y optimizaciones. Invitamos a discutir posibles mejoras ya sea en complejidad temporal o espacial.

Aprender a implementar y optimizar algoritmos mediante ejemplos como este no solo mejora las habilidades de resolución de problemas, sino que también abre puertas a comprender estructuras de datos más complejas. ¡Continúa explorando y desafiando tus límites en cada lección!

Daniel Ortiz

student•

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

JOHANBERT MOSQUERA

student•

jajajaja trabajo honesto dice jajajaj

Mario Alberto Hernández Pintor

student•

En javascript:

Miguel Angel Reyes Moreno

student•

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

Yojan Antonio Pardo Zabala

student•

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?


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;
    }
}