Voy a interpretar que esto significa que quieres un solo conjunto de movimientos que, si se ejecutan en un cubo de Rubik, darán como resultado un cubo resuelto en algún momento durante el proceso .
En ese caso, la respuesta es sí.
Antecedentes:
Las acciones que puede realizar en un cubo de Rubik forman un grupo en composición.
- ¿Cuáles son los acertijos más comunes / difíciles que se preguntan en las entrevistas?
- En un Cubo de Rubik, ¿hay un algoritmo que si sigues repitiendo llegarás a una solución en algún momento?
- Cómo aprender a resolver un cubo de Rubik con el método Fridrich
- Cómo hacer un Sudoku difícil que tenga una solución única
- ¿Alguien puede dibujar un patrón que cubra todos los rompecabezas de 3 * 3 puntos con 6 o 7 líneas?
Este es el subgrupo de [matemáticas] S_ {48} [/ matemáticas] (el grupo simétrico de 48 elementos) generado por las rotaciones de la cara: [matemáticas] \ {F, B, U, D, L, R \} [/ matemática], que representan los giros en sentido horario de las caras frontal, posterior, superior, inferior, izquierda y derecha desde una perspectiva predefinida. Llamaremos al grupo [matemáticas] G [/ matemáticas].
Este grupo define una “acción de grupo” en el conjunto de todos los estados posibles del cubo, que llamaremos [math] X [/ math]. Eso significa que cada elemento de [matemáticas] G [/ matemáticas] define un mapa que asigna cada estado a otro estado.
La cardinalidad de [matemáticas] G [/ matemáticas] (número de elementos en el grupo) es [matemáticas] 2 ^ {27} 3 ^ {14} 5 ^ 37 ^ 211 [/ matemáticas]. Este es también el número de estados en los que puede estar un cubo de Rubik.
Prueba:
Deje [math] x_0 [/ math] ser el estado resuelto. Para cualquier estado, [math] x [/ math], [math] x [/ math] es accesible desde [math] x_0 [/ math] mediante algún conjunto finito de movimientos. De lo contrario, no sería un posible estado del cubo. Cada conjunto finito de movimientos se puede representar como una secuencia de elementos de [matemáticas] \ {F, B, U, D, L, R \} [/ matemáticas] y, por lo tanto, es un elemento de [matemáticas] G [/ matemáticas] . Esto forma un surjection [math] G \ to X [/ math], lo que implica que para cada posible estado del cubo, hay al menos un elemento de [math] G [/ math].
Para cualquier [matemática] g \ en G, x \ en X [/ matemática], si [matemática] g * x = x [/ matemática] entonces [matemática] g [/ matemática] debe ser la identidad, indicada [matemática] e [/ matemáticas]. Esto se debe a que el efecto aleatorio de la acción del grupo es independiente del estado actual, por lo que si asigna un estado a sí mismo, asignará todos los estados a sí mismos. Si [matemáticas] g, h \ en G [/ matemáticas] y [matemáticas] g * x = h * x [/ matemáticas], entonces [matemáticas] x = g ^ {- 1} g * x = g ^ {- 1} h * x [/ math], entonces [math] g ^ {- 1} h = e [/ math]. Así [matemáticas] g = h [/ matemáticas]. Eso significa que el mapa que describimos anteriormente no era solo una surjeción [matemática] G \ a [/ matemática] [matemática] X [/ matemática], era una biyección. Así [matemáticas] | G | = | X | [/ matemáticas].
El algoritmo:
Comience desde cualquier estado de cubo, [math] x [/ math]. Para cada elemento [math] g \ en G [/ math], aplique [math] g [/ math] y luego [math] g ^ {- 1} [/ math]. Para cada estado [matemática] x [/ matemática] hay una [matemática] r \ en G [/ matemática] tal que [matemática] r * x = x_0 [/ matemática], así que eventualmente llegarás a esa, resolviendo el cubo.
Este algoritmo está muy lejos de ser óptimo y nunca lo terminará en su vida, pero al menos hemos demostrado que existe.
Encontrar el algoritmo más rápido:
Este conjunto de todos los estados posibles del cubo se puede considerar como un gráfico dirigido con dos nodos que tienen un borde entre ellos si una sola rotación (elemento del conjunto [matemática] \ {F, B, U, D, L, R \} [/ math]) asigna uno al otro. Queremos una secuencia de elementos de [matemáticas] \ {F, B, U, D, L, R \} [/ matemáticas] que, sin importar dónde empecemos, eventualmente nos llevarán a [matemáticas] x_0 [/ matemáticas] . Si la secuencia pierde algún nodo, entonces hay un punto de partida tal que el nodo perdido es [math] x_0 [/ math], por lo que necesitamos la secuencia para visitar cada nodo y queremos que vuelva a visitar los nodos con la menor frecuencia posible. Dado que [matemática] F ‘[/ matemática], girar la cara frontal en sentido antihorario en lugar de hacerlo en sentido horario, lleva la misma cantidad de tiempo que girarlo en sentido horario, podemos reemplazar el gráfico dirigido con un gráfico no dirigido.
Cada uno de estos bordes está “coloreado” según la cara que rote.
Al girar todo el cubo se formará una acción de grupo en el conjunto [matemática] \ {F, B, U, D, L, R \} [/ matemática], intercambiando los colores. Todo el grupo de rotación de cubos es mucho más simple, ya que es el subconjunto de [math] S_8 [/ math] generado por [math] \ {H, V \} [/ math] (rotaciones horizontales y verticales). Teniendo en cuenta esto, podemos reducir aún más la coloración, lo que significa que solo necesitamos una secuencia de colores en lugar de giros.
Si hay un camino hamiltoniano en el gráfico de 6 regular con [matemáticas] 2 ^ {27} 3 ^ {14} 5 ^ 37 ^ 211 [/ matemáticas] y ese camino hamiltoniano tiene una naturaleza suficientemente repetitiva con respecto a nuestra coloración, puede haber un algoritmo que se pueda ejecutar en [math] 2 ^ {27} 3 ^ {14} 5 ^ 37 ^ 211-1 [/ math] movimientos. No ganará ninguna competencia de velocidad en cubos, pero tal vez una competencia de matemáticas.
EDITAR:
Mirando las otras respuestas, empiezo a darme cuenta de que me dejé llevar por las matemáticas.
Así que aquí está el TLDR:
Sí, lo hay, pero encontrarlo es increíblemente difícil y hacerlo realmente llevaría demasiado tiempo.
EDIT2: Gracias a Joshua Bloch por señalar que alguien ya descubrió que hay un camino hamiltoniano a través del espacio estatal y lo construyó. Un circuito hamiltoniano para el cubo de Rubik