8 Puzzle · Búsqueda en anchura (BFS)

Aplicación de escritorio en Java que resuelve el 8-puzzle con búsqueda en anchura (BFS). Encuentra la secuencia más corta de movimientos entre dos configuraciones del tablero, informa el tiempo de búsqueda y los nodos expandidos, y exporta el árbol de búsqueda a Graphviz para visualizarlo.

Proyecto del curso Programación 3 en la Universidad Mariano Gálvez de Guatemala (2025).

El problema

El 8-puzzle es un tablero de 3×3 con ocho fichas numeradas y un espacio vacío. En cada movimiento, una ficha vecina se desliza hacia el espacio. El objetivo es llegar a una configuración final con el menor número de movimientos. Desde cualquier configuración se pueden alcanzar 181 440 estados distintos, que son la mitad de las 9! permutaciones del tablero.

Funcionalidades

• Entrada simple: el estado inicial y el objetivo se escriben como 9 números separados por comas, con 0 como espacio vacío.
• Solución óptima: BFS explora el árbol nivel por nivel, así que la primera solución que encuentra tiene la menor cantidad de movimientos posible.
• Paso a paso: lista la secuencia de movimientos del espacio vacío (arriba, abajo, izquierda o derecha).
• Métricas: tiempo de búsqueda en milisegundos y cantidad de nodos expandidos.
• Exportación a Graphviz: genera arbol_8Puzzle.dot con el árbol completo si la solución tiene hasta 5 movimientos, o solo con el camino de la solución si es más larga, para que el gráfico siga siendo legible.
• Validación del formato de entrada y botón para reiniciar la búsqueda.

Cómo funciona la búsqueda

flowchart TD
    A["Encolar el estado inicial"] --> B{"¿Cola vacía?"}
    B -- Sí --> X["Sin solución"]
    B -- No --> C["Sacar el primer nodo de la cola"]
    C --> D{"¿Es el estado objetivo?"}
    D -- Sí --> E["Reconstruir el camino subiendo por los padres"]
    D -- No --> F["Generar hasta 4 estados sucesores"]
    F --> G["Encolar los que no se han visitado"]
    G --> B

Loading

• Estado representa el tablero como una matriz de 3×3. Sobrescribe equals y hashCode según el contenido, lo que permite guardar los estados en un HashSet y detectar en tiempo constante, en promedio, los que ya se visitaron.
• generarEstadosHijos produce los sucesores moviendo el espacio vacío en las direcciones posibles.
• BuscadorBFS usa una cola FIFO. Cada NodoArbol guarda su estado, su padre, la acción que lo generó y su nivel, lo que permite reconstruir la solución y dibujar el árbol.
• GeneradorGraphviz recorre el árbol y escribe el archivo DOT, con cada tablero como nodo y cada movimiento como etiqueta de la arista.

Resultados de ejemplo

Con el estado objetivo 1,2,3,4,5,6,7,8,0:

Estado inicial	Movimientos	Nodos expandidos	Tiempo aproximado
1,2,3,4,5,6,0,7,8	2	7	1 ms
1,2,3,0,4,6,7,5,8	3	17	< 1 ms
8,6,7,2,5,4,3,0,1	31	181 439	0.5 s
1,2,3,4,5,6,8,7,0	Sin solución	181 440	0.4 s

El tercer caso requiere 31 movimientos, el máximo que puede necesitar cualquier 8-puzzle, y BFS lo resuelve explorando prácticamente todo el espacio de estados. El cuarto no tiene solución porque intercambia dos fichas, y ninguna secuencia de movimientos puede lograr eso. Los tiempos dependen del equipo.

Árbol de búsqueda con Graphviz

Árbol exportado por la aplicación para el estado inicial 1,2,3,0,4,6,7,5,8, cuya solución tiene 3 movimientos:

Para convertir el archivo exportado en una imagen:

dot -Tpng arbol_8Puzzle.dot -o arbol.png

Estructura del proyecto

8-Puzzle-BFS/
├── src/
│   ├── InterfazPrincipal.java    # Ventana principal y punto de entrada
│   ├── BuscadorBFS.java          # Algoritmo de búsqueda en anchura
│   ├── Estado.java               # Tablero 3×3 y generación de sucesores
│   ├── EstadoConAccion.java      # Estado junto con el movimiento que lo produjo
│   ├── NodoArbol.java            # Nodo del árbol de búsqueda
│   ├── GeneradorGraphviz.java    # Exportación a formato DOT
│   └── resources/ImageIcon.png   # Ícono de la ventana
├── docs/
│   └── arbol-ejemplo.png         # Árbol de ejemplo generado con Graphviz
├── nbproject/                    # Configuración del proyecto NetBeans
├── build.xml                     # Script de compilación Ant
└── manifest.mf

Cómo ejecutarlo

Requiere JDK 24 o superior. Graphviz es opcional y solo se necesita para convertir el árbol exportado en imagen.

Con NetBeans: abre el proyecto (File → Open Project) y ejecútalo.

Desde la terminal (en Windows, reemplaza : por ; en el classpath):

javac -d build/classes src/*.java
java -cp build/classes:src InterfazPrincipal

Uso

1. Escribe el estado inicial, por ejemplo 1,2,3,0,4,6,7,5,8.
2. Escribe el estado objetivo, por ejemplo 1,2,3,4,5,6,7,8,0.
3. Pulsa Buscar Solución para ver los movimientos, el tiempo y los nodos expandidos.
4. Pulsa Exportar Graphviz para generar arbol_8Puzzle.dot en la carpeta desde donde se ejecuta la aplicación.
5. Pulsa Reiniciar Busqueda antes de resolver otro tablero.

Próximas mejoras

• Reiniciar automáticamente el estado de la búsqueda al empezar una nueva. Hoy, si no se pulsa Reiniciar Busqueda, la segunda búsqueda puede dar un resultado incorrecto, como repetir la solución anterior.
• Comprobar antes de buscar si el objetivo es alcanzable, usando la paridad de inversiones, para no recorrer los 181 440 estados en vano.
• Validar que la entrada contenga los números del 0 al 8 sin repetir.
• Ejecutar la búsqueda en segundo plano para que la ventana no se congele en los casos difíciles.
• Añadir una búsqueda informada, como A* con distancia Manhattan, para compararla con BFS.

Autora

Erica Franco · @Erica4fr