¿Las matemáticas detrás de los rompecabezas de rotación?

Question

En el juego Machinarium, existe el siguiente rompecabezas en el que el objetivo es conseguir todos los puntos verdes de la zona verde girándolos a lo largo de cualquiera de los 3 círculos grabados en la placa de fondo. ( Aquí hay un vídeo que lo muestra en movimiento )

¿Hay alguna teoría detrás de este tipo de rompecabezas?

Edición: Y si lo hay, ¿hay alguna forma de aprovechar esa teoría para obtener una solución más eficiente que hacer clic al azar hasta llegar a una solución?

Answer 1

Este puzzle es un ejemplo de acción de grupo . En este caso, nuestro conjunto $X$ es la colección de todas las disposiciones posibles de los puntos verdes y rojos, y el grupo $G$ que está actuando en $X$ es el subgrupo de $S_X$ ( el grupo de todas las permutaciones de $X$ ) generados por los tres elementos correspondientes a una vuelta del primer círculo, del segundo círculo y del tercer círculo, respectivamente. La cuestión es entonces, si $x\in X$ es la disposición actual de los puntos, y $y\in X$ es la disposición deseada de los puntos, cómo encontrar un $g\in G$ tal que $gx=y$ (es de suponer que el rompecabezas no se configuraría de tal manera que no hubiera $g$ es decir, se puede llegar a la disposición deseada a partir de la disposición inicial).

Answer 2

Sí, hay mucha teoría de grupos en estos rompecabezas. La literatura mejor desarrollada que he visto (pero no he leído mucho) es sobre el cubo de Rubik. Un enfoque es encontrar una serie de movimientos que intercambien dos puntos, dejando todo el resto solo. En este rompecabezas es más difícil de ver, ya que los puntos no se distinguen; ayudaría poner los números 1-6 en los verdes y 11-16 en los rojos. Entonces se usa la lógica de los conmutadores: se encuentra un par que se quiere intercambiar, se hacen los movimientos que sean necesarios para ponerlos en la posición que se sabe que hay que intercambiar (recordando cómo los pusiste allí), se intercambian y luego se deshacen los movimientos que los llevaron allí. En el lenguaje de la teoría de grupos, esto es un cojugado. La razón por la que es teoría de grupos es que tienes tres movimientos básicos con inversiones y asociatividad.

Añadido, basado en el comentario de Benno a la respuesta de Zev: si puedes encontrar una serie de movimientos que intercambien un punto interior con un punto exterior dejando todos los demás en su sitio tienes un algoritmo (quizás no el más rápido). Es posible que no haya tal serie de movimientos, pero el rompecabezas se puede resolver de todos modos. Por ejemplo, podría haber una restricción de paridad de que siempre hay un número par de verdes en el centro. Me sorprendería mucho. Pero el cubo de Rubik tiene algunas restricciones que reducen las posiciones posibles en un factor $12$ en comparación con el montaje de la diáspora.

Answer 3

Este rompecabezas es fácil una vez que intentas poner los puntos rojos en sus lugares correctos en lugar de centrarte en los puntos verdes. De hecho, ¡puedes hacerlo sin usar el círculo superior izquierdo!

En general, para los rompecabezas de permutación que no tienen restricciones físicas, incluidos los rompecabezas como el cubo de Rubik, podemos resolverlos sistemáticamente

(Utilizo A' para denotar la inversa de A)

1. Dos transformaciones A,B que se cruzan en un solo lugar X tal que tanto A como B alejan la pieza en X. Entonces ABA'B' es un conmutador que hará un 3-círculo que involucra a X. Normalmente no es difícil elegir A y B de tal manera que A tira de la pieza correcta en X y B' empuja la pieza en X en el lugar correcto de la pieza que estaba originalmente en X. A veces puede ser necesario establecer las piezas usando una tercera secuencia C para que se pueda hacer un conmutador, y luego deshacer C'. Por lo general, no es más difícil conseguir que el 3 ciclo coloque y oriente correctamente 2 de las 3 piezas en el 3 ciclo.

2. Dos transformaciones A,B que se cruzan en un solo lugar X, de tal manera que sólo B aleja la pieza en X, mientras que A simplemente cambia la orientación de la pieza en X. Entonces ABA'B' es un conmutador que cambiará la orientación de dos piezas, una de las cuales está en X. Normalmente esto puede ser sustituido por el uso de dos triciclos, el primero para desalojar las dos piezas y una tercera, y el segundo para ponerlas de nuevo en las orientaciones correctas, sin embargo este único conmutador puede tomar menos movimientos.

3. Los conmutadores pueden resolver un estado si y sólo si las posiciones de las piezas son una permutación par y la descripción completa, incluyendo las orientaciones, es también una permutación par. (Para un cubo de Rubik, un giro de esquina es un ciclo de 3 en las tres caras exteriores de la pieza). Algunas posiciones no son permutaciones pares, y debes encontrar una forma de corregir todas estas paridades. (En el caso de un cubo de Rubik de 3*3*3 un cuarto de vuelta de cualquier cara corresponde a un 4-ciclo de aristas y un 4-ciclo de esquinas. Esta paridad significa que exactamente la mitad de las posiciones pueden resolverse sólo con conmutadores, mientras que la otra mitad requiere una corrección de paridad. Para un cubo de Rubik de 4*4*4,5*5*5,6*6*6 hay 2,2,3 paridades respectivamente si he contado bien).

Para aquellos rompecabezas con restricciones físicas, como el Square One, puede ser suficiente para conseguir una forma lo suficientemente bonita como para poder utilizar los conmutadores sin que se bloqueen.

Tenga en cuenta que este método no implica absolutamente ningún algoritmo memorizado, lo que significa que funciona en una gran clase de rompecabezas de permutación, pero también significa que no suele ser tan rápido como los métodos basados en la memorización que se adaptan al rompecabezas específico. Sin embargo, su ventaja más importante es que usted entiende completamente cómo funcionan los rompecabezas de permutación.

Hay algunos rompecabezas con los que me he encontrado en los que es difícil encontrar 3 ciclos, como por ejemplo Twiddle . La única sugerencia que tengo es encontrar dos secuencias que se crucen en el menor número de lugares posible, y que el conmutador obtenido permute como máximo 3 veces más piezas que intersecciones, y luego combinar conmutadores que se crucen en menos lugares, y así sucesivamente. Si alguien tiene alguna idea mejor, por supuesto que me interesaría escucharla.