12 - Ejemplo práctico 3: backtracking en un laberinto

12.1 Formulación del problema

Tenemos un laberinto rectangular representado como una matriz de caracteres donde # son paredes, . celdas transitables, S el inicio y E la salida. Debemos encontrar un camino sin recursión, usando una pila para recordar las posiciones visitadas y retroceder cuando no haya movimientos disponibles.

12.2 Estructura de datos

  • Una pila que almacena coordenadas (fila, columna).
  • Una matriz auxiliar de visitados para evitar bucles.
  • Un arreglo con los cuatro movimientos posibles: arriba, abajo, izquierda, derecha.

12.3 Flujo del algoritmo

  1. Apilar la posición de inicio.
  2. Mientras la pila no esté vacía:
    • Consultar el tope.
    • Si es la salida, detenerse.
    • Buscar el siguiente vecino no visitado; si existe, marcarlo, apilarlo y continuar.
    • Si no hay vecinos, desapilar (backtracking).

El algoritmo es un DFS iterativo basado en pila.

12.4 Casos especiales

  • Laberintos sin salida: la pila terminará vacía sin hallar E.
  • Múltiples salidas: se detiene en la primera encontrada; se puede continuar para encontrar todas.
  • Restricciones de movimiento (diagonal, portales) pueden modelarse agregando direcciones extra.

12.5 Implementación en Python

MOVS = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def resolver(mapa):
  filas, cols = len(mapa), len(mapa[0])
  visitado = [[False] * cols for _ in range(filas)]

  inicio = None
  for i, fila in enumerate(mapa):
    for j, ch in enumerate(fila):
      if ch == "S":
        inicio = (i, j)
        break
    if inicio:
      break

  if inicio is None:
    return False

  pila = [inicio]
  visitado[inicio[0]][inicio[1]] = True

  while pila:
    fila, col = pila[-1]
    if mapa[fila][col] == "E":
      return True

    avanzo = False
    for df, dc in MOVS:
      nf, nc = fila + df, col + dc
      if not (0 <= nf < filas and 0 <= nc < cols):
        continue
      if mapa[nf][nc] == "#" or visitado[nf][nc]:
        continue
      visitado[nf][nc] = True
      pila.append((nf, nc))
      avanzo = True
      break

    if not avanzo:
      pila.pop()

  return False


if __name__ == "__main__":
  lab = [
    "S....#..",
    "##.#.#..",
    "..#....E",
    "..#....#",
    "..#####.",
    "..#.....",
    "..###.##",
    "........",
  ]

  print("Resultado:", "Camino encontrado" if resolver(lab) else "Sin salida")

Este ejemplo usa un tablero pequeño, pero la lógica escala a mapas grandes cambiando las constantes.

Abrir editor online
Representación del laberinto resuelto con pilas Ilustración del camino encontrado

12.6 Extensiones y entrevistas

  • Registrar el camino final copiando la pila en un arreglo auxiliar.
  • Agregar pesos o recolectar objetos en el recorrido.
  • Convertir el algoritmo a una pila de listas para guardar decisiones en juegos de backtracking, muy popular en entrevistas de algoritmos.
Retornar