2.1 - Introducción
El puzzle cuadrado de piezas deslizantes fue creado por Sam Loyd en 1878. El puzzle original por él diseñado disponía de 15
cuadrados numerados del 1 al 15 que se colocaban en una caja de 4 filas x 4 columnas, dejando vacía una de las 16 posiciones.
El inventor de este puzzle ofreció 1000 dólares (de los de aquella época) a quien resolviera una configuración que él había predeterminado.
Muchísimas personas reclamaron el premio asegurando haberlo resuelto pero, lamentablemente, no podían recordar los movimientos que habían
tenido que realizar. No es de extrañar, puesto que dos científicos demostraron posteriormente que sólo la mitad de las posibles configuraciones
iniciales del puzzle de 15 piezas tenían una solución (y, lógicamente, la configuración que proponía Sam Loyd, estaba entre las que eran
irresolubles).
2.2 - Objetivo y solubilidad del puzzle
Los puzzles de piezas deslizantes se encuadran dentro de los pasatiempos dinámicos y, en particular, en el grupo de los que consisten
en hallar la serie de movimientos necesarios para resolver una determinada tarea.
Los cuadrados que conforman el puzzle (8, 15, 24, 35, ...) se colocan al azar formando una configuración inicial aleatoria. El objetivo
es, deslizándolos de uno en uno, colocarlos ordenadamente en una distribución establecida de antemano (restableciendo la imagen de fondo,
ordenándolos alfabéticamente o del 1 al número de piezas,...). Como se ha comentado en la Introducción, no todas las posibles configuraciones
iniciales tienen solución. Para determinar la solubilidad de una configuración inicial dada se actúa de la siguiente forma:
- Por cada cuadro del puzzle determinamos el total de cuadros posteriores (de izquierda a derecha y de arriba abajo) que tienen un número
de orden menor que él (considerando que en la configuración final, al cuadro de la esquina superior izquierda le correspondería el 1,
y al del extremo derecho de la fila inferior, el valor correspondiente al número de piezas). A este valor se le denomina inversiones
de la permutación.
- Sumamos los valores obtenidos en cada cuadro. En el caso de que el puzzle tenga un número par de filas, a esta cantidad hay que sumarle
el número de la fila donde se encuentra el cuadrado vacío.
- Si el número obtenido es par, el puzzle tiene solución. Si es impar, el puzzle es irresoluble.
|
