stringtranslate.com

Locura instantánea

Rompecabezas Instant Insanity en la configuración "resuelta". De arriba a abajo, los colores en la parte posterior de los cubos son blanco, verde, azul y rojo (lado izquierdo), y azul, rojo, verde y blanco (lado derecho).
Redes de los cubos de Instant Insanity: el estilo de línea es para identificar los cubos en la solución

Instant Insanity es el nombre dado por Parker Brothers a su versión de 1967 de un rompecabezas que ha existido desde la antigüedad, y que ha sido comercializado por muchos fabricantes de juguetes y rompecabezas bajo una variedad de nombres, incluyendo: Devil's Dice ( Pressman ); DamBlocks (Schaper); Logi-Qubes (Schaeffer); Logi Cubes (ThinkinGames); Daffy Dots (Reiss); Those Blocks (Austin); PsykoNosis (A to Z Ideas), y muchos otros. [1]

El rompecabezas consta de cuatro cubos con caras coloreadas con cuatro colores (normalmente rojo, azul, verde y blanco). El objetivo del rompecabezas es apilar estos cubos en una columna de modo que cada lado de la pila (delante, atrás, izquierdo y derecho) muestre cada uno de los cuatro colores. La distribución de colores en cada cubo es única y el orden en el que se apilan los cuatro cubos es irrelevante siempre que cada lado muestre todos los colores.

Este problema tiene una solución de teoría de grafos en la que se puede utilizar un grafo con cuatro vértices etiquetados B, G, R, W (para azul, verde, rojo y blanco) para representar cada cubo; hay una arista entre dos vértices si los dos colores están en los lados opuestos del cubo, y un bucle en un vértice si los lados opuestos tienen el mismo color. Cada cubo individual se puede colocar en una de las 24 posiciones, colocando cualquiera de las seis caras hacia arriba y luego dando al cubo hasta tres cuartos de vuelta. Una vez que se forma la pila, se puede girar hasta tres cuartos de vuelta sin alterar la orientación de ningún cubo en relación con los demás. Ignorando el orden en el que se apilan los cubos, el número total posible de disposiciones es, por tanto, 82.944 (24 * 24 * 24 * 24 / 4). El rompecabezas es estudiado por DE Knuth en un artículo sobre la estimación del tiempo de ejecución de los procedimientos de búsqueda exhaustiva con retroceso. [2]

Cada posición del rompecabezas se puede resolver en ocho movimientos o menos. [3]

La primera versión patentada conocida del rompecabezas fue creada por Frederick A. Schossow en 1900 y comercializada como el rompecabezas Katzenjammer . [4] El rompecabezas fue recreado por Franz Owen Armbruster, también conocido como Frank Armbruster, y publicado de forma independiente por Parker Brothers y Pressman , en 1967. Solo Parker Brothers vendió más de 12 millones de rompecabezas. El rompecabezas es similar o idéntico a muchos otros rompecabezas [5] [6] (por ejemplo, The Great Tantalizer , alrededor de 1940, y el nombre más popular antes de Instant Insanity ).

Actualmente, Winning Moves Games USA comercializa una versión del rompecabezas.

Solución

Un gráfico de las caras opuestas de los cubos, los estilos de línea corresponden a los cubos en la imagen de sus redes de arriba.

Dados los cubos ya coloreados y los cuatro colores distintos (rojo, verde, azul, blanco), intentaremos generar un gráfico que dé una imagen clara de todas las posiciones de los colores en todos los cubos. El gráfico resultante contendrá cuatro vértices, uno por cada color, y numeraremos cada arista del uno al cuatro (un número por cada cubo). Si una arista conecta dos vértices (rojo y verde) y el número de la arista es tres, entonces significa que el tercer cubo tiene caras rojas y verdes opuestas entre sí.

Para encontrar una solución a este problema necesitamos la disposición de las cuatro caras de cada uno de los cubos. Para representar la información de dos caras opuestas de los cuatro cubos necesitamos un subgrafo dirigido en lugar de uno no dirigido porque dos direcciones solo pueden representar dos caras opuestas, pero no si una cara debe estar al frente o al fondo.

Entonces, si tenemos dos subgrafos dirigidos, podemos representar las cuatro caras (que importan) de los cuatro cubos.

No podemos seleccionar aleatoriamente dos subgrafos, entonces ¿cuáles son los criterios para la selección?

Necesitamos elegir gráficos tales que:

  1. los dos subgrafos no tienen aristas en común, porque si hay una arista que es común eso significa que al menos un cubo tiene el par de caras opuestas de exactamente el mismo color, es decir, si un cubo tiene Rojo y Azul como caras frontal y posterior, entonces lo mismo es cierto para sus caras izquierda y derecha.
  2. un subgrafo contiene solo un borde de cada cubo, porque el subgrafo tiene que dar cuenta de todos los cubos y un borde puede representar completamente un par de caras opuestas.
  3. Un subgrafo puede contener solo vértices de grado dos, porque un grado dos significa que un color solo puede estar presente en las caras de dos cubos. Una forma fácil de entenderlo es que hay ocho caras que se deben dividir en cuatro colores de manera uniforme. Por lo tanto, dos por color.

Después de comprender estas restricciones, si intentamos derivar los dos subgráficos, podemos terminar con un conjunto posible como se muestra en la Imagen 3. Cada estilo de línea de borde representa un cubo.

Al mapear los bordes de los dos subgrafos dirigidos hacia las caras izquierda (L) y derecha (R), y frontal (F) y posterior (B), se resuelve el problema.

El subgrafo superior permite derivar los colores de las caras izquierda y derecha del cubo correspondiente. Por ejemplo:

  1. La flecha sólida de Rojo a Verde indica que el primer cubo tendrá Rojo en la cara izquierda y Verde en la derecha.
  2. La flecha discontinua de Azul a Rojo indica que el segundo cubo tendrá Azul en la cara izquierda y Rojo en la derecha.
  3. La flecha punteada de Blanco a Azul indica que el tercer cubo tendrá Blanco en la cara izquierda y Azul en la derecha.
  4. La flecha de puntos y guiones de Verde a Blanco indica que el cuarto cubo tendrá Verde en la cara izquierda y Blanco en la derecha.

El subgrafo inferior permite obtener los colores de las caras frontal y posterior del cubo correspondiente. Por ejemplo:

  1. La flecha sólida de Blanco a Azul indica que el primer cubo tendrá Blanco en la cara frontal y Azul en la parte posterior.
  2. La flecha discontinua de Verde a Blanco indica que el segundo cubo tendrá Verde en la cara frontal y Blanco en la parte posterior.
  3. La flecha punteada de Azul a Rojo indica que el tercer cubo tendrá Azul en la cara frontal y Rojo en la parte posterior.
  4. La flecha de puntos y guiones de Rojo a Verde indica que el cuarto cubo tendrá Rojo en la cara frontal y Verde en la posterior.

La tercera imagen muestra la pila de cubos derivada que es la solución al problema.

Es importante tener en cuenta que:

  1. Puedes etiquetar arbitrariamente los cubos, ya que una de esas soluciones generará 23 más intercambiando las posiciones de los cubos pero sin cambiar sus configuraciones.
  2. Los dos subgrafos dirigidos pueden representar de adelante hacia atrás y de izquierda a derecha de manera intercambiable, es decir, uno de ellos puede representar de adelante hacia atrás o de izquierda a derecha. Esto se debe a que una de esas soluciones también genera 3 más con solo rotar. Si sumamos el efecto en 1, generamos 95 soluciones más al proporcionar solo una. Para ponerlo en perspectiva, esos cuatro cubos pueden generar 24 configuraciones de 3 × 3 = 41472.
  3. No es importante prestar atención a la parte superior e inferior de la pila de cubos. [7]

Generalizaciones

Una variante con los palos de las cartas es más fácil, a menos que los símbolos puedan orientarse de alguna manera.

Dados n cubos, con las caras de cada cubo coloreadas con uno de n colores, determinar si es posible apilar los cubos de manera que cada color aparezca exactamente una vez en cada uno de los 4 lados de la pila es NP-completo . [8] [9]

El juego de apilar cubos es una versión de este rompecabezas para dos jugadores. Dada una lista ordenada de cubos, los jugadores se turnan para agregar el siguiente cubo a la parte superior de una pila creciente de cubos. El perdedor es el primer jugador que agrega un cubo que hace que uno de los cuatro lados de la pila tenga un color repetido más de una vez. Robertson y Munro [10] demostraron que este juego es PSPACE-completo , lo que ilustra la observación de que los rompecabezas NP-completos tienden a conducir a juegos PSPACE-completos.

Referencias

  1. ^ Dados del diablo
  2. ^ Knuth, DE (1975), "Estimación de la eficiencia de los programas de retroceso", Math. Comp. , 29 (129): 132–136, doi : 10.1090/S0025-5718-1975-0373371-6
  3. ^ https://habrahabr.ru/post/336858/ (en ruso)
  4. ^ Patente de EE. UU. N.° 646 463
  5. ^ Slocum; Botermans (1986), Rompecabezas antiguos y nuevos , pág. 38
  6. ^ "Página de rompecabezas de Rob: Rompecabezas de patrones". Archivado desde el original el 22 de octubre de 2007. Consultado el 12 de agosto de 2007 .
  7. ^ Beeler, R.; Instant Insanity: Material complementario para la introducción a la teoría de grafos; Departamento de Matemáticas y Estadística, Universidad Estatal del Este de Tennessee; Johnson City, Tennessee: 2017
  8. ^ Garey, MR; Johnson, DS (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, pág. 258(problema GP15);
  9. ^ Robertson, E.; Munro, I. (1978), "NP-completitud, acertijos y juegos", Util. Math. , 13 : 99–116.
  10. ^ Robertson, Edward; Munro, Ian (1978). "NP-completitud, rompecabezas y juegos". Utilitas Mathematica . 13 : 99–116.