Resolución rápida del cubo de Rubik

El cubo de rubik es uno de los puzles más extendidos del mundo, creado por Erno Rubik en 1974. Dicho cubo alcanzó gran fama como juguete, y salieron al mercado distintas versiones del mismo, e incluso algunas que no tienen forma de cubo.

El cubo de rubik tradicional supone un desafío, puesto que tiene muchos estados y sólo uno se considera «estado final» o «solución». También es un desafío crear una aplicación capaz de resolver el cubo.

Debido a la amplitud del problema, crear una aplicación que resuelva el cubo es una tarea complicada.

Las aplicaciones actuales buscan resolver el cubo de manera óptima, eso implica una exploración de un espacio de estados enorme, lo que consumiría mucho tiempo. Hoy día se usan distintos métodos para encontrar la solución óptima en el menor tiempo posible.

Pero hay un hecho curioso, en las competiciones oficiales del cubo de rubik, donde se trata de resolver en el menor tiempo posible, los participantes no resuelven el cubo de manera óptima, es decir, hacen más movimientos de los necesarios.

Entonces, ¿se puede resolver el cubo de rubik de manera sub-óptima, pero ganando mucho tiempo?

Siguiendo una de las metodologías que existen para resolverlo nos ahorramos la exploración de un árbol de estados muy grande dividiendo el desarrollo del cubo en etapas. Cada etapa tiene un objetivo concreto y definible, y es fácil verificar si se ha llegado al final de una etapa.

El resultado será una cadena de movimientos que resuelve un cubo dado, y dicha solución la obtendremos casi al instante.

Estado del arte

El cubo de rubik ha supuesto un reto desde que se inventó. Un puzle creado por Erno Rubik, arquitecto, escultor y diseñador de la Escuela de Artes de Budapest. Se dice que es el juguete más vendido con más de 300 millones de unidades vendidas.

El cubo ha supuesto un reto desde que se inventó, ha sido objeto de estudio por parte de la inteligencia artificial, intentando buscar la solución óptima y creando heurísticas, bases de datos de patrones y otras técnicas que ayudaran a buscar la solución.

El enorme espacio de estados del cubo de rubik de 3x3x3 hace interesante su estudio, ya que para buscar la solución hay que explorar un árbol de estados enorme.

En julio de 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson, y John Dethridge probaron que el número máximo de movimientos que hay que realizar para resolver cualquier estado del cubo de rubik es 20. Para ello resolvieron todos los estados del cubo de rubik, con muchas máquinas muy potentes, y con técnicas que les permitían acelerar el proceso (podar el árbol de estado, eliminando estados repetidos, estados simétricos etc….)

Otros puzles

Los puzles de ingenio de distintos tipos son casi tan antiguos como la humanidad misma.

Stomachion

El «Stomachion» se considera el puzle más antiguo del mundo. Similar al Tangram, el juego consistía en una serie de piezas que formaban un cuadrado. El objetivo era armar una serie de figuras usando las piezas.

Ilustración 1: Stomachion

Ilustración 2: Figuras stomachion

Como se ve en la imagen superior, se tenían que conseguir una serie de figuras geométricas, o representando animales, símbolos o personas. Este puzle se dice que es de hace 2200 años y tiene origen en la antigua Grecia.

Fuente: Miguel Abreu García