¿Existe (o puede existir) un algoritmo general para resolver cubos de Rubik de cualquier dimensión?

Question

Me encanta resolver el cubo de Rubik (el usual en 3D). Pero, una conferencia de Matt Parker en el Royal Institute (Enlace de YouTube) me llevó a una aplicación que puede simular un cubo de Rubik en cuatro dimensiones. Pero desafortunadamente era tan complejo que pronto me aburrí al no poder resolverlo.

El sitio web del cubo en 4D: http://superliminal.com/cube/cube.htm

Después de eso, ¡hoy también encontré una aplicación que puede simular un cubo en 5D!

El sitio web del cubo en 5D: http://www.gravitation3d.com/magiccube5d/

Entonces, mis dos preguntas son:

1. ¿Existe un algoritmo general (que no sea de fuerza bruta) que se pueda usar para resolver un cubo bien desordenado de cualquier dimensión (aunque puede que no sea muy eficiente, pero aún así no es una simple búsqueda en todo el espacio disponible de secuencias de movimientos) ? [Punto modificado después de leer la respuesta de @RavenclawPrefect :D]
2. Matemáticamente, ¿qué es común en todos estos cubos y "hipercubos"?

NOTA: Por dimensiones me refiero a la dimensión física y no al número de filas de piezas en una cara del cubo. Entonces, un cubo de cuatro dimensiones es un cubo en las dimensiones x, y, z, δ donde $\hat x, \hat y, \hat z, \hat \delta$ son vectores unitarios mutuamente ortogonales en las dimensiones respectivas.
Por ejemplo, así es como se mueve el cubo de 4D mencionado anteriormente: https://miro.medium.com/max/2552/1*ga32DoV_Hc6e8t6PC1hFHw.gif

---

Addendum:
Lista de recursos que pueden ayudar a encontrar una respuesta a esta pregunta:

• Resolviendo el cubo de Rubik y otros puzzles de permutación

Answer 1

El problema algorítmico es un caso especial de "prueba de membresía constructiva en grupos de permutaciones": dados una permutación (etiquetas cada cara del cubo con un número, luego cada rotación de la capa corresponde a una permutación de los números, al igual que el estado mixto), escríbelo como un producto de generadores. Esto no se preocupa por la dimensión del cubo en el que trabajas, solo obtienes más y más etiquetas.

La solución genérica al problema se llama algoritmo Schreier-Sims (https://en.wikipedia.org/wiki/Schreier–Sims_algorithm). Sin embargo, en su forma ingenua, produce soluciones muy largas (longitud >100k para el cubo $3\times3\times 3$).

Se pueden agregar heurísticas (básicamente sembrar previamente con productos cortos como generadores "extra"), ver por ejemplo: https://doi.org/10.1006/jsco.1998.0202. Con tales heurísticas, el cubo $3\times3\times 3$ obtiene soluciones de longitud $\sim 40-100$, por lo que es un orden de magnitud demasiado grande, pero no astronómicamente. Se pueden ajustar las heurísticas (utilizar más memoria) para obtener mejores soluciones, aunque la única forma (conocida) de encontrar una solución más corta es por fuerza bruta.

Answer 2

Aquí hay un algoritmo muy simple (y muy ineficiente):

El conjunto de secuencias finitas de movimientos es contable, por lo que podemos enumerar tales secuencias $s_1, s_2, \ldots$ (específicamente, podemos hacerlo de manera computable). Luego ejecuta el siguiente algoritmo:

i=1
while el cubo no esté resuelto:
  execute la secuencia de movimientos s_i
  if el cubo está resuelto:
    return s_i
  else
    deshacer la secuencia de movimientos s_i
  i = i+1

Dado que cada secuencia finita de movimientos aparece en nuestra enumeración, este algoritmo siempre terminará en tiempo finito (y de hecho, para un rompecabezas fijo con un número finito de configuraciones, su tiempo de ejecución necesariamente estará limitado).

Para un algoritmo más "razonable", es necesario establecer algún tipo de límite en el tiempo de ejecución; este es al menos exponencial en la dimensión del cubo, lo cual sospecho que es muy subóptimo.

Editar: Esta respuesta parece haber recibido mucha atención por ser la primera en la pregunta, pero las otras respuestas a esta pregunta son significativamente más interesantes; ¡vota positivo por ellas en su lugar!

Answer 3

En primer lugar, ¿estás familiarizado con la solución basada en conmutadores para rompecabezas de permutaciones generales? Seguramente puedes hacer lo mismo aquí para cada dimensión y tamaño específicos, y probablemente puedas generalizarlo a una dimensión y tamaño arbitrarios con algo de esfuerzo. Se trata de encontrar conmutadores adecuados para cada una de las órbitas y mostrar que las paridades pueden resolverse. Aquí, una órbita es un conjunto S de posiciones tal que cualquier pieza en una posición en S se puede mover a cada posición en S pero no a ninguna posición fuera de S. (En términos grupales, la acción del grupo de todos los movimientos del cubo en el cubo es transitiva).

Aunque no he pensado en los detalles, la idea general sería demostrar lo siguiente:

1. Existe un algoritmo para hacer que para cada órbita S las piezas en S estén en alguna permutación par.

2. Para cada órbita S, hay algún conmutador de 3-ciclos en algunas posiciones P, Q, R en S y algún algoritmo para mover piezas en posiciones dadas A, B, C en S a P, Q, R respectivamente. Esto te permite realizar cualquier permutación par en las piezas en S.

3. Para cada órbita S, creo que puedes definir la orientación de piezas en cada órbita de forma que cada giro de cara no cambie su orientación total, y hay algún conmutador que solo cambia la orientación de las piezas en algunas posiciones P, Q por +1 y -1 respectivamente, y algún algoritmo para mover piezas en posiciones dadas A, B en S a P, Q respectivamente. Esto sería suficiente para fijar la orientación de todas las piezas en S.

Una vez establezcas los puntos anteriores, simplemente aplícalos en ese orden para resolver el cubo. Por ejemplo, no es difícil probar los puntos anteriores para el cubo 3D de tamaño arbitrario, donde usas los giros de capa para lograr el primer punto (corrección de paridad para todas las órbitas), incluso si es un poco confuso. Creo que se generaliza a dimensiones arbitrarias de manera similar.