PDF de programación - Cubo de Rubik

Cubo de Rubik

Jesica R. Julita, Vanesa A. Viejo

UTN FRBA (Universidad Tecnológica Nacional Regional Buenos Aires)

Resumen. El Cubo de Rubik fue inventado en 1974 por el profesor húngaro
Erno Rubik. El propósito fue explicar a sus alumnos el concepto de volumen y
espacio. Luego, este juego de ingenio se hizo tan famoso que fue lanzado co-
mercialmente. El objetivo es restaurar el cubo a su condición original. Se debe
rotar cada uno de sus lados para ir llevando cada pieza a su correcta ubicación,
logrando, en cada cara, un único color. Con la Investigación Operativa y la Si-
mulación, se planteó un modelo matemático para resolver un cubo 3x3x3 des-
armado a partir de una mezcla y algoritmos de resolución (Pensados como res-
tricciones). Se resalta la relevancia de la Investigación Operativa para la toma
de decisiones, especialmente para la optimización. El método Simplex permitió
obtener los resultados del problema basados en la programación lineal. Después
de investigar y probar el modelo variando las restricciones y la disponibilidad
mínima de cada cara y/o de los algoritmos del método Fridrich para la resolu-
ción del Cubo de Rubik, se concluyo que, bajo las condiciones del sistema
planteado, la solución óptima es exactamente la inversa de la mezcla propuesta,
sin reducir a cero la cantidad de giros de una o más caras.

Palabras Claves: Cubo de Rubik; mezcla; optimización; programación lineal; y
Simulación.

1 Introducción

A grandes rasgos, el cubo de Rubik es un bloque cúbico con su superficie subdividida
de modo que cada cara consiste en nueve cuadrados. Cada cara se puede rotar, dando
el aspecto de una rebanada entera del bloque que rota sobre sí mismo. Esto da la im-
presión de que el cubo está compuesto de 27 cubos más pequeños.

En su estado original, cada cara del cubo es de un color, pero la rotación de cada
una de estas permite que los cubos más pequeños sean combinados de muchas mane-
ras. Tal es así que el cubo puede tener más de 43 trillones de diversas posiciones.

Existen variaciones al clásico cubo. Algunas con otro número distinto de cuadrados
por cara y otros con diferentes formas (Por ejemplo, el Pyraminx con forma pira-
midal). Las principales versiones que hay son las siguientes: el 2×2×2 (Cubo de bolsi-
llo), el 3×3×3 que es el cubo de Rubik estándar (Utilizado en el presente Trabajo), el
4×4×4 (La venganza de Rubik), el 5×5×5 (El Cubo del Profesor) y desde Septiembre
de 2008 el 6×6×6 (V-Cube 6) y el 7×7×7 (V-Cube 7). La empresa Shengshou lanzó
al mercado, a principios de 2012, cubos de 8x8x8 y 9x9x9. Luego, se incorporó
10x10x10, 11x11x11 y 12x12x12. Recientemente, la marca MoYu (YJ) lanzó al mer-
cado un cubo 13x13x13.8 (Ver Referencias al final del Trabajo)

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761167 El objetivo básico de este juego de ingenio es restaurar el cubo a su condición ori-
ginal. Se deben utilizar las diferentes rotaciones que el cubo permite, en cada uno de
sus lados, para ir llevando cada pieza de éste, a su correcta ubicación, logrando así
que cada cara sea de un único color.

Se eligió trabajar con el cubo de Rubik ya que consideramos que es un tema intere-
sante y aplicable a la programación lineal junto con herramientas de Simulación.
Además, se contaba con la información necesaria para hacer el modelo matemático y
la experiencia de una aficionada de SpeedCubing (Que es la actividad de armar el
Cubo de Rubik cronometrado).

1.1 Objetivos a cumplir por la Investigación Operativa

Se sabe que la programación lineal utiliza modelos matemáticos, estadísticos y algo-
ritmos para modelar y resolver problemas complejos, determinando así la solución
óptima y mejorando la toma de decisiones. Así, a través de la disciplina de la Investi-
gación Operativa, se puede definir formalmente el problema, llegando a formular un
modelo matemático que represente la realidad del problema planteado (Optimización
para el armado del Cubo Rubik).

Una vez modelado el sistema, se dispone varias herramientas para su resolución y
posterior análisis y/o ajuste, tales como el Método Simplex. En este caso, se usará un
Software de aplicación (WinQSB3) que nos servirá de apoyo para plantearlo desde el
Método Simplex.

De este modo, poder encontrar alguna secuencia lógica que logre la cantidad de
movimientos mínimos para armar el cubo de Rubik. Es decir, que para un cubo están-
dar (3x3x3) y para una mezcla determinada, se deberá encontrar la secuencia óptima
para llegar a un cubo ordenado.

Tras finalizar este Trabajo, se conocerá la solución óptima matemáticamente de la

menor cantidad de movimientos para resolver el cubo.

2 Modelización del problema presentado

Consideraciones del Modelo General

Después de haber evaluado exhaustivamente la modelización del problema en las pri-
meras instancias del Trabajo de investigación, se descartó la posibilidad de tener coe-
ficientes económicos distintos a 1 (Uno) ya que, por la naturaleza de la definición de
las variables de estudio, no se encontró una relación entre ellas que se corresponda
siempre a una posible resolución (Solve) de una mezcla (Scramble).

Cada mezcla elegida cumple con las normativas de WCA4 (Fueron generadas con
el cronometro1). Cada mezcla oficial tiene al menos 27 movimientos, con lo cual se
tuvo en cuenta este mínimo para facilitar el análisis matemático del problema. Se cal-

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761168 culó los movimientos de cada cara de las mezclas presentadas, verificando que el total
de movimientos esté incluido en esta restricción.

El método Fridrich propone resolver el Cubo de Rubik de la siguiente manera:

1. Cruz: Hay que armar una cruz en una cara, haciendo coincidir los centros con
los lados de cada una de las aristas. La cara elegida generalmente es la cara
Blanca.

2. F2L (First two layers): Luego, hay que colocar cada una de las esquinas en su
ubicación correcta y su arista correspondiente. Así, ya se tiene correctamente
armadas la primera capa y la segunda capa.

3. OLL (Orientation of the Last Layer): Se debe armar la cara completa de arriba.

En este caso, la cara opuesta al blanco es la cara Amarilla.

4. PLL (Permutation of the Last Layer): Ordenar las piezas de la última capa.

La cantidad mínima de movimientos de cada uno de los pasos a seguir para resol-
ver el Cubo de Rubik se determinó en base a las recomendaciones estadísticas de
quienes resuelven el cubo con un tiempo promedio de 20 segundos (Los llamados
“Sub20”) y la cantidad de movimientos de cada uno de los algoritmos para resolver
esos pasos. Para ello, se consideró también el promedio de la cantidad de movimien-
tos para hacer cada paso, de una persona que hizo el cubo en 86 movimientos; otra, en
60 movimientos y otra, en 43 movimientos.

La información estadística mencionada anteriormente es en base a un promedio de
resolución de cada parte del método Fridrich de quienes se tomaron muestras (3 per-
sonas con distinto promedio de tiempo de resolución, es decir que cada uno tiene su
manera de resolver el cubo siempre en base a los algoritmos del método Fridrich; uno
más rápido que otro, pero todos utilizan el método Fridrich) y en base a las buenas
estrategias y la habilidad del solver (Quien resuelve el cubo cronometrado) para resol-
verlo en menor tiempo un caso de Cruz, F2L, OLL o PLL.

En las restricciones, se consideró la cantidad mínima de movimientos para cada

una las combinaciones de las caras opuestas y de las caras adyacentes.

Debido a que, mediante el modelo, no se podía plantear que la combinación de la
solución fuera efectivamente un cubo ordenado fue necesaria la utilización no solo de
Software de la materia WinQSB3, sino también la ayuda del Software de simulación
Cube Explorer 5.12 HTM2, diseñado especialmente para, a partir de una mezcla, ob-
tener las resoluciones de menor cantidad de movimientos. En el mismo, se ingresa una
mezcla, y basándose en el mismo algoritmo antes nombrado, devuelve las soluciones
algorítmicas de menor cantidad movimientos. Lo que se hizo fue contar por cada color
para facilitar nuestro análisis (Dando entre 20 y 31 movimientos para las mezclas ele-
gidas).

La resolución de los modelos presentados en este Trabajo es en base al promedio
de las secuencias de menor cantidad de movimientos que aporta el programa de simu-
lación, que utiliza algoritmos del método Fridrich y otros atajos matemáticos. No se
citaron ya que se considera que no aporta datos relevantes a la resolución que brinda

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761169 el modelo matemático de la Programación Lineal (Resuelto por el WinQSB). Además,
representa una dificultad extra en modelizar cada secuencia posible bajo la Programa-
ción Lineal ya que se pierde claridad y simplicidad de entendimiento.

2.1 Condiciones del Modelo General

Para el desarrollo del Trabajo, se utilizará un cubo de Rubik estándar (3x3x3) que
posee 6 (seis) colores distintos. Está conformado por 12 aristas, 8 esquinas y 6 cen-
tros.

La mezcla (Scramble), utilizada en los torneos oficiales de la WCA (World Cube
Association), consta de aproximadamente 20 grupos de movimientos6 con la cara
blanca hacia arriba y con la cara verde hacia el frente. Cada grupo de movimientos
está formado por una letra y un número multiplicador. Entonces, para facilitar el aná-
lisis, los grupos de movimientos se desglosan y se cuentan como el total de movimien-
tos que representan. Es decir