He desarrollado un pequeño programa donde se pueden definir la posición de las piezas y resolver tableros de 8 piezas (3x3) y tableros de 15 piezas (4x4) y se puede resolver automáticamente (si tiene solución ) usando el algoritmo A estrella (A *).
Se basan en este algoritmo, aunque los tableros de 15 piezas (y en general los de orden superior a 4x4), se resuelven con un paso "intermedio"... os explico...
Tenemos que llegar a la posición de la figura 1, para resolver el puzzle.
El primer paso es conseguir que la columna 1 y fila 1 queden ordenadas:
 |
| Figura 2 |
Una vez conseguido esto, resolvermos el puzzle 8 (3x3) que nos queda.
En mi programa uso el algoritmo A* para resolver el puzzle. Haciendo los siguientes pasos.
- El usuario define el tablero, y pulsa el botón de "Resolver"
- Con el tablero ya definido, se lleva a la posicion de las fichas que indica en la figura 2. Para ello definimos el tableroFin como el de la figura 2 (teniendo en cuenta solo la fila 1 y columna 1, el resto me da igual lo que valgan)
- Luego resuelvo el puzzle de 3x3, que ha quedado, llevandolo al estado final de la figura 3
 |
| Figura 3 |
En mi caso los cuadros se numeran del 1 al 16, siendo el 16 el cuadro "vacio".
He "aprovechado" , las mismas funciones de calculo algoritmo Start, F, H, para los dos tipos de tablero, añadiendo un parametro opcional que indicaba como era el tablero (de 8 o 15) y asi conocer cual es el estado fin al que hay que llegar.ç
De ese modo el programa puede resolver los dos tipos de de puzzles.
Aqui os dejo los archivos del código fuente y el ejecutable en gambas3.2:
Código Fuente: codigo 0.0.12 (actualizado)
Ejecutable Gambas 3.2: .gambas
Notas:
Mejoras Rendimiento:
Si se ejecuta como root y con el comando nice se le dice que le de la maxima prioridad se mejora el rendimiento de la aplicacion:
$nice -n -19 ./Puzzle15slide.gambas
21/9/12: Actualizado. Corregido bug a la hora de introducir datos en el tablero, y añadido un reloj para indicar el tiempo que se ha tardado en encontrar la solución.
Fuente:
Resolucion de puzzle deslizantes de Lara Rojo Celemín e Iván Suárez Morejudo
Nota:
Si no ve completo este articulo es que tienes adblock activado. Por favor desactive adblock para este blog. Gracias
