Matemáticas del cubo de rubik

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de julio de 2021; las comprobaciones requieren 17 ediciones .

matemáticas del cubo de rubik

Archivos multimedia en Wikimedia Commons

Matemáticas del Cubo de Rubik es un conjunto de métodos matemáticos para estudiar las propiedades del Cubo de Rubik desde un punto de vista matemático abstracto. Esta rama de las matemáticas estudia algoritmos de ensamblaje de cubos y los evalúa. Basado en teoría de grafos , teoría de grupos, teoría de computabilidad y combinatoria .

Hay muchos algoritmos diseñados para transferir el Cubo de Rubik de una configuración arbitraria a la configuración final (el cubo ensamblado). En 2010, se probó rigurosamente que no más de 20 vueltas de las caras son suficientes para transferir el Cubo de Rubik de una configuración arbitraria a una configuración ensamblada (a menudo llamada "ensamblaje" o "solución") [1] . Este número es el diámetro del gráfico de Cayley del grupo de cubos de Rubik [2] . En 2014 se demostró que 26 movimientos son siempre suficientes para resolver el Cubo de Rubik usando solo giros de 90° de las caras [3] .

Un algoritmo que resuelve un rompecabezas en el menor número posible de movimientos se llama algoritmo Dios .

Notación

Este artículo utiliza la "notación Singmaster" [4] [5] desarrollada por David Singmaster y publicada por él en 1981 para indicar la secuencia de rotación de las caras de un cubo de Rubik de 3×3×3 .

Las letras representan la rotación de 90° en el sentido de las agujas del reloj de las caras izquierda ( izquierda ), derecha ( derecha ), frontal ( frontal ), posterior ( posterior ), superior ( arriba ) e inferior ( abajo ), respectivamente. Los giros de 180° se indican agregando un 2 a la derecha de la letra, o agregando un superíndice 2 a la derecha de la letra. Una rotación de 90° en sentido antihorario se indica agregando un guión ( ′ ) o agregando un superíndice -1 a la derecha de la letra. Entonces, por ejemplo, las entradas y son equivalentes, así como las entradas y . $L,R,F,B,U,D$ $L^{2}$ $L2$ $L'$ $L^{{-1}}$

Métricas del gráfico de configuración

Hay dos formas más comunes de medir la longitud de una solución ( métrica ). La primera forma: un giro de la solución se considera un giro de la cara de 90 ° ( cuarto de vuelta métrico , QTM ). De acuerdo con el segundo método, también se considera una media vuelta de la cara para 1 movimiento ( métrica de giro de cara , FTM , a veces se denota por HTM - métrica de media vuelta ). Por lo tanto, F2 (girar la cara frontal 180°) debería contarse como dos movimientos en la métrica QTM o 1 movimiento en la métrica FTM [6] [7] .

Para indicar en el texto la longitud de la secuencia para la métrica utilizada, se utiliza la notación [8] [9] [10] , que consiste en los números del número de movimientos y la primera letra minúscula de la designación de la métrica. 14f significa "14 movimientos en la métrica FTM" y 10q significa "10 movimientos en la métrica QTM". Para indicar que el número de movimientos es el mínimo en una métrica determinada, se utiliza un asterisco : 10f* denota la optimización de la solución en 10 movimientos FTM.

Grupo de cubos de Rubik

El cubo de Rubik se puede ver como un ejemplo de un grupo matemático .

Cada una de las seis rotaciones de las caras del cubo de Rubik se puede considerar como un elemento del grupo simétrico del conjunto de 48 etiquetas del cubo de Rubik que no son los centros de las caras. Más específicamente, se pueden marcar las 48 etiquetas con números del 1 al 48 y asignar a cada uno de los movimientos un elemento del grupo simétrico . $\{F,B,U,D,L,R\}$ $S_{{48}}$

Entonces el grupo del cubo de Rubik se define como el subgrupo generado por seis rotaciones de caras: $GRAMO$ $S_{{48}}$

G=\langle F,B,U,D,L,R\rangle .

El orden del grupo es [11] [12] $GRAMO$

|G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\,252\,003 \,274\,489\,856\,000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11.

Cada una de las configuraciones se puede resolver en no más de 20 movimientos (si contamos cualquier giro de la cara como un movimiento) [1] . $4{,}325\cdot 10^{19}$

El orden más alto de un elemento en es 1260. Por ejemplo, la secuencia de movimientos debe repetirse 1260 veces antes de que el cubo de Rubik vuelva a su estado original [13] . $GRAMO$ $(R\ U^{2}\ D^{{\principal}}\ B\ D^{{\principal}})$

Algoritmo de Dios

La búsqueda del algoritmo de Dios comenzó a más tardar en 1980, cuando se abrió una lista de correo para los fanáticos del Cubo de Rubik [6] . Desde entonces, matemáticos, programadores y aficionados han buscado encontrar el algoritmo de Dios para que en la práctica, en el mínimo número de movimientos, se resuelva el cubo de Rubik. Relacionado con este problema estaba el problema de determinar el número de Dios, el número de movimientos que siempre es suficiente para completar el rompecabezas.

En 2010, el programador de Palo Alto Thomas Rokiki, el profesor de matemáticas de Darmstadt Herbert Kotsemba, el matemático de la Universidad de Kent Morley Davidson y el ingeniero de Google Inc. John Dethridge demostró que un cubo de Rubik de cualquier estado desmontado se puede montar en 20 movimientos. En este caso, cualquier giro de la cara se consideraba un movimiento. La cantidad de cómputo fue de 35 años de tiempo de CPU donados por Google [1] [14] [15] . Los datos técnicos sobre el rendimiento y la cantidad de computadoras no fueron revelados. La duración de los cálculos fue de varias semanas [16] [17] [18] .

En 2014, Thomas Rockicki y Morley Davidson demostraron que el cubo de Rubik se puede resolver en no más de 26 movimientos sin el uso de giros de 180°. El volumen de cálculos fue de 29 años de tiempo de procesador en el centro de supercomputación de Ohio [3] .

Límites inferiores para el número de Dios

Es fácil mostrar que hay configuraciones solucionables [19] que no pueden resolverse en menos de 17 movimientos en la métrica FTM o 19 movimientos en la métrica QTM.

Esta estimación se puede mejorar teniendo en cuenta identidades adicionales: la conmutatividad de las rotaciones de dos caras opuestas (LR = RL, L2 R = R L2, etc.) Este enfoque permite obtener un límite inferior para el número de Dios en 18f o 21q [20] [21 ] .

Esta estimación ha sido durante mucho tiempo la más conocida. Se sigue de una prueba no constructiva, ya que no indica un ejemplo específico de una configuración que requiera 18f o 21q para construir.

Una de las configuraciones para las que no se pudo encontrar una solución corta fue el llamado " superflip " o "12-flip". En "Superflip" todos los cubos de esquina y borde están en sus lugares, pero cada cubo de borde está orientado de manera opuesta [22] . El vértice correspondiente al superflip en el gráfico del cubo de Rubik es un máximo local: cualquier movimiento desde esta configuración reduce la distancia a la configuración inicial. Esto sugirió que el superflip está a la distancia máxima de la configuración inicial. Es decir, un superflip es un máximo global [23] [24] [25] .

En 1992, Dick T. Winter encontró una solución al superflip en 20f [26] . En 1995, Michael Reed demostró lo óptimo de esta solución [27] , como resultado de lo cual el límite inferior para el número de Dios se convirtió en 20 FTM. En 1995, Michael Reid descubrió la solución al "superflip" en 24q [28] . Jerry Bryan [29] probó lo óptimo de esta solución . En 1998, Michael Reed encontró una configuración cuya solución óptima era 26q* [30] .

Límites superiores para el número de Dios

Para obtener un límite superior para el número de Dios, basta con especificar cualquier algoritmo de ensamblaje de rompecabezas que consista en un número finito de movimientos.

Los primeros límites superiores para el número de Dios se basaron en algoritmos "humanos" que constaban de varias etapas. Sumando las estimaciones anteriores para cada una de las etapas, fue posible obtener una estimación final del orden de varias decenas o cientos de movimientos.

Probablemente, la primera estimación concreta desde arriba fue dada por David Singmaster en 1979. Su algoritmo de ensamblaje permitió ensamblar el rompecabezas en no más de 277 movimientos [16] [31] . Singmaster informó más tarde que Alvin Berlekamp , John Conway y Richard Guy desarrollaron un algoritmo de ensamblaje que no requería más de 160 movimientos. Pronto, un grupo de "cubistas de Cambridge de Conway", que estaban compilando una lista de combinaciones para una cara, encontraron un algoritmo de 94 vías [16] [32] . En 1982, la revista Kvant publicó una lista de combinaciones que permiten resolver el Cubo de Rubik en 79 movimientos [33] .

Algoritmo de Thistlethwaite

A principios de la década de 1980, el matemático inglés Morvin Thistlethwaite desarrolló un algoritmo que mejoró significativamente el límite superior. Los detalles del algoritmo fueron publicados por Douglas Hofstadter en 1981 en Scientific American . El algoritmo se basó en la teoría de grupos e incluyó cuatro etapas.

Descripción

Thistlethwaite usó varios subgrupos de longitud 4

G=G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq G_{3}\supseteq G_{4}=\{1\},

dónde

$G_{0}=\langle L,R,F,B,U,D\rangle .$

Este grupo es el mismo que el del cubo de Rubik . Su orden es [34] [35]

GRAMO

{\dfrac {8!\cdot 3^{8}}{3}}\cdot {\dfrac {12!\cdot 2^{12}}{2}}\cdot {\dfrac {1}{ 2}}=43\,252\,003\,274\,489\,856\,000.

$G_{1}=\langle L^{2},R^{2},F,B,U,D\rangle .$

Este subgrupo incluye todas las configuraciones que se pueden resolver sin el uso de rotaciones de los lados izquierdo o derecho de ±90°. su orden es

{\dfrac {8!\cdot 3^{8}}{3}}\cdot 12!\cdot {\dfrac {1}{2}}=21\,119\,142\,223\, 872\,000.

$G_{2}=\langle L^{2},R^{2},F^{2},B^{2},U,D\rangle .$

Este subgrupo incluye todas las configuraciones que se pueden resolver siempre que se prohíban las rotaciones de ±90° de las cuatro caras verticales. su orden es

8!\cdot (8!\cdot 4!)\cdot {\dfrac {1}{2))=19\,508\,428\,800.

$G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle .$

En este subgrupo se incluyen todas las configuraciones que se pueden resolver utilizando solo giros de 180° (medias vueltas). Fue llamado el "grupo de cuadrados" (grupo de cuadrados). su orden es

(4!\cdot 4)\cdot {\dfrac {4!\cdot 4!\cdot 4!}{2))\cdot 1=663\,552.

$G_{4}=\{1\}.$

Este subgrupo incluye una única configuración inicial.

En la primera etapa, una configuración dada arbitrariamente del grupo se reduce a una configuración que se encuentra en el subgrupo . El objetivo de la segunda etapa es llevar el cubo a la configuración en el subgrupo sin utilizar rotaciones de las caras izquierda y derecha de ±90°. En la tercera etapa, el cubo de Rubik se reduce a una configuración perteneciente al grupo , mientras que las rotaciones de las caras verticales de ±90° están prohibidas. En la cuarta etapa final, el Cubo de Rubik se ensambla completamente girando las caras 180°. $GRAMO$ $G_{1}$ $G_{2}$ $G_{3}$

Los índices de subgrupos en son 2048, 1082565, 29400 y 663552, respectivamente. $[G_{i}:G_{{i+1}}]$ $i=0,1,2,3$

Para cada una de las cuatro familias de clases laterales derechas, se crea una tabla de búsqueda , cuyo tamaño coincide con el índice del subgrupo en el grupo . Para cada clase de adyacencia de subgrupo, la tabla de búsqueda contiene una secuencia de movimientos que traduce cualquier configuración de esta clase de adyacencia en una configuración que se encuentra en el propio subgrupo . $G_{i}/G_{{i+1}}$ $T_{yo}$ $G_{{yo+1}}$ $Soldado americano}$ $Soldado americano}}$ $T_{yo}$ $Soldado americano}$

Para reducir el número de entradas en las tablas de búsqueda, Thistlethwaite usó movimientos preliminares simplificados. Originalmente recibió una puntuación de 85 movimientos. Durante 1980, esta puntuación se redujo a 80 movimientos, luego a 63 y 52 [16] [36] . Los alumnos de Thistlethwaite realizaron un análisis completo de cada una de las etapas. Los valores máximos en las tablas son 7, 10, 13 y 15 FTM golpes respectivamente. Dado que 7 + 10 + 13 + 15 = 45, el Cubo de Rubik siempre se puede resolver en 45 FTM [25] [37] [38] movimientos .

Conde Schreier

El gráfico de Schreier es un gráficoasociado a un grupo, un grupo electrógeno y un subgrupo. Cada vértice del gráfico de Schreier es una clase lateral derechapara algunos. Los filos de Count Schreier son pares. $S(G,X,H)$ $GRAMO$ $X=\{x_{i}|i\en I\}$ $H\subconjunto G$ $Hg=\{hg|h\in H\}$ $g\in g$ $(Hg,Hgx_{i})$

Cada una de las cuatro etapas del algoritmo de Thistlethwaite es un recorrido transversal del gráfico de Schreier , donde es el conjunto generador del grupo . $S_{i}(G_{i},X_{i},G_{{i+1}})$ $X_{yo}$ $Soldado americano}$

Por lo tanto, la estimación superior de 45 movimientos es

{\ estilo de visualización \ suma _ {i = 0} ^ {3} \ épsilon (v_ {i}),}

dónde

\epsilon(v_{i})

es la excentricidad del vértice correspondiente a la clase lateral unitaria .

v_{i}\en S_{i}

G_{{yo+1}}

La noción de gráfico de Schreier se utilizó en los trabajos de Radu [39] , Kunkle y Cooperman [40] .

Modificaciones del algoritmo de thistlethwaite

En diciembre de 1990, Hans Kloosterman usó una versión modificada del método de Thistlethwaite para probar la suficiencia de 42 movimientos [1] [20] [41] .

En mayo de 1992, Michael Reid demostró que 39f o 56q eran suficientes [42] . En su modificación se utilizó la siguiente cadena de subgrupos:

$G_{0}=\langle U,F,R,L,B,D\rangle$
$G_{1}=\langle U,R,F\rangle$
$G_{2}=\langle U,R^{2},F^{2}\rangle$
$G_{3}=\{1\}$

Unos días más tarde, Dick T. Winter bajó su puntaje FTM a 37 movimientos [43] .

En diciembre de 2002, Ryan Hayes desarrolló una versión del algoritmo de Thistlethwaite diseñada para resolver rápidamente el cubo de Rubik [44] .

Algoritmo de Kotsemba de dos fases

El algoritmo de Thistlethwaite fue mejorado en 1992 por Herbert Kotsemba, un profesor de matemáticas de Darmstadt.

Descripción

Kotsemba redujo el número de pasos del algoritmo a dos [20] [45] [46] :

$G_{0}=\langle U,D,L,R,F,B\rangle$
$G_{1}=\ángulo U,D,L^{2},R^{2},F^{2},B^{2}\ángulo$
$G_{2}=\{1\}$

Se puede obtener una descripción visual del grupo si se hace el siguiente marcado [20] [47] : $G_{1}$

Marque todas las etiquetas U y D con un signo "+".
Las etiquetas F y B en los elementos de borde FR , FL , BL y BR están marcadas con un "-".
Deje todas las demás etiquetas sin marcar.

Entonces todas las configuraciones del grupo tendrán el mismo marcado (coincidiendo con el marcado en el cubo ensamblado). $G_{1}$

La solución consta de dos etapas. En la primera etapa, la configuración dada se traduce mediante una secuencia de movimientos en alguna configuración . En otras palabras, la tarea de la primera etapa es restaurar el marcado correspondiente a la configuración inicial, ignorando los colores de las etiquetas. $x\en G_{0}$ $s_{1}$ $x^{{\principal}}\en G_{1}$

En la segunda etapa, la configuración se transfiere mediante una secuencia de movimientos a la configuración inicial. En este caso, no se utilizan las rotaciones de las caras laterales de ±90°, por lo que el marcado se guarda automáticamente. $x^{{\principal}}\en G_{1}$ $s_{2}$

Pegar secuencias de movimientos es una solución subóptima para la configuración original [20] [46] [48] . $s_{1}$ $s_{2}$

Soluciones subóptimas alternativas

El algoritmo de Kotsemba no se detiene después de encontrar la primera solución. Las soluciones óptimas alternativas en la primera etapa pueden conducir a soluciones más cortas en la segunda etapa, lo que reducirá la longitud total de la solución. El algoritmo continúa buscando también soluciones no óptimas en la primera etapa en orden de aumentar su longitud [20] [46] [48] .

Funciones de implementación

Para buscar soluciones en cada una de las dos etapas, se utiliza el algoritmo IDA* con funciones heurísticas basadas en los costos de resolver las subtareas correspondientes [48] .

La tarea de la primera etapa se reduce a encontrar un camino en el espacio con tres coordenadas desde el rotulado con coordenadas ( x 1 , y 1 , z 1 ) hasta el rotulado (0, 0, 0) [49] :

Orientación x 1 de ocho elementos de esquina (2187 valores)
La orientación y 1 de doce elementos de borde (2048 valores)
Disposición z 1 de cuatro elementos de borde FR , FL , BL y BR (495 valores)

Considere tres subproblemas para encontrar un camino desde el marcado ( x 1 , y 1 , z 1 ) al marcado ( x 1 ', y 1 ', 0), ( x 1 ', 0, z 1 '), (0, y1 ', z1 ' ) . El valor de la función heurística h 1 utilizada en la primera etapa es igual al costo máximo de resolver estos subproblemas. Los costes de resolución de las subtareas se calculan previamente y se almacenan en forma de bases de datos con plantillas [50] [51] .

La tarea de la segunda etapa se reduce a encontrar un camino en el espacio con tres coordenadas desde la configuración ( x 2 , y 2 , z 2 ) hasta la configuración (0, 0, 0) [52] :

Permutación x 2 ocho elementos de esquina (40320 valores)
Permutación y 2 de los ocho elementos de borde de las caras superior e inferior (40320 valores)
Permutación z 2 de los cuatro elementos de borde de la capa intermedia (24 valores)

Considere tres subproblemas para encontrar un camino desde la configuración ( x 2 , y 2 , z 2 ) a la configuración ( x 2 ', y 2 ', 0), ( x 2 ', 0, z 2 '), (0, y 2 ', z2 ') . El valor de la función heurística h 2 utilizada en la segunda etapa es igual al costo máximo de resolver estos subproblemas.

El algoritmo utiliza optimizaciones adicionales destinadas a aumentar el rendimiento y reducir la memoria ocupada por las tablas [20] [45] [46] [53] .

Implementaciones de software

Cube Explorer es una implementación de software del algoritmo para el sistema operativo Windows. Los enlaces de descarga están en el sitio web de Herbert Kotsemba [54] . En 1992, en una PC Atari ST con 1 MB de memoria y una frecuencia de 8 MHz, el algoritmo permitió encontrar una solución de no más de 22 movimientos en 1-2 minutos [20] [45] . En una computadora moderna, Cube Explorer hace posible encontrar una solución en unos segundos en no más de 20 movimientos para una configuración dada arbitrariamente [45] .

Hay una versión en línea del algoritmo [55] .

Análisis

En 1995, Michael Reed demostró que la primera y la segunda fase del algoritmo de Kotsemba podrían requerir como máximo 12 y 18 movimientos (FTM), respectivamente. De esto se deduce que el Cubo de Rubik siempre se puede resolver en 30 movimientos. Un análisis adicional mostró que 29f o 42q [25] [56] siempre es suficiente .

Algoritmo de Korff

El algoritmo de Kotsemba le permite encontrar rápidamente soluciones cortas y subóptimas. Sin embargo, puede llevar un tiempo considerable probar la optimización de la solución encontrada. Se necesitaba un algoritmo especializado para encontrar soluciones óptimas.

En 1997, publicó un algoritmo que le permitía resolver de forma óptima configuraciones arbitrarias del Cubo de Rubik. Diez configuraciones seleccionadas al azar se resolvieron en no más de 18 movimientos FTM [57] [58] .

El algoritmo de Korff en sí funciona de la siguiente manera. En primer lugar, se determinan subproblemas lo suficientemente simples como para realizar una enumeración completa. Se utilizaron las siguientes tres subtareas [25] :

El estado del rompecabezas solo está determinado por los ocho cubos de las esquinas, las posiciones y orientaciones de los bordes se ignoran.
El estado del rompecabezas está determinado por seis de los 12 dados de borde, los otros dados se ignoran.
El estado del rompecabezas está determinado por los otros seis dados de borde.

El número de movimientos necesarios para resolver cada uno de estos subproblemas es un límite inferior del número de movimientos necesarios para completar la solución. Una configuración dada arbitrariamente del Cubo de Rubik se resuelve usando el algoritmo IDA* , que usa esta estimación como una heurística. Los costes de resolución de las subtareas se almacenan en forma de bases de datos con plantillas [50] [57] .

Aunque este algoritmo siempre encontrará soluciones óptimas, no determina directamente cuántos movimientos pueden ser necesarios en el peor de los casos.

Una implementación del algoritmo en C se puede encontrar en [59] .

Otras mejoras

En 2005, la puntuación QTM de Michael Reid mejoró a Silviu Radu a 40q [60] . En 2006, Silviu Radu demostró que el cubo de Rubik se puede resolver en 27f [39] o 35q [61] .

En 2007, Daniel Kunkle y Gene Cooperman usaron una supercomputadora para demostrar que todas las configuraciones no resueltas pueden resolverse en no más de 26 movimientos FTM. La idea era llevar el Cubo de Rubik a uno de los 15.752 subconjuntos de configuraciones de cuadrados , cada uno de los cuales se puede resolver finalmente con algunos movimientos adicionales. La mayoría de las configuraciones se resolvieron de esta forma en no más de 26 movimientos. Las configuraciones restantes se sometieron a un análisis adicional, que mostró que también se pueden resolver en 26 movimientos [40] [62] .

En 2008, Thomas Rokicki publicó una prueba computacional de la solución del rompecabezas FTM de 25 movimientos [63] . En agosto de 2008, Rokiki anunció una prueba de solvencia en 23f [64] . Más tarde, esta estimación mejoró a 22f [65] . En 2009, también logró demostrar la solvencia en 29 movimientos QTM [66] .

En 2010, Thomas Rokicki, Herbert Kotsemba, Morley Davidson y John Dethridge anunciaron una prueba de que cualquier configuración del cubo de Rubik se puede resolver en un máximo de 20 movimientos en la métrica FTM [1] [14] . Junto con la estimación más baja conocida anteriormente de 20f*, esto demostró que el número de Dios del Cubo de Rubik en la métrica FTM es 20.

En agosto de 2014, Rockiki y Davidson anunciaron que el número de Dios para el cubo de Rubik en la métrica QTM es 26 [3] [67] .

Buscar antípodas

La configuración del cubo de Rubik, que se encuentra a la máxima distancia de la configuración inicial, se denomina antípoda. Cualquier antípoda en la métrica FTM tiene una solución óptima en 20f*, y cualquier antípoda en la métrica QTM tiene una solución óptima en 26q* [3] [68] .

Se sabe que hay millones de antípodas en la métrica FTM [69] . Una de esas configuraciones es el "superflip". Por el contrario, en la métrica QTM, actualmente solo se conoce una configuración antípoda (sin contar las configuraciones obtenidas de ella por rotaciones), la llamada. superflip compuesto por cuatro puntos [30] [67] [68] [70] . Solo se conocen dos configuraciones a una distancia de 25q* de la configuración inicial y unas 80 mil configuraciones a una distancia de 24q* [3] [69] .

Estimaciones asintóticas

En 2011, se demostró que el número de Dios del cubo n × n × n era Θ( n 2 / log( n )) [71] [72] .

Otros rompecabezas

Cubo vacío

Void Cube es un cubo de Rubik de 3x3x3 sin piezas centrales.

La longitud de la solución óptima para un " superflip vacío " en la métrica FTM es 20 [73] [74] , lo que demuestra que se necesitan 20 movimientos. Dado que Void Cube es un problema debilitado [50] del Rubik's Cube, la prueba existente de la suficiencia de 20 movimientos para el Rubik's Cube [1] se aplica al Void Cube. Por lo tanto, el número de Dios del Cubo del Vacío en la métrica FTM es 20.

Cubo 4×4×4

El número de configuraciones del rompecabezas 4×4×4 ( Ing. Rubik's Revenge ) es [75]

{\frac {8!\times 3^{7}\times 24!^{2}}{4!^{6}\times 24}}=7401196841564901869874093974498574336000000000\approx 7{,}40\times 10^ {45}.

Métricas 4×4×4

Hay varias formas de determinar la métrica de un cubo de 4x4x4. Esta sección utiliza las siguientes métricas:

qs (cuarto de corte): se considera un giro para rotar cualquiera de las 12 capas del rompecabezas en ±90°;
qw (cuarto de giro): se considera que una vuelta rota cualquier bloque exterior (es decir, solo caras o caras con varias capas adyacentes en una fila ) en ±90°;
qb (cuarto de bloque): se considera un giro para rotar cualquier bloque exterior o interior (es decir, cualquier secuencia de capas paralelas consecutivas ) ±90° en relación con el resto del rompecabezas;
hs , hw , hb : Igual que las 3 métricas anteriores, excepto que también se permiten rotaciones de 180°.

La longitud de la solución óptima de una configuración arbitraria en la métrica qb no es mayor que en las métricas qw o qs , ya que todos los movimientos de las otras dos métricas q están permitidos en la métrica qb . Lo mismo se aplica a las métricas h.

Estimaciones del número de cubo de Dios 4×4×4

En 2006-2007 Bruce Norskog hizo un análisis de 5 pasos del cubo de 4x4x4, similar al análisis de 4 pasos realizado por Thistlethwaite para el cubo de Rubik de 3x3x3. El análisis produjo límites superiores de 82 movimientos en la métrica hw [76] , 77 movimientos en la métrica hs [77] [78] y 67 movimientos en la métrica hb [76] .

En 2011, Thomas Rokiki, basado en varias ideas existentes, determinó límites inferiores para el número de Dios en seis métricas para rompecabezas cúbicos con tamaños de 2×2×2 a 20×20×20 [79] .

En 2013, Shuang Chen (陈霜) redujo su puntaje hw de 82 a 57 turnos [80] .

En 2015, Thomas Rokicki confirmó la puntuación máxima de 57 hw y recibió nuevas puntuaciones máximas de 56 hs y 53 hb [81] . Unos días más tarde, Shuang Chen (陈霜) logró obtener cotas superiores de 55 hw y 53 hs redefiniendo los pasos de la prueba [82] [83] .

En la tabla se muestran las puntuaciones superiores e inferiores conocidas actuales para el dado 4×4×4 en varias métricas:

Estimaciones del número de Dios del cubo 4x4x4

métrica	hora	cómo	media pensión	qs	qq	qb
estimación más baja	32	35	29	37	41	33
estimación superior	53	55	53	?	?	?

Megaminx

Megaminx es el análogo más simple del cubo de Rubik en forma de dodecaedro. El número de configuraciones del Megaminx de 12 colores es 1.01·10 68 .

En 2012, Herbert Kotsemba determinó un límite inferior para el número de Dios de Megaminx en 45 rotaciones de cara en cualquier ángulo, o 55 rotaciones en un ángulo de ± 72 ° [84] [85] .
En 2016, Herbert Kotsemba mejoró la estimación más baja del número de Dios para Megaminx, aumentándolo a 48 rotaciones de cara en cualquier ángulo [86] .

Véase también

Notas

↑ 1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; y Dethridge, J. El número de Dios es 20 . Consultado el 19 de julio de 2013. Archivado desde el original el 21 de julio de 2013.
↑ Según el sistema de generadores, consistente en giros de las caras de ±90° y 180°.
↑ 1 2 3 4 5 Rokicki, T. y Davidson, M. El número de Dios es 26 en la métrica de cuarto de vuelta . Consultado el 4 de julio de 2015. Archivado desde el original el 7 de julio de 2015.
↑ Joyner, 2002 , pág. 7.
↑ Lecciones morales y matemáticas de un cubo de Rubik // Nuevo científico. - mil novecientos ochenta y dos.
↑ 1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. El cubo: la guía definitiva para el rompecabezas más vendido del mundo: secretos, historias, soluciones . - 2009. - S. 26. - 142 p.
↑ Jaap Scherphuis. Matemáticas útiles . Métricas (inglés) (enlace descendente) . Consultado el 17 de julio de 2013. Archivado desde el original el 24 de noviembre de 2012.
↑ Jerry Bryan. Convención de notación (27 de mayo de 2006). Consultado el 28 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014. (indefinido)
↑ David Singmaster. Cúbico Circular . - 1982. - Edicion. 5 y 6 . — Pág. 26 .
↑ Jaap Scherphuis. Estadísticas de rompecabezas . Consultado el 17 de julio de 2013. Archivado desde el original el 21 de junio de 2013.
↑ Schönert, Martin Analizando el cubo de Rubik con GAP . Fecha de acceso: 19 de julio de 2013. Archivado desde el original el 20 de enero de 2013.
↑ Jaap Scherphuis. Cubo de Rubik 3x3x3 (inglés) (enlace no disponible) . Consultado el 19 de julio de 2013. Archivado desde el original el 28 de julio de 2013.
↑ Joyner, 2008 , págs. 93 , 108.
↑ 1 2 Herbert Kociemba. Algoritmo de dos fases y algoritmo de Dios: el número de Dios es 20 (inglés) (enlace no disponible) . Fecha de acceso: 23 de julio de 2013. Archivado desde el original el 2 de mayo de 2013.
↑ Tomas Rokicki, Herbert Kociemba, Morley Davidson y John Dethridge. El diámetro del grupo del cubo de Rubik es veinte // SIAM J. Matemáticas discretas.. - 2013. - Vol. 27, núm. 2.- Pág. 1082-1105. -doi : 10.1137/ 120867366 .
↑ 1 2 3 4 Rik van Grol. La búsqueda del número de Dios . Horizontes matemáticos (noviembre de 2010). Consultado el 26 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014.
↑ Stefan Edelkamp, Stefan Schrodl. Búsqueda heurística: teoría y aplicaciones. - Morgan Kaufmann Publishers , 2012. - 712 p. — ISBN 978-0-12-372512-7 .
↑ SIAM J. Matemáticas discretas, 27(2), 1082–1105 . Consultado el 19 de noviembre de 2013. Archivado desde el original el 3 de diciembre de 2019. (indefinido)
↑ Una configuración "resolvible" es una configuración que se puede traducir a una compilada. Dado que la gráfica del cubo de Rubik no está dirigida, se deduce que cualquier configuración obtenida a partir de la secuencia arbitraria original de movimientos es decidible. Pero hay configuraciones irresolubles. Por ejemplo, si uno de los vértices del cubo se gira 120° en el estado ensamblado, se obtendrá una configuración irresoluble.
↑ 1 2 3 4 5 6 7 8 V. Dubrovsky, A. Kalinin. Noticias de cubología // Kvant . - 1992. - Nº 11 . - S. 52-56 .
↑ Jaap Scherphuis. Matemáticas útiles . Algoritmo de Dios (inglés) (enlace no disponible) . Consultado el 17 de julio de 2013. Archivado desde el original el 24 de noviembre de 2012.
↑ Michael Reid. Página del cubo de Rubik de Michael Reid . Posiciones simétricas M (inglés) (24 de mayo de 2005) . Consultado el 17 de julio de 2013. Archivado desde el original el 6 de julio de 2015.
↑ David Singmaster. Cúbico Circular . - 1982. - Edicion. 5 y 6 . — Pág. 24 .
↑ Joyner, 2002 , pág. 149.
↑ 1 2 3 4 Stefan Pochmann. Análisis de métodos de resolución humanos para el cubo de Rubik y rompecabezas similares (tesis de diploma ) . Archivado desde el original el 9 de noviembre de 2014.
↑ Dik T. Invierno. Algoritmo de Kociemba (inglés) (18 de mayo de 1992). Consultado el 17 de julio de 2013. Archivado desde el original el 15 de julio de 2013.
↑ Michael Reid. superflip requiere 20 vueltas de cara ( 18 de enero de 1995). Consultado el 17 de julio de 2013. Archivado desde el original el 8 de julio de 2013.
↑ Michael Reid. superflip (inglés) (10 de enero de 1995). Consultado el 17 de julio de 2013. Archivado desde el original el 19 de junio de 2014.
↑ Jerry Bryan. Qturn Lengths of M-Symmetric Positions ( 19 de febrero de 1995). Consultado el 17 de julio de 2013. Archivado desde el original el 20 de junio de 2014.
↑ 12Michael Reid . superflip compuesto con four spot (inglés) (2 de agosto de 1998). Consultado el 4 de julio de 2015. Archivado desde el original el 4 de octubre de 2015.
↑ L. A. Kaluzhnin, V. I. Sushchansky. Transformaciones y permutaciones. - M. , 1985. - S. 143. - 160 p.
↑ David Singmaster. Apuntes sobre el Cubo Mágico de Rubik (neopr.) . — Editores de Enslow, 1981. - S. 30 .
↑ V. Dubrovski. El algoritmo del cubo mágico // Kvant . - 1982. - Nº 7 . - S. 22-25 .
↑ El orden de este y los siguientes tres grupos se calcula como el producto de tres factores que indican, respectivamente, la cantidad de configuraciones de esquinas resolubles, la cantidad de configuraciones de bordes resolubles y la restricción general de "paridad" en la configuración resoluble.
↑ Jaap Scherphuis. Subgrupos de cubos . Subgrupos generados por movimientos faciales (ing.) (enlace no disponible) . Fecha de acceso: 19 de julio de 2013. Archivado desde el original el 20 de enero de 2013.
↑ Mark Longridge. Mejoras progresivas en la resolución de algoritmos . Consultado el 28 de julio de 2013. Archivado desde el original el 9 de octubre de 2013.
↑ V. Dubrovski. Matemáticas del Cubo Mágico // Kvant . - 1982. - Nº 8 . - S. 22-27, 48 .
↑ Jaap Scherphuis. Algoritmo de 52 movimientos de Thistlethwaite . Consultado el 17 de julio de 2013. Archivado desde el original el 28 de julio de 2013.
↑ 12 silviu . Rubik se puede resolver en 27f . Foro Dominio del Cubo (1 de abril de 2006). Consultado el 20 de julio de 2013. Archivado desde el original el 27 de agosto de 2013. (indefinido)
↑ 1 2 Kunkle, D.; Cooperman, C. (2007). "Veintiséis movimientos son suficientes para el cubo de Rubik" (PDF) . Actas del Simposio Internacional sobre Computación Simbólica y Algebraica (ISSAC '07) . Prensa ACM. Archivado (PDF) desde el original el 2019-02-18 . Consultado el 17 de julio de 2013 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ Michael Reid. un límite superior en el número de dios (inglés) (29 de abril de 1992). Fecha de acceso: 17 de julio de 2013. Archivado desde el original el 24 de agosto de 2013.
↑ Michael Reid. nuevo límite superior (inglés) (22 de mayo de 1992). Consultado el 19 de julio de 2013. Archivado desde el original el 24 de agosto de 2013.
↑ Dik T. Invierno. Los cálculos corregidos ya están hechos. (inglés) (28 de mayo de 1992). Consultado el 19 de julio de 2013. Archivado desde el original el 20 de junio de 2014.
↑ Ryan Heise. El algoritmo humano de Thistlethwaite . Fecha de acceso: 19 de julio de 2013. Archivado desde el original el 2 de agosto de 2016.
↑ 1 2 3 4 Herbert Kociemba. Detalles del algoritmo de dos fases . Consultado el 20 de julio de 2013. Archivado desde el original el 2 de mayo de 2013.
↑ 1 2 3 4 Jaap Scherphuis. Desconcierto informático . Algoritmo de Kociemba . Consultado el 23 de julio de 2013. Archivado desde el original el 25 de junio de 2013.
↑ Herbert Kociemba. El Subgrupo H y sus clases laterales . Consultado el 23 de julio de 2013. Archivado desde el original el 22 de mayo de 2013.
↑ 1 2 3 Herbert Kociemba. El algoritmo de dos fases . Fecha de acceso: 23 de julio de 2013. Archivado desde el original el 2 de mayo de 2013.
↑ Biyección entre configuraciones y triples de coordenadas La copia archivada del 2 de mayo de 2013 en Wayback Machine está configurada de tal manera que el diseño objetivo de la primera etapa (es decir, cualquier configuración del grupo G 1 ) corresponde al triple (0 , 0, 0).
↑ 1 2 3 Stuart Russell, Peter Norvig. Recopilación de funciones heurísticas admisibles // Inteligencia artificial: un enfoque moderno = Inteligencia artificial: un enfoque moderno. - 2ª ed. - M. : Williams, 2006. - S. 170 - 173. - 1408 p. — ISBN 5-8459-0887-6 .
↑ Inglés. bases de datos de patrones . En la presentación del autor del algoritmo Copia de archivo fechada el 2 de mayo de 2013 en Wayback Machine - "tablas de poda".
↑ Debido a la limitación de paridad de la permutación de elementos, solo ocurre la mitad de todos los triples de coordenadas.
↑ Herbert Kociemba. Mesas de poda . Fecha de acceso: 23 de julio de 2013. Archivado desde el original el 2 de mayo de 2013.
↑ Herbert Kociemba. Descargar (inglés) . Consultado el 20 de julio de 2013. Archivado desde el original el 2 de mayo de 2013.
↑ Eric Dietz. Resuelve tu cubo en menos de 25 movimientos . Consultado el 20 de julio de 2013. Archivado desde el original el 9 de enero de 2022.
↑ Michael Reid. nuevos límites superiores (inglés) (7 de enero de 1995). Consultado el 19 de julio de 2013. Archivado desde el original el 24 de agosto de 2013.
↑ 1 2 Richard E. Korf. Búsqueda de soluciones óptimas para el cubo de Rubik utilizando bases de datos de patrones . — 1997.
↑ Arturo Fisher . Rubik's Reduced (inglés) , Popular Science (octubre de 1997), página 58.
↑ Michael Reid. Página del cubo de Rubik . Solucionador óptimo del cubo de Rubik (28 de octubre de 2006) . Consultado el 20 de julio de 2013. Archivado desde el original el 5 de julio de 2015. (indefinido)
↑ Silviu Radu, Un nuevo límite superior en el grupo de cubos de Rubik, arΧiv : math/0512485 .
↑ Silvio. Rubik se puede resolver en 35q . Foro Dominio del Cubo (22 de marzo de 2006). Consultado el 20 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014. (indefinido)
↑ Investigadores de la Universidad del Noreste resuelven el cubo de Rubik en 26 movimientos . Consultado el 20 de julio de 2013. Archivado desde el original el 23 de octubre de 2019. (indefinido)
↑ Tom Rokicki, Veinticinco movimientos son suficientes para el cubo de Rubik, arΧiv : 0803.3435 .
↑ rocoso. Veintitrés movimientos son suficientes . Foro Dominio del Cubo (29 de abril de 2008). Consultado el 20 de julio de 2013. Archivado desde el original el 27 de agosto de 2013. (indefinido)
↑ rocoso. Veintidós movimientos son suficientes (enlace no disponible) . Foro Dominio del Cubo (12 de agosto de 2008). Consultado el 20 de julio de 2013. Archivado desde el original el 5 de diciembre de 2011. (indefinido)
↑ rocoso. Veintinueve movimientos QTM son suficientes . Foro Dominio del Cubo (15 de junio de 2009). Fecha de acceso: 20 de julio de 2013. Archivado desde el original el 26 de julio de 2011. (indefinido)
↑ 1 2 Adam P. Goucher. Superflip compuesto con fourspot . Complex Projective 4-Space (25 de septiembre de 2015). Consultado el 23 de octubre de 2015. Archivado desde el original el 1 de febrero de 2016. (indefinido)
↑ 1 2 Jaap Scherphuis. Gráficas de Cayley . Distancias (inglés) . Consultado el 4 de julio de 2015. Archivado desde el original el 6 de julio de 2015.
↑ 1 2 Distancia conocida: 20 posiciones en la métrica de media vuelta. Distancia conocida: 24 posiciones o más en la métrica de cuarto de vuelta . Consultado el 4 de julio de 2015. Archivado desde el original el 29 de junio de 2015. (indefinido)
↑ Patrones bonitos Cubo de Rubik | Volteo de borde, punto | Superflip, Con 4 Puntos . Consultado el 4 de julio de 2015. Archivado desde el original el 5 de julio de 2015. (indefinido)
↑ Demaine, Erik D.; Demaine, Martín L.; Eisenstat, Sara; Lubiw, Anna y Winslow, Andrew (2011), Algoritmos para resolver cubos de Rubik, archivo iv : 1106.5736v1 [cs.DS].
↑ Larry Hardesty. Las matemáticas del cubo de Rubik . Una nueva investigación establece la relación entre el número de cuadrados en un rompecabezas tipo cubo de Rubik y el número máximo de movimientos necesarios para resolverlo . Oficina de noticias del MIT (29 de junio de 2011) . Consultado el 23 de julio de 2013. Archivado desde el original el 19 de septiembre de 2013.
↑ rocoso. Diámetro del cubo vacío de al menos 20 (métrico de giro de cara) . Foro Dominio del Cubo (19 de enero de 2010). Consultado el 28 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014. (indefinido)
↑ rocoso. Diámetro del cubo vacío al menos 20 (probablemente 20) . Speedsolve.com (19 de enero de 2010). Consultado el 28 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014. (indefinido)
↑ Jaap Scherphuis. La venganza de Rubik . Consultado el 28 de julio de 2013. Archivado desde el original el 27 de julio de 2013.
↑ 1 2 Bruce Norskog. Nuevos límites superiores: 82 giros giratorios, 67 giros en bloque . Foro Dominio del Cubo (13 de agosto de 2007). Consultado el 28 de julio de 2013. Archivado desde el original el 29 de mayo de 2014. (indefinido)
↑ Bruce Norskog. El 4x4x4 se puede resolver en 77 turnos de un solo corte . Foro Dominio del Cubo (26 de julio de 2007). Consultado el 28 de julio de 2013. Archivado desde el original el 29 de mayo de 2014. (indefinido)
↑ Bigger rubik cube binded (enlace descendente) . Proyecto Euler. Consultado el 28 de julio de 2013. Archivado desde el original el 29 de mayo de 2014. (indefinido)
↑ rocoso. Límites inferiores para nxnxn Cubos de Rubik (hasta n=20) en Six Metrics . Foro Dominio del Cubo (18 de julio de 2011). Consultado el 28 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014. (indefinido)
↑ SC. Resolviendo el 4x4x4 en 57 movimientos (OBTM) . Foro Dominio del Cubo (30 de septiembre de 2013). Consultado el 19 de noviembre de 2013. Archivado desde el original el 26 de noviembre de 2013. (indefinido)
↑ rocoso. Límites superiores de 4x4x4: 57 OBTM confirmados; 56 SST y 53 BT calculados. . Foro Dominio del Cubo (3 de marzo de 2015). Consultado el 1 de julio de 2015. Archivado desde el original el 29 de mayo de 2015. (indefinido)
↑ SC. 4x4x4 nuevo límite superior: 55 OBTM . Foro Dominio del Cubo (3 de julio de 2015). Consultado el 1 de julio de 2015. Archivado desde el original el 29 de mayo de 2015. (indefinido)
↑ SC. 4x4x4 nuevo límite superior: 53 SSTM . Foro Dominio del Cubo (3 de septiembre de 2015). Consultado el 1 de julio de 2015. Archivado desde el original el 29 de mayo de 2015. (indefinido)
↑ Herbert Kociemba. Megaminx necesita al menos 45 movimientos . Foro Dominio del Cubo (28 de febrero de 2012). Consultado el 28 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014. (indefinido)
↑ Herbert Kociemba. Límite inferior para Megaminx en htm y qtm . Speedsolve.com (3 de enero de 2012). Consultado el 28 de julio de 2013. Archivado desde el original el 9 de noviembre de 2014. (indefinido)
↑ Límite inferior para Megaminx en htm y qtm . Consultado el 2 de septiembre de 2016. Archivado desde el original el 17 de septiembre de 2016. (indefinido)

Lectura sugerida

V. Zalgaller, S. Zalgaller. Cubo articulado húngaro // Kvant . - 1980. - Nº 12 . - S. 17 - 21 . (Ruso)
V. Dubrovski. El algoritmo del cubo mágico // Kvant . - 1982. - Nº 7 . - S. 22-25 . (Ruso)
V. Dubrovski. Matemáticas del Cubo Mágico // Kvant . - 1982. - Nº 8 . - S. 22 - 27, 48 . (Ruso)
V. Dubrovski, A. Kalinin. Noticias de cubología // Kvant . - 1992. - Nº 11 . - S. 52 - 56 . (Ruso)
L. A. Kaluzhnin, V. I. Sushchansky. Transformaciones y permutaciones. - M. , 1985. - S. 143. - 160 p.
David Singmaster. Cúbico Circular . - 1981 - 1985.
David Singmaster, Alexander Frey. Manual de Matemáticas Cubik. — 1987.
David Joyner. Aventuras en la teoría de grupos: el cubo de Rubik, la máquina de Merlín y otros juguetes matemáticos . - Baltimore: Johns Hopkins University Press, 2002. - ISBN 0-8018-6947-1 .
David Joyner. Aventuras en la teoría de grupos: el cubo de Rubik, la máquina de Merlín y otros juguetes matemáticos . - Segunda edicion. - Prensa JHU, 2008. - 328 p. - ISBN 0-801-89726-2 , 978-0-801-89726-9.
ED Demaine, ML Demaine, S. Eisenstat, A. Lubiw, A. Winslow. Algoritmos para resolver cubos de Rubik // Apuntes de clase en informática. - 2011. - T. 6942 . - S. 689-700 . -doi : 10.1007 / 978-3-642-23719-5_58 .

Enlaces

Konstantin Knop. Cubo de Rubik: Asalto a la Fortaleza . Consultado el 20 de julio de 2013. Archivado desde el original el 20 de octubre de 2009. (Ruso)
Rik van Grol. La búsqueda del número de Dios . Horizontes matemáticos (noviembre de 2010). Consultado: 26 de julio de 2013.

Reimpreso en: Rik van Grol. La búsqueda del número de Dios // Los mejores escritos sobre matemáticas 2011 / Mircea Pitici, Freeman Dyson . - Prensa de la Universidad de Princeton , 2011. - P. 27-34. — 416 pág. - ISBN 1-400-83954-8 , 978-1-400-83954-4.

Jaap Scherphuis. La página del rompecabezas de Jaap . - Una selección de información sobre una variedad de acertijos y métodos para resolverlos. Consultado: 20 de julio de 2013.
Herbert Kociemba. Cube Explorer 5.01 (inglés) . — Página de inicio de Herbert Kotsemba. Descripción detallada de los algoritmos utilizados en el programa Cube Explorer. Consultado: 20 de julio de 2013.
Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. El número de Dios es 20 (inglés) . Consultado: 20 de julio de 2013.
Martín Schonert. Archivos de Cube Lovers convertidos a HTML . — Artículos de 1947 entre julio de 1980 y junio de 1996. Consultado el 20 de julio de 2013.
Marcos Longridge. Foro del Dominio del Cubo . — Discusiones sobre las matemáticas del cubo. Consultado: 20 de julio de 2013.
W.D. Joyner. Apuntes de clase sobre las matemáticas del cubo de Rubik (inglés) (enlace no disponible) . Consultado el 22 de julio de 2013. Archivado desde el original el 5 de septiembre de 2013.
Tomás Rokicki. Computers and the Cube (diapositivas) (inglés) (3 de noviembre de 2009). — MATH 78SI : Speedcubing: historia, teoría y práctica . Curso iniciado por estudiantes en Stanford (otoño de 2009). Consultado: 30 de julio de 2013.