¿Hay un camino a través del "flipbook" del juego 504?

Question

Inspirado por la discusión en este foro. Para el fondo, el juego 504 se denomina de esta manera porque hay 504 posible "variaciones", formada por escoger 3 módulos de un total de 9 (donde el orden es importante). Así, por ejemplo, el juego formado por módulos de 4, 1 y 5 (también conocido como "mundo 415") tiene condiciones de victoria basada en la guerra (Módulo 4: Militar) con los ingresos de un pick-up y entregar mecánico (Módulo 1) y los puntos de bonificación basa en la exploración de nuevos territorios (Módulo 5: la Exploración). Para ayudar a mantener un seguimiento de lo que las reglas que usted está jugando, un flipbook es siempre (un poco como los libros donde se le da la vuelta a través de una serie de imágenes para elegir un estilo de peinado, los ojos, la nariz, etc para hacer una cara).

Así que la pertinente bits son:

• Cada "mundo" está definido por una permutación de 3 dígitos elegido a partir de (1, ..., 9).
• Si dos mundos diferentes sólo a través de uno de los 3 dígitos diferentes por 1, que se puede considerar adyacentes, ya que sólo tiene que pasar una página del libro animado para ir de una a la siguiente (así, por ejemplo, el mundo 456 es adyacente a los 356).
• Por lo tanto, puede representar el flipbook como un grafo donde los vértices son los mundos posibles y los bordes representan pasar las páginas.

Es bastante fácil para probar que tal y como está, no es Hamiltoniano camino a través de la flipbook - cada uno de los mundos mediante el uso de módulos 1, 2 y 3 en orden (y de manera similar, 7, 8 y 9) sólo tiene una adyacentes mundo, formado por darle la vuelta a la 3 a la 4. El volteo de cualquiera de las otras páginas causa reiterada de un valor (por ejemplo, 223 o 113) lo cual no está permitido en el juego de la construcción. Pero tener 12 mundos, cada uno con sólo una adyacentes mundo significa que usted no puede dibujar un bonito sendero entre ellos.

Sin embargo, lo que si asumimos que los módulos 1 y 9 fueron también adyacente, de modo que podríamos alternar entre ellos? A continuación, mundo 123 es adyacente a ambos 923 y 124, y lo mismo para el otro problema mundos.

Como lo que puedo decir, este gráfico no pertenezcan a ninguna de las familias de los grupos que está garantizado para tener un camino Hamiltoniano. Pero hay uno? Y si es así, hay una casa algoritmo a seguir?

Answer 1

De hecho, esta alteración del flipbook gráfico no está conectado! Imagine la organización de los números 1,..., 9, como la cara de un reloj, por lo que 1 es adyacente a los 2 y 9, y que la lectura en sentido horario el fin de da $1,2,\dots, 9, 1, 2$. Luego llame a un vértice de la 'derecha' si los tres dígitos en la permutación que da son en orden de las agujas del reloj, y la 'izquierda' en caso contrario. Así que 123 es hacia la derecha, pero 132 es en sentido antihorario.

Ahora no las agujas del reloj vértice pueden ser adyacentes a un vértice en el sentido contrario. Para ver esta nota que un vértice puede ser representado por tres puntos en el reloj. Los vértices son adyacentes si tienen dos puntos en común y el tercer punto de un vértice puede ser deslizada para el tercer punto de los otros vértices. Pero deslizamiento claramente no se puede cambiar el sentido de vértices en un en el sentido contrario vértice.

Por supuesto, esto deja abierta la cuestión de si los vértices de las agujas del reloj forman un gráfico con un camino Hamiltoniano, pero no tengo idea de por donde empezar con eso!