Este curioso vídeo de Polylog es un curioso crossover entre dos de mis temas favoritos: el cubo de Rubik y la criptografía. Explica cómo utilizar la técnica Meet-in-the-Middle («Encontrarse a medio camino») para resolver un cubo de Rubik. Esta técnica se emplea para atacar algunos algoritmos criptográficos, y no es precisamente la ideal para resolver el cubo. Pero sirve para hacerse una idea de cómo funciona este tipo de ataques convirtiendo un ataque imposible por fuerza bruta en otros dos más pequeños que sí son factibles. El vídeo está además estupendamente ilustrado con muy buenas animaciones.
La cuestión es que enseña a ver los movimientos del Cubo como un grafo, algo que puede suceder en otras situaciones, en el que unas posiciones (vértices) llevan a otras con cada giro, en un grafo que podría ser equivalente al de una red social o al de la teoría de los seis grados de separación. Encontrar la solución sería ir de la posición A (mezclado) a la B (resuelto) recorriendo el camino óptimo que tenga menos pasos. Y eso muchas veces puede hacerse, aunque depende de la complejidad y el número de vértices y caminos.
Contamos con una ventaja: para el Cubo de Rubik tradicional de 3×3×3 sabemos que 20 es el número máximo de movimientos necesario para resolverlo de forma óptima. Ojo a los matices, que mucha gente se lía: es el número máximo para resolverlo de forma óptima, que no el mínimo –que pueden ser muchos menos si el cubo está casi resuelto– ni el máximo absoluto –que puede ser infinito si te pones a hacer el tonto girando siempre la misma cara–. El número total de posiciones distintas de un cubo se sabe desde la antigüedad que es 43.252.003.274.489.856.000 (unas 1020).
El problema es que usar la fuerza bruta para llegar a todas las posiciones no sirve porque 1020 es un número un poco inabarcable; que esto es un juguete, no un satélite espía enemigo en el que invertir millones y millones. Pero curiosamente la forma de abordarlo con la técnica Meet-in-the-Middle permite explorar todas las posiciones a las que se pueden llegar con 10 movimientos desde el cubo mezclado (unas 1010) y al mismo tiempo las 1010 posiciones a las que se pueden llegar desde el cubo resuelto. Como está demostrado que el máximo necesario son 20 movimientos, eso quiere decir que si se solapan esos grafos alguna de esas posiciones (que ocupan unos 80 GB, así que se necesita mucha RAM) coincidirá. Se toma un camino del primera grafo, otro del segundo y esa será el camino ideal a la solución. Problema resuelto. Nota: esto solo funciona si el número de posiciones crece de forma suficientemente exponencial.
Incidentalmente, resulta que así es como se atacan criptográficamente sistemas de cifrado como el DES (con una clave única de 56 bits), calculando los dos grupos de 228 bits (algo más abarcable) y solapándolos. Por esta razón se quedó obsoleto y se inventó el Triple DES que usa 168 bits (3×56).
Ya lo hemos dicho antes: este algoritmo Meet-in-the-Middle no es óptimo por poco práctico –muchas veces la fuerza bruta no lo es– pero enseña algunas cosas interesantes. El código puede verse en Github (Rubik MITM Solution) donde se cita a Cube Explorer como sitio en el que encontrar algoritmos mucho más rápidos basados en otras ideas.
En God’s Number is 20 puede leerse algo más sobre cómo se resolvió el problema del número máximo de movimientos y en un vídeo de J Perm se explica lo del conteo de las 4,3 ×1019 posiciones distintas de un cubo 3×3×3.
Relacionado:
- Una forma alternativa de cronometrar cómo se resuelve un Cubo de Rubik
- Un cubo de Rubik completamente funcional fabricado única y exclusivamente con piezas de Lego
- Récord Guinness: resolver tres cubos de Rubik a la vez
- Un cubo de Rubik que levita en el aire mientras se resuelve
- Rubik’s Impossible: un cubo cuyas pegatinas cambian de color
- Gregoire Pfennig, creador de cubos de Rubik y del 33 × 33 × 33
- El puzle de piezas que cambian de color, de Clemens Habitcht
- Un cubo de Rubik tamaño 32.768 x 32.768 x 32.768 que se resuelve (¡fácilmente!) en 7.000 millones de movimientos
- VisualCube, un generador gráfico de imágenes de cubos de Rubik
- Molecube, el cubo de Rubik + sudoku
- Scrambled: un cortometraje de animación protagonizado por un cubo
- La primera Academia Internacional del cubo de Rubik, en A Coruña
- Nuevo récord resolviendo 3 cubos a la vez «haciendo malabarismos»
- Feliks Zemdegs bate nuevamente el récord con 4,22 segundos
- Una máquina que resuelve el cubo de Rubik en 0,38 segundos
- Cubestormer 3: resuelve el cubo de Rubik en poco más de 3 segundos
- El Multicuber 999: un robot de Lego que resuelve el cubo 9x9x9
- Récord de Europa del cubo de Rubik 3x3x3 «a ciegas»
- Esto es lo que ve un experto mientras resuelve el cubo en 9 segundos
- El método Fridrich para resolver el cubo de Rubik
- La segunda juventud del cubo de Rubik, artículo 30º aniversario
- Resolviendo Rubiks colosales de hasta 20×20×20
- Resolver el Cubo de Rubik: mi explicación en un PDF con ilustraciones y todo tipo de detalles. Es uno de los más tradicionales (primitivo e ineficiente), pero fácil de aprender. Permite resolverlo en <60 segundos
