En el Cubo de Rubik, ¿hay algún algoritmo que si sigues repitiendo llegarás a una solución en algún momento?

Answer 1

¡Si!

¿Sabemos de qué se trata?

No.

Piénsalo de esta manera: si giras un lado del cubo de Rubik completamente, de modo que llegues a la misma posición en la que estabas, entonces recorrerías 4 permutaciones del cubo. La repetición de algoritmos más complejos (como la permanente T) pasará por más y más permutaciones.

Esto significa, muy probablemente, que existe un algoritmo (MUY largo), que recorre todas las 43.252.003.274.489.856.000 configuraciones posibles de un cubo de Rubik.

Teniendo en cuenta que este algoritmo probablemente tenga miles de millones de movimientos largos, no sería práctico incluso usar un algoritmo, ya que le tomaría EXTREMADAMENTE mucho tiempo resolverlo, y mucho menos memorizar tal cosa.

PD: El algoritmo que recorre todas las combinaciones se llama Algoritmo del diablo.

Answer 2

¡No!

Seguir el mismo conjunto de movimientos te llevará a la misma posición con la que comenzaste .

Por lo tanto, si el cubo está en el estado resuelto y sigue cualquier secuencia particular de movimientos y repítala lo suficiente (la cantidad de veces que tendrá que repetir la secuencia cambia con la secuencia que ha utilizado) la cantidad de veces que tendrá que volver a la posición con la que comenzó, que en este caso será El estado resuelto .

(Fuente: notación del cubo de Rubik – Cómo leer las letras de rotación)

Ejemplo 1: en el estado resuelto, siga la secuencia R2 [matemáticas] 2 [/ matemáticas] veces (es decir, haga RRRR ) y volverá a la misma posición

Ejemplo 2: en el estado resuelto, siga la secuencia RUR’U ‘ [matemáticas] 6 [/ matemáticas] veces (es decir, haga RUR prima U prima) y volverá a la misma posición

Ejemplo 3: en el estado resuelto, siga la secuencia RU2R’U ‘ [matemáticas] 12 [/ matemáticas] veces y volverás a la misma posición

No puede haber una secuencia única que pueda llevar el cubo de Rubik al estado resuelto desde cualquier estado aleatorio (codificado) .

Answer 3

Si. Pero no quieres esperar tanto. Cualquier algoritmo que debe funcionar simplemente por repetición tiene que pasar por todas las permutaciones necesarias para pasar de cualquier posición inicial al cubo resuelto; lo que significa que eventualmente debe llevar el cubo en órbita a través de todas sus posiciones posibles. ¿Puedes esperar tanto?

El grupo de cubos no es cíclico; ninguna permutación independiente del color (es decir, ninguna secuencia de movimientos definida solo por la orientación del cubo) lo genera todo. Sin embargo, usted dijo “algoritmo”, que es más general. Ciertamente, puede trabajar sistemáticamente a través de todas las posibilidades utilizando dos generadores. Sin embargo, esto es bastante grave.

Mucho más plausible es una solución basada en un mayor número de generadores con relaciones mutuas más simples.

Trabaja incluso en permutaciones de esquinas. Para cada paso, trabaje a través de permutaciones uniformes de bordes, luego intercambie dos esquinas y dos bordes, luego trabaje hacia atrás invirtiendo las permutaciones de bordes hasta que regrese a la permutación original de esquinas, con el intercambio adicional de esquinas y bordes, que puede ahora retroceda antes de pasar a la próxima permutación de esquinas.

Desafortunadamente, no es fácil hacerlo mucho mejor que esto, porque ninguna permutación del cubo tiene un orden superior (ninguno superior a 1260). Es probable que la confianza inteligente en soluciones mínimas sea confusamente poco práctica. Deberá tener generadores de los grupos de esquinas y grupos de bordes separados, y variantes de la permutación swap-two-corners-and-swap-two-edge para revertir su efecto cuando se envuelva alrededor de la secuencia de permutaciones de borde (esto podría ser hecho un poco más fácil, si es redundante, al completar el ciclo de permutaciones de borde entre estos intercambios).

Sin embargo, repito que ninguna solución “debe funcionar a través de todo” es remotamente práctica.

Incluso sin repeticiones, hay [matemáticas] 2 ^ 27.3 ^ 14.5 ^ 3.7 ^ 2.11 [/ matemáticas] posiciones del cubo, sin contar las rotaciones centrales. Creo que tu cubo se desintegrará en astillas de plástico mucho antes de que termines un cubo completo, o incluso mueras de vejez.

Answer 4

En términos de secuencias de movimiento , ese sería el algoritmo del diablo .

Existe una secuencia de movimiento que atraviesa cada uno de los 43 quintillones de estados del Cubo. Tal recorrido se llama Circuito Hamiltoniano. Puede encontrar detalles en el sitio web de Cuber Bruce: Un circuito hamiltoniano para el Cubo de Rubik

Es más fácil visualizar esto con un cubo de 2, y esta página web ayuda con eso: el algoritmo del diablo

Lo anterior atrae a los matemáticos.

En informática, un algoritmo no es una secuencia de movimiento, sino, en términos generales, la esencia abstracta e interesante de un programa. En ese sentido, los programas implementan algoritmos. Y un algoritmo para resolver un cubo de Rubik es un método de solución.

Esto atrae a los ingenieros:

Entonces, los robots que resuelven los Cubos de Rubik usan programas que implementan un Método de solución, es decir, un Algoritmo. Por ejemplo:

Utiliza un programa que implementa el algoritmo de Herbert Kociemba.

Answer 5

Conozco el algoritmo Probablemente no sea el mejor algoritmo pero funciona. Me lleva unos 80 movimientos resolverlo. Pero los movimientos nunca son iguales. Todo depende del estado inicial del cubo y de mi suerte durante el proceso.

Aquí están los pasos principales del algoritmo que uso.

1. Capa superior 4 cubos intermedios (2 colores).
2. Capa superior 4 cubos de esquina (3 colores).
3. Capa de en medio.
4. Capa inferior 4 cubos de esquinas (3 colores).
5. Capa inferior 4 cubos intermedios (2 colores).

Los pasos 4 y 5 son mucho más difíciles que otros.

Hay dos formas de hacer trampa sin conocer el algoritmo. La más obvia es arrancar los colores y pegarlos de la manera correcta. La otra forma es separar el cubo y luego armarlo de la manera correcta. Para hacer esto, debe comprender lo siguiente.

Hay tres tipos de cubitos de 1 color, 2 colores y 3 colores. Es importante entender que los cubos de 1 color en el medio de cada cara no van a ninguna parte, solo se dan la vuelta. Y determinan el color de toda la cara. Si tiene el cubo de un color blanco medio, toda la cara se volverá blanca. Y el pequeño cubo de dos colores en el borde entre las futuras caras blancas y rojas tendrá dos colores: blanco y rojo. Del mismo modo, determinamos las posiciones de los cubos de 3 colores.

Con esto en mente, podemos determinar las posiciones futuras de todos los cubitos. Esto nos permite desmontar el cubo y ensamblarlo correctamente. No se necesita conocimiento del algoritmo para eso. Para impresionar a tus amigos, lleva el cubo desordenado a otra habitación, gira un lado 45 grados y, usando el otro extremo de una cuchara, saca cuatro cubos de color medio. Ellos simplemente saldrán. Entonces el cubo se vendrá abajo. Entonces verá el núcleo del cubo. Luego lo ensamblas correctamente. Primero colocas cubos de 3 colores, luego 2 cubos de colores. El último paso del montaje es el mismo que el primero del desmontaje. La capa se gira 45 grados y los cuatro cubos de 2 colores se ajustan en último lugar.

Answer 6

Que yo sepa, no. Sin embargo, hay estrategias para resolverlo, cada lucha puede resolverse en 20 movimientos o menos, y aquí hay un pequeño dato interesante: si comienzas resuelto y haces una serie de movimientos, repitiendo esa misma serie (No importa lo que sea) eventualmente lo volverá a resolver. Por ejemplo, si vas hacia arriba, hacia la izquierda, hacia abajo, hacia adelante, hacia atrás, hacia arriba, hacia la izquierda, hacia abajo, hacia adelante, hacia atrás una y otra vez, eventualmente volverás a un cubo resuelto.

Answer 7

No.

Cada algoritmo (como en una serie fija de vueltas del cubo) volverá a la posición inicial en 1280 repeticiones (o algún divisor del mismo). Como hay más de 1280 posiciones posibles del cubo, ningún algoritmo único, repetido indefinidamente, resolverá todas las posiciones iniciales posibles.

Answer 8

No.

El ciclo más largo posible en un cubo 3 × 3 tiene una longitud de 1260.

Sin embargo, es posible recorrer todas las posiciones, ya que es posible pasar de cualquier posición legal a cualquier otra posición legal.

Answer 9

Depende de cómo interpretemos la pregunta.

Definitivamente hay una secuencia de movimientos que, si se siguen, pasarán por todos los arreglos posibles. Podemos enumerar los posibles arreglos y sabemos que hay una secuencia de 20 movimientos (permitiendo que los medios turnos cuenten como 1 movimiento) que nos llevará de cualquier posible arreglo a cualquier otro posible arreglo. Combine todo esto y tendrá una secuencia única que garantiza que pasará por todos los arreglos posibles.

Si no se consideran los arreglos intermedios en una secuencia de movimientos, de modo que usamos una secuencia única de movimientos y los repetimos una y otra vez mirando los arreglos al final de cada secuencia completa (ignorando los arreglos intermedios), entonces el número máximo de arreglos es posible alcanzar es, creo, 1260.

El máximo de 1260 consiste en:

a. Tres ciclos de esquinas, incluido un giro de una de esas esquinas (creando un ciclo de 9).

si. Cinco ciclos de esquinas (que también deben incluir un giro, creando un ciclo de 15).

C. Dos ciclos de bordes que incluyen un giro de uno de esos bordes (creando un ciclo de 4).

re. Siete ciclos de aristas (al menos un ciclo de 7, el factor adicional de dos de un posible giro no nos ayuda).

mi. Debe haber necesariamente otros dos ciclos irrelevantes de bordes que pueden incluir o no un giro.

La duración total del ciclo es el MCM de 9, 15, 4 y 7, que es 1260.

Estoy bastante seguro de que 1260 es el máximo posible.

Answer 10

Solo bastará un conjunto de movimientos que pasen el cubo a través de cada permutación posible. En algún momento a través de este conjunto, se garantiza que el cubo se resolverá, sin necesidad de repetirlo. Por supuesto, llevaría una gran cantidad de tiempo llevarlo a cabo, por lo que sería inutilizable en la práctica.

Answer 11

No, ni un solo algoritmo.

Pero se ha demostrado en numerosas ocasiones que un mínimo de tres algoritmos resolverán cualquier cubo.

Muestro eso ya que mi método solo necesita tres: dos para las esquinas (todos los casos, a veces solo necesita uno) y uno para todos los nervios.

Answer 12

Actualmente, es un triste no. No importa qué algoritmo haga, terminará en su posición inicial. Pero, dado que el cubo tiene tantos algoritmos posibles como codificación, ¿quién puede decir que algún día no podemos encontrar uno?