Sam Loyd
Sam Loyd es considerado uno de los creadores de puzzles más importantes de Estados Unidos, si no el más importante, tal y como lo nombró Martín Gardner en 1957. Pero, al mismo tiempo, fue mentiroso y oportunista, asignándose la autoría de puzzles que no inventó.
Uno de ellos fue el juego de las 15 baldosas. Consiste en un "tablero" con 4×4 compartimentos en el que hay colocadas 15 "baldosas" que se pueden deslizar unas sobre otras aprovechando el hueco que dejan. Las baldosas comienzan en una determinada configuración y el objetivo es conseguir recolocarlas en otra.
La primera versión del juego fue creada por Palmer Chapman durante la década de 1870. En 1880 su popularidad estalló en Estados Unidos, convirtiéndose en una moda maniática que lo hizo aparecer en infinidad de lugares, como ocurriría con el cubo de Rubik un siglo después. Aun así, no fue hasta 1891 cuando Sam Loyd empezó a asegurar que había sido invención suya, cosa que afirmó hasta su muerte en 1911.
Al menos sí colaboró al resurgimiento del juego cuando ofreció un premio de 1.000 dólares (una pequeña fortuna para el momento) a quien resolviera el que llamó puzzle 15−14. Consistía en una distribución inicial de las piezas en la que la número 14 y la número 15 estaban invertidas y se pedía que se colocaran todas en orden.
También en esto fue un tramposo. En 1879 se había demostrado matemáticamente que era imposible resolverlo. Las configuraciones de las baldosas forman dos conjuntos independientes. Es posible desplazar las baldosas de cualquier configuración a cualquier otra del mismo conjunto, pero es imposible pasar de una configuración de un conjunto a otra del contrario.
Una configuración incial puede llevarse a una configuración final si la paridad del número de inversiones es la misma. El número de inversiones se calcula colocando todas las baldosas seguidas por filas, poniendo un 16 en el lugar que ocupa el hueco, y contando la cantidad de parejas de baldosas en las que una baldosa con un número más grande aparece antes que una con un número más pequeño. Por ejemplo, la configuración inicial con todas las fichas colocadas en secuencia (1, 2, …, 16, figura a) no tiene inversiones y por tanto tiene paridad par. En la configuración tramposa de Sam Loyd (1, 2, …, 13, 15, 14, 16, figura b) la pareja de baldosas 15−14 supone una inversión (la única en este caso) y por tanto la configuración tiene paridad impar. Al tener paridades contrarias, una configuración no es alcanzable desde la otra.
La figura c muestra una configuración con dos inversiones (la formada por las parejas 2−1 y 3−1), lo que la categoriza como paridad par y por tanto es alcanzable desde la configuración inicial. Por último, la figura d tiene tres inversiones, las dos de la figura c y la formada por la pareja 15−14. Tiene por tanto paridad impar y no es alcanzable desde la configuración inicial, pero sí desde la configuración tramposa de Sam Loyd.
Entrada
Cada caso de prueba está compuesto por una permutación de los números del 1 al 16 indicando una configuración del puzzle de las 15 baldosas.
Salida
Por cada caso de prueba, el programa escribirá SI si la configuración es alcanzable desde la posición inicial del tablero con todas las baldosas en orden. Si no es alcanzable se escribirá NO.
Entrada de ejemplo
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 16 2 3 1 4 5 6 7 8 9 10 11 12 13 14 15 16 2 3 1 4 5 6 7 8 9 10 11 12 13 15 14 16
Salida de ejemplo
NO SI NO