El Número de Dios

Antes de nada, tenemos que comprender qué es un algoritmo óptimo, semi-óptimo y no óptimo. Un algoritmo óptimo es aquel, cuyo resultado en el cubo se ha realizado con el mínimo número de movimientos. No es muy común encontrarlos, ya que requiere cierto tiempo de procesamiento en el ordenador y la relación procesamiento/número de movimientos no es eficiente. Por este problema, los ordenadores suelen buscar una solución semi-óptima, esto es, una solución al algoritmo muy próxima a la solución óptima y que no requiere tanto tiempo de procesamiento. Puede añadir varios movimientos más que la solución más corta. Por último, una solución no óptima es aquella que excede cierto número de movimientos y se aleja de la solución óptima.

Comprendido esto, los más expertos en la teoría matemática que rodea al cubo siempre se han preguntado cúal es el máximo número de movimientos que requiere la solución óptima de las 43 trillones (y pico) de situaciones posibles en el cubo. Hay mezclas cuya solución óptima tiene 8 movimientos, pero hay otras tantas cuya solución óptima son 9, por poner un ejemplo. Entonces... ¿cuál es el máximo?¿qué mezcla (o mezclas) tiene una solución óptima con mayor número de movimientos? Este máximo se conoce como Número de Dios, y no estaba muy claro hasta hace poco.

Se empezó pensando que el Número de Dios era 52. Nada más lejos de la realidad, hoy se sabe y se ha demostrado que es  20. Esta demostración se ha llevado a cabo por lo que se denomina coloquialmente "fuerza bruta": un ordenador se dedica a resolver todas las combinaciones posibles en algo que un humano tardaría meses o incluso años. Sin embargo no fue necesario resolver todos los estados del cubo de Rubik, pues eliminando simetrías y casos evidentes (como el scramble R2, por ejemplo) se pudo reducir el número de casos a "tan solo" 55.882.296, todo un logro. A partir de esto, y gracias a una generosa aportación de super-computadoras de Google, se logró llegar a la conclusión de que el Numero de Dios era 20 y no podía reducirse más.

Como curiosidad, la solución que más trabajo costó a los ordenadores fue la siguiente:

F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2

Se podría denominar como la posición más difícil del cubo de Rubik, o sea, el cubo más complicado (al menos para un ordenador).

Podéis encontrar mucha más información al respecto sobre el Número de Dios en esta página web: http://www.cube20.org/ (ENG)