Minimum Knight's Move con BFS

Cursos Empresas Blog Live Conf Precios

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Minimum Knight's Move con BFS

Resumen

El problema Minimum Knight's Move plantea un reto clásico de algoritmos: dado un caballo en un tablero de ajedrez infinito, calcular la cantidad mínima de saltos necesarios para llegar desde una posición de origen hasta una de destino. La clave está en pensar el tablero como un grafo y aplicar Breadth First Search (BFS) para encontrar la ruta más corta.

¿Por qué un tablero de ajedrez se puede tratar como un grafo?

Cada casilla del tablero funciona como un nodo. Lo interesante es que las conexiones entre nodos no son las casillas contiguas, como pasaría con un peón, sino las casillas que respetan el movimiento en L del caballo.

Desde la posición donde está el caballo, los nodos vecinos son las ocho casillas a las que puede saltar siguiendo su patrón característico. Esa relación entre casilla y vecinos es exactamente lo que define un grafo.

¿Qué es BFS y por qué sirve aquí? Breadth First Search recorre un grafo por niveles, explorando primero todos los vecinos cercanos antes de avanzar a los lejanos. Por eso garantiza encontrar el camino más corto en número de saltos.

¿Cómo se modelan los movimientos del caballo en código?

El caballo tiene ocho direcciones posibles desde cualquier casilla [1:30]. Para representarlas, sumas o restas a las coordenadas actuales siguiendo este patrón:

En X suma 2 o -2, y en Y suma 1 o -1.
En X suma 1 o -1, y en Y suma 2 o -2.

Esas combinaciones generan los ocho saltos posibles. Cada salto que haces te lleva a un nuevo nodo, y desde ese nodo se abren otras ocho posibilidades.

¿Cómo aplicar BFS para contar la mínima cantidad de saltos?

La idea es avanzar por niveles desde el origen [1:50]. El nivel uno son las ocho casillas alcanzables en un solo salto. El nivel dos son las casillas alcanzables desde esas primeras ocho, y así sucesivamente.

La primera vez que el destino aparezca en alguno de los niveles, ese número de nivel es la respuesta. Como BFS explora por capas, garantizas que ningún camino más corto pasó desapercibido.

¿Qué estructuras de datos necesitas para resolverlo?

Dos estructuras hacen el trabajo pesado: una queue y un hash set. Cada una cumple un rol específico dentro del recorrido.

La queue respeta el principio FIFO, donde el primer elemento que entra es el primero que sale [3:30]. Eso es justo lo que necesitas para procesar primero las casillas de niveles cercanos antes que las de niveles lejanos. No puedes llegar a una coordenada lejana sin haber pasado por las cercanas primero.

El hash set almacena las casillas ya visitadas. Su utilidad es enorme porque consultar si un elemento existe en un hash set tiene complejidad O(1) [3:00]. Sin esta verificación, el caballo podría regresar infinitamente a casillas anteriores y nunca terminar.

¿Por qué usar un hash set en vez de una lista? Porque revisar pertenencia en una lista es O(n), mientras que en un hash set es O(1). Esa diferencia evita que el algoritmo se vuelva lento al crecer el tablero.

¿Cómo se combinan queue y hash set durante el recorrido?

El flujo funciona así de claro:

Sacas la casilla al frente de la queue.
Generas las ocho casillas vecinas según el movimiento del caballo.
Por cada vecina, revisas si ya está en el hash set. Si no, la agregas al set y al final de la queue.
Repites hasta que la casilla destino aparezca.

Cada iteración remueve la dirección actual y suma las nuevas al final de la cola. Así mantienes el orden por niveles que BFS necesita.

¿Cuál es la complejidad temporal y espacial de esta solución?

La complejidad espacial es O(n), donde n es la cantidad de pasos posibles que se exploran hasta llegar al destino [4:30]. La cola puede crecer bastante, sobre todo cuando el destino está lejos del origen.

Es una complejidad alta, pero razonable considerando que estás haciendo BFS sobre un tablero infinito. Cada nivel multiplica las posibilidades, y el hash set evita recalcular casillas ya vistas, lo que mantiene el algoritmo viable.

¿Existen soluciones más eficientes que BFS para este problema?

BFS resuelve correctamente el problema, pero no siempre es la opción óptima. Existen aproximaciones matemáticas o BFS bidireccional que pueden mejorar tanto el tiempo como la memoria utilizada.

Si tienes una propuesta con mejor complejidad, compártela en los comentarios. ¿Qué enfoque alternativo se te ocurre para reducir la cantidad de casillas exploradas?

Comentarios

Daniel Ortiz

Estudiante

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

Estudiante

jajajaja trabajo honesto dice jajajaj

Diego Portillo

Estudiante

Solution:

def minimum_knight_moves(x_start, y_start, x_end, y_end):
    moves = 0
    options = [
        (1,2), (2,1),
        (-1,2), (-2,1),
        (1,-2), (2,-1),
        (-1,-2), (-2,-1)
    ]
    queue = [(x_start, y_start)]
    while queue:
        if (x_end, y_end) in queue:
            break
        for coordinates in range(len(queue)):
            # important: here we use FIFO to follow the order in which elements are added
            x, y = queue.pop(0)
            print(x, y)
            for option in options:
                x_add, y_add = option
                queue.append((x+x_add, y+y_add))
        moves += 1
    return moves

print(minimum_knight_moves(0,0,5,5) == 4)

Review comparing with teacher's code (mine has a bug):

Comparison

Correctness — the most important difference

The first solution has a critical bug: it checks (x_end, y_end) in queue to verify if the destination was reached, but this searches the entire queue including future positions that haven't actually been "reached" yet at that level. On top of that, it has no visited set, so the queue grows infinitely — on a board without boundaries, it would never finish or take extremely long.

The second solution is correct: it checks the destination when dequeuing each position, and uses visited to avoid revisiting nodes.

queue.pop(0) vs deque.popleft() complexity

python

# Solution 1 — Python list
queue.pop(0)  # O(n) — shifts all elements

# Solution 2 — deque
queue.popleft()  # O(1) — designed for this

Using a list as a queue is a classic performance mistake. For BFS you should always use deque.

BFS structure

The first attempts level-by-level BFS with an inner loop, which is a valid way to track steps, but it's poorly implemented because it mixes the destination check outside the main loop. The second carries the step counter directly in the queue as (position, steps), which is cleaner and less error-prone.

Visited set

Without visited, the first solution revisits positions infinitely. This is its most serious flaw — in practice the program never terminates for large inputs.

Verdict

Solution 1Solution 2

Correct BFS

❌

✅

Visited set

❌

✅

Efficient queue

❌ O(n) pop

✅ O(1) pop

Always terminates

❌

✅

The second solution is clearly superior in every aspect. The first has the right intuition but fails in execution.

Mario Alberto Hernández Pintor

Estudiante

En javascript:

Miguel Angel Reyes Moreno

Estudiante

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

Estudiante

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

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Inorder, Preorder y Postorder en árboles

Suma de caminos raíz a hoja en árboles

Suma de caminos raíz a hoja con DFS

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Número de islas con DFS en matrices

Problema de islas resuelto con DFS

Playground: Number of Islands

Número de islas con DFS recursivo en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Cómo BFS recorre grafos por niveles

Implementación de BFS con colas en Python

Mínimos movimientos del caballo en ajedrez