Solución:
Martin Gardner escribió muy bien el acertijo 14-15 en uno de sus libros de Juegos matemáticos.
Sam Loyd inventó el rompecabezas. Periódicamente publicó recompensas por soluciones a ciertas configuraciones iniciales. No se reclamó ninguna de esas recompensas.
Se dedicó mucho análisis y finalmente se determinó, a través de un argumento de paridad (como se menciona en el comentario anterior), que la mitad de las posibles configuraciones iniciales no tenían solución. Curiosamente, TODOS de las configuraciones de recompensa de Loyd eran irresolubles.
SO: No, todas las configuraciones posibles no tienen solución. Si EMPIEZAS con un rompecabezas resuelto y solo le aplicas transformaciones legales (movimientos), siempre terminará con una configuración que se pueda resolver.
Para la pregunta GENERAL nxm, probablemente tendría que expandir el argumento de paridad.
Solo una pista. Una vez tuve que demostrar con álgebra básica (grupos de permutación) que un rompecabezas estándar de $ 15 $ no tenía solución. La idea allí era la siguiente:
para reorganizar el rompecabezas, debe realizar una permutación de las fichas de $ 15 $.
Ahora, observe que una vez que escribe cualquier permutación permitida, se escribe como un producto de un número par de $ 2 $ -ciclos (siempre mueve el mosaico “vacío”, comienza en la esquina y tiene que estar todavía allí en el final de tus movimientos). Por tanto, la permutación con el signo $ -1 $ no está permitida.
En mi caso fue suficiente concluir que el rompecabezas no tenía solución (tuve que realizar un intercambio entre dos fichas, por lo que tenía el signo $ -1 $). Quizás pueda ayudarlo a excluir algunas configuraciones.