El Algoritmo de Dios para el cubo Rubik

Seguramente conoces el rompecabezas que hizo furor
durante la década de 1980: el cubo de
Rubik. Si te cuentas entre la legión de
usuarios que pasaron cientos de horas
intentando armarlo, te gustará saber
que se ha encontrado un algoritmo
que permite solucionarlo en solo 23
movimientos, independientemente de su
estado inicial.

El cubo de Rubik es un rompecabezas mecánico
y tridimensional, inventado en 1974 por un
profesor de arquitectura húngaro de apellido
Rubik. Las caras de un cubo están divididas
en 9 cuadros de un mismo color, que pueden
moverse mediante rotaciones de las secciones que
componen el rompecabezas. El objetivo del juego
consiste en, partiendo del cubo desordenado, armar
una cara de cada color. A pesar de que solo se tienen
27 piezas, de las cuales 6 están fijas, el número de estados
iniciales posibles es impresionante. Según Wikipedia, donde
puede encontrarse la demostración matemática, existen
43.252.003.274.489.856.000 (cuarenta y tres trillones
doscientos cincuenta y dos mil tres billones doscientos
setenta y cuatro mil cuatrocientos ochenta y nueve millones
ochocientos cincuenta y seis mil) permutaciones posibles.
Sin embargo, hay personas que pueden resolverlo en solo
unos minutos, gracias al empleo de algoritmos o técnicas
sumamente eficaces, que limitan la cantidad de movimientos
necesarios a unos pocos.
Pero recientemente se ha encontrado, utilizando un
superordenador, que el número máximo de movimientos
necesarios para armar el cubo, a partir de cualquier posición
inicial, es de 23. El estudio lo ha llevado a cabo Tomas
Rokicki, y lo ha publicado bajo el nombre Twenty-Three
Moves Suffice. En él se explica como, utilizando el tiempo
libre de un superordenador de Sony Pictures Imageworks,
encontró el “Algoritmo de Dios” para el cubo de Rubik.
La denominación de “Algoritmo de Dios” se debe a que se
trata de un algoritmo práctico que produce una solución con
el menor número de movimientos posibles. Se supone que un
omnisciente conocería una solución óptima para cada posible
configuración, de allí el nombre. Por supuesto, la solución
encontrada dice que 23 movimientos es el máximo número
necesario, en el peor de los casos posibles. Si uno tiene un
poco de suerte con las condiciones iniciales, podría resolverlo
en 22, 21 o (en un caso trivial) en solo 1 movimiento.
De hecho, aquí puedes ver a un aficionado resolviéndolo en
11 segundos:

http://www.neoteo.com/descubierto-el-algoritmo-de-dios-para-el-cubo-de.neo

Y esta no es una información que le interese a pocos. Se
estima que unos 100 millones de cubos Rubik se han vendido
en el mundo entero. Y eso sin contar las “copias piratas”. -

Ariel
Palazzesi