Manera de calcular el giro de tétrada total de un cubo de rubik
Estoy trabajando en una implementación del algoritmo de Thistlewaite para resolver un cubo de Rubik y ahora me enfrento al problema de los giros de tétrada. Gracias a esta respuesta , entiendo qué son y cómo reducen la cantidad de estados en la fase 3, pero el problema que tengo es encontrar una manera de calcular el giro total de tétrada de un cubo solo desde su estado.
La forma en que estoy implementando este algoritmo no es con una búsqueda en amplitud y, por lo tanto, no puedo simplemente usar la condición más fuerte que se encuentra aquí y aquí para saber si terminé con la etapa 3, ya que eso no es útil para mí. La forma en que lo estoy haciendo es precalcular tablas de búsqueda y mirar en ellas para saber cómo resolver un estado determinado. Por esa razón, necesito caracterizar completamente la información necesaria para distinguir los diferentes estados de la etapa 3. Ya tengo tétradas de esquina, cortes de bordes y paridad, lo último que necesito es una forma de expresar el giro de tétrada de un estado (o cualquier información equivalente). Lo mejor sería simplemente poder dar un valor entre 0, 1 o 2 y usarlo para describir el giro total.
Espero que mi pregunta sea clara, y si no lo es, siéntase libre de hacer preguntas en los comentarios, haré todo lo posible para explicarlo mejor.
Respuestas
Es bastante difícil extraer esta información directamente de las ubicaciones actuales de las esquinas. Con mucho, la forma más fácil es tratar de resolver esas piezas de las esquinas usando solo medio giro (mientras ignoras las piezas de los bordes) y ver qué tan lejos llegas.
Por ahora, supondré que las piezas de las esquinas ya están ubicadas en sus órbitas cuádruples correctas {UFR, UBL, DFL, DBR} y {UFL, UBR, DFR, DBL}. Puedes resolver las piezas de una tétrada muy fácilmente, no más de medio giro por cada pieza, como máximo 3 movimientos en total. Por ejemplo, resuelva DBR usando como máximo uno de {D2, B2, R2}, luego DFL usando como máximo uno de {F2, L2} y finalmente UBL usando {U2} si es necesario, lo que también deja resuelto a UFR.
Luego resuelve una parte de la segunda tétrada, por ejemplo DBL, usando una de las secuencias de movimiento {F2 L2 F2 U2, U2 F2 U2 L2, L2 U2 L2 F2}. Estas secuencias de movimientos realizan un intercambio doble en las cuatro piezas de la segunda tétrada y son las únicas permutaciones posibles que mantienen fija la primera tétrada.
Esto deja tres piezas sin resolver, {UFL, UBR, DFR}. Estos pueden estar en cualquiera de 3!=6 permutaciones. Estas 6 posibilidades representan el giro de la tétrada en combinación con la paridad de la permutación, por lo que si asigna esta permutación a un número del 0 al 5, ha codificado tanto la paridad de la permutación como el giro de la tétrada en un solo número.
Para el algoritmo Thistlethwaite, probablemente desee codificar una posición arbitraria de la tercera etapa del algoritmo. Esto tiene que hacerse de manera consistente, con lo que quiero decir que si dos posiciones diferentes son llevadas a la cuarta etapa por la misma secuencia de movimientos (es decir, después de aplicar la secuencia de movimientos a esas posiciones, ambas se vuelven solucionables usando solo medias vueltas), entonces esas dos posiciones deben tener la misma codificación para la etapa 3.
Presumiblemente, su programa enumera las ubicaciones de las esquinas del cubo en un orden fijo particular. Por ejemplo, puede tener una matriz de longitud 8 que represente las ubicaciones en el orden
UFR , UFL, UBL , UBR, DFR, DFL , DBL, DBR .
He resaltado en negrita aquellas ubicaciones que representan una de las tétradas, aquellas en el índice 0, 2, 5, 7 en la matriz. Es posible que haya elegido una convención de orden diferente en su programa, pero el método es el mismo.
Suponga que ahora tiene una posición arbitraria del cubo de la etapa 3, alguna permutación aleatoria de esas 8 esquinas, por ejemplo:
UBR, UBL , DBR , DFR, DFL , UFR , UFL, DBL.
Una forma simple y consistente de separar las piezas en dos tétradas es separar literalmente los dos tipos de piezas sin cambiar su orden relativo:
UBL , DBR , DFL , UFR
UBR, DFR, UFL, DBL.
Y luego colóquelos en la matriz de almacenamiento, en orden, cada uno en su conjunto correcto de ubicaciones de tétradas. Entonces, el primer conjunto entra en los índices 0,2,5,7, el otro en los índices 1,3,4,6.
UBL , UBR, DBR, DFR, UFL, DFL , DBL, UFR .
Ahora puede aplicar la técnica de resolución que expliqué al principio, para terminar con una codificación consistente de las posiciones tetrad twist y parity.
Lo anterior supone que usas una sola forma estandarizada para representar el cubo, y aplicas movimientos a eso. En su lugar, es posible que desee mantener las dos listas separadas de las piezas de la tétrada como una representación simplificada de esta posición, y permutarlas directamente a medida que las resuelve para extraer la codificación de torsión + paridad.
Puede echar un vistazo a algunos de los programas en este antiguo concurso de programación de cubos , aunque no estoy seguro de que sean muy útiles ya que están escritos para ser concisos, no para ser inteligibles.