Algoritmos Cubo Rubik

10
Aplicar secuencia de movimientos
}
3.5.5 Paso 6: Colocación de las esquinas en la cara Inferior
Este paso consiste en colocar las esquinas de la cara inferior
en su sitio aunque posiblemente queden giradas (como se ve
en el grafico). Puede observarse en el dibujo que cada
esquina está en su sitio aunque dos de ellas necesitan un
giro para que estén correctamente situadas.
Paraimplementar debimos hacer hincapié en cuántas piezas
están colocadas en el lugar correcto, puede pasar que
ninguna esquina esté bien ubicada; que sólo sea una o que
estén ubicadas bien las cuatro con lo que se saltea el paso.
Una vez identificado esto procedimos a aplicar las heurísticas según el caso, por ejemplo,
cuando no se encuentre ubicada ninguna esquina las posibles correcciones pasan porrotar
horizontal o diagonalmente las esquinas con respecto a la cara inferior. Cuando se encuentre que
solo una esquina esta posicionada correctamente, hallamos que solo basta rotar las esquinas
restantes en sentido horario o antihorario según convenga.
Cantidad de movimientos esperados: 11
Pseudocódigo del esquema general del Paso 6:
Posiciona correctamente las 4 esquinas en una llamada debacktracking
Identificar cantidad de esquinas bien posicionadas en cara inferior
Si (la cantidad no es 4)
{
Buscar secuencia de movimientos para posicionar las esquinas
Aplicar secuencia de movimientos
}
3.5.6 Paso 7: Orientación de las esquinas en la cara Inferior
En este paso se orientan las esquinas. Puede ocurrir que
estén bien orientadas cero, una o dos esquinas y en cada
caso seubican de dos en dos una o dos veces. También
puede ocurrir que el cubo ya halla quedado armado.
Al implementar encontramos que los movimientos
necesarios para realizar este paso son los de mayor longitud
ya que es difícil manipular el cubo sin perder lo que hemos
armado hasta este momento. Una vez que identificamos en
cual de las posibles situaciones nos encontramos se aplica la
secuencia demovimientos correspondiente.
Cantidad de movimientos esperados: 24
Pseudocódigo del esquema general del Paso 7:
Orienta correctamente 2 esquinas en una llamada de backtracking
Identificar cantidad de esquinas bien orientadas en cara inferior
Si (la cantidad no es 4)
{
Buscar secuencia de movimientos para orientar las esquinas
Aplicar secuencia de movimientos
}
11
3.5.7 Promedio GeneralA partir de una muestra aleatoria de 500 configuraciones diferentes del cubo pudimos
encontrar que la esperanza matemática (o promedio) para este algoritmo es de 101 pasos
aproximadamente.
3.6 Algoritmo Experto
El algoritmo que se utiliza aquí es uno de los más rápidos para resolver el cubo de Rubik. Este
método es debido entre otros, a Jessica Fridrich [4] y el mismo consiste en resolver elcubo en 4
pasos. Resulta entonces muy complejo, ya que utiliza una combinación de varios algoritmos que
permiten minimizar la solución. A continuación se describen los pasos.
3.6.1 Paso 2: Orientación de la capa Superior y Media
Esta etapa es equivalente al paso 2 y al paso 3 del algoritmo
principiante, con la diferencia que los pasos se realizan
simultáneamente, por lo tanto se ahorra grancantidad de
movimientos.
Al implementar se nos presentaron 22 casos diferentes, sin
contar reflexiones1, según las posiciones de aristas y
esquinas a acomodar. Por lo que el primer objetivo va a ser
identificar en cual de todos los casos nos encontramos
mirando la orientación y posición de una arista, en un
principio, y luego de su respectiva esquina. Una vez
cumplido esto se aplica lasecuencia de pasos correspondiente. Como se ve en el dibujo, las
aristas centrales y las esquinas se van acomodando de a pares por lo que resulta evidente que
este proceso se realiza 4 veces.
Cantidad de movimientos esperados: 4x7
3.6.2 Paso 3: Orientación de la capa Inferior
Se comienza en esta etapa con la cara inferior. Se debe
lograr que esta cara quede de un único color por lo que se...