Puzzle del 8

El 8 Puzzle es el hermano menor del 15 Puzzle, jugado en una rejilla 3x3 con fichas numeradas 1 a 8 y un espacio vacío. El objetivo es deslizar las fichas en el espacio vacío para organizarlas en orden numérico. A pesar de su tamaño compacto, el 8 Puzzle ofrece un desafío satisfactorio, y tiene un lugar especial en la informática como uno de los problemas más estudiados en algoritmos de búsqueda de inteligencia artificial.

Reglas

1. El tablero es una cuadrícula 3x3 con azulejos numerados 1-8 y un espacio vacío.
2. Deslice cualquier baldosa adyacente al espacio vacío en el espacio vacío.
3. Sólo una baldosa se mueve a la vez, horizontal o verticalmente.
4. Arregle las fichas en orden: 1-3 en la fila superior, 4-6 en la fila media, 7-8 y el espacio vacío en la fila inferior (vacío en la parte inferior derecha).

Estrategias

• Top Row First: Coloca los azulejos 1, 2, y 3 en la fila superior. Una vez encerrados, no deberían tener que moverse de nuevo.
• Columna izquierda Siguiente: Colocar los azulejos 4 y 7 en la columna izquierda (si no se hace ya mientras se resuelve la fila superior).
• Afinar el Corner: Las baldosas restantes (5, 6, 8) y el espacio vacío forman un pequeño área de 2x2 que se puede resolver por las baldosas en bicicleta alrededor.
• #Cycle Move # Cuando los últimos azulejos necesitan reordenar, girar alrededor del espacio vacío en un ciclo hasta llegar a las posiciones correctas.
• * Comprobación de viabilidad* Exactamente la mitad de todas las configuraciones posibles son solvables. Cuenta el número de inversiones (tiles que aparecen ante su predecesor natural). Si el conteo es incluso, el rompecabezas es solvable; si es extraño, no lo es.
• Manhattan Distancia: Para cada ficha, calcula cuántos movimientos es desde su posición de meta (horizontal + vertical). La suma da un límite inferior al número de movimientos necesarios. Usa esto para medir lo cerca que estás para resolver.

El 8 Puzzle es un descendiente directo del 15 Puzzle, escalado de un 4x4 a una cuadrícula 3x3. Mientras que el 15 Puzzle dominaba la atención popular desde 1880 en adelante, el 8 Puzzle más pequeño se convirtió en el centro del estudio académico, particularmente en el campo de la inteligencia artificial.

En los años 1960 y 1970, los investigadores de AI adoptaron el 8 Puzzle como un referente estándar para los algoritmos de búsqueda de pruebas. Su espacio estatal es lo suficientemente pequeño para ser explorado completamente (181,440 estados alcanzables de 362,880 posibles permutaciones), pero lo suficientemente complejo para probar la eficiencia de diferentes enfoques. El rompecabezas se utilizó para demostrar y comparar la búsqueda de amplitud, búsqueda de profundidad, profundización iterativa, y el famoso algoritmo A* desarrollado por Peter Hart, Nils Nilsson, y Bertram Raphael en 1968.

El algoritmo A*, cuando se combina con la heurística de distancia de Manhattan, puede resolver la configuración de 8 Puzzle de forma óptima, encontrando el número mínimo de movimientos. El número máximo de movimientos necesarios para resolver cualquier configuración solvable es de 31, y el promedio es de unos 22 movimientos. Estos resultados se establecieron mediante búsquedas computacionales exhaustivas.

El 8 Puzzle sigue siendo un pilar de cursos introductorios de IA y algoritmos en universidades de todo el mundo. Los estudiantes implementan algoritmos de búsqueda usando el rompecabezas para entender conceptos como heurística, caminos óptimos y exploración del espacio-estado. Sirve como puerta de entrada para entender problemas más complejos en la planificación, robótica y optimización. Más allá del mundo académico, el 8 Puzzle es un popular rompecabezas casual que se encuentra en tiendas de juguetes, aplicaciones móviles y como un mini-juego dentro de juegos de video más grandes.