Juegos de Lógica y Estrategia

Es éste un conocido juego de tipo solitario.

En una cuadrícula de 4x4 se colocan los números del 1 al 15, dejando una casilla vacía, que puede ser ocupada por las piezas adyacentes.

Se trata de desordenar las 15 piezas con número y volver a recomponer el orden.

Puede resultar entretenido el proceso mediante el que se consigue resolverlo, pero el problema que te planteo es decidir si cualquier permutación de los 15 números puede ser reordenada.

Es decir, si el juego tiene solución para cualquier distribución inicial de los 15 números.