Implementación del Problema del 8-Puzzle en Python: Algoritmos y Heurísticas

Implementación del Problema del 8-Puzzle en Python

Ejercicio 1: Definición de Acciones Aplicables y Transiciones

En esta sección se define la lógica para identificar los movimientos válidos del hueco (representado por el valor 0) dentro de un tablero de 3x3, así como la función para aplicar dichos movimientos.

def acciones_aplicables(self, estado):
    pos_hueco = estado.index(0)
    accs = list()
    if pos_hueco not in (0, 1, 2):           # Fila de arriba
        accs.append("Mover hueco arriba")
    if pos_hueco not in (6, 7, 8):           # Fila de abajo
        accs.append("Mover hueco abajo")
    if pos_hueco not in (0, 3, 6):           # Columna izquierda
        accs.append("Mover hueco izquierda")
    if pos_hueco not in (2, 5, 8):           # Columna derecha
        accs.append("Mover hueco derecha")
    return accs

def aplicar(self, estado, accion):
    pos_hueco = estado.index(0)
    if accion == "Mover hueco arriba":
        nueva_pos = pos_hueco - 3
    elif accion == "Mover hueco abajo":
        nueva_pos = pos_hueco + 3
    elif accion == "Mover hueco izquierda":
        nueva_pos = pos_hueco - 1
    elif accion == "Mover hueco derecha":
        nueva_pos = pos_hueco + 1
    
    tablero = list(estado)        # Las tuplas no se pueden modificar
    tablero[pos_hueco], tablero[nueva_pos] = tablero[nueva_pos], tablero[pos_hueco]
    return tuple(tablero)

Ejercicio 3: Funciones Heurísticas (h1 y h2)

Para optimizar la búsqueda, implementamos dos heurísticas clásicas: la cantidad de piezas fuera de su lugar (h1) y la distancia de Manhattan (h2).

def h1_ocho_puzzle(estado):
    estado_final = (1, 2, 3, 8, 0, 4, 7, 6, 5)
    contador = 0
    for i in range(9):
        if estado[i] != 0 and estado[i] != estado_final[i]:
            contador += 1
    return contador

def h2_ocho_puzzle(estado):
    estado_final = (1, 2, 3, 8, 0, 4, 7, 6, 5)
    distancia_total = 0
    for pieza in range(1, 9):
        pos_actual = estado.index(pieza)
        pos_objetivo = estado_final.index(pieza)
        fila_actual, columna_actual = pos_actual // 3, pos_actual % 3
        fila_objetivo, columna_objetivo = pos_objetivo // 3, pos_objetivo % 3
        distancia_total += abs(fila_actual - fila_objetivo) + abs(columna_actual - columna_objetivo)
    return distancia_total

Ejercicio 5: Comparativa de Algoritmos de Búsqueda

El siguiente bloque de código permite realizar una comparativa de rendimiento entre diferentes estrategias de búsqueda: Anchura, Profundidad y Primero el Mejor.

def ejercicio_5(recalcular=False):
    combinaciones = [
        ("Anchura", búsqueda_en_anchura, None),
        ("Profundidad", búsqueda_en_profundidad, None),
        ("Primero_h1", búsqueda_primero_el_mejor, h1_ocho_puzzle),
        ("Primero_h2", búsqueda_primero_el_mejor, h2_ocho_puzzle), ]

Continuación del Ejercicio 5

A continuación, se detalla el proceso de iteración sobre los estados y la impresión de resultados formateados:

    print("{0:6} | {1:22} | {2:>6} | {3:>6}".format("Estado", "Algoritmo", "L", "NA"))
    print("-" * 52)
    for nombre_estado, estado in ESTADOS.items():
        for nombre_algoritmo, algoritmo, h in combinaciones:
            referencia = RESULTADOS_DE_REFERENCIA[(nombre_estado, nombre_algoritmo)]
            if referencia is None and not recalcular:
                print("{0:6} | {1:22} | {2:>6} | {3:>6}  (no termina en tiempo razonable)".format(
                    nombre_estado, nombre_algoritmo, "--", "--"))
                continue
            if referencia is not None and not recalcular:
                L, NA = referencia
            else:
                p8p = Problema_con_Analizados(Ocho_Puzzle(estado))
                sol = (algoritmo(p8p, h).solucion() if h else algoritmo(p8p).solucion())
                L, NA = len(sol), p8p.analizados
            print("{0:6} | {1:22} | {2:6d} | {3:6d}".format(nombre_estado, nombre_algoritmo, L, NA))