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.
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:
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.
El subgrafo superior permite derivar los colores de las caras izquierda y derecha del cubo correspondiente. Por ejemplo:
El subgrafo inferior permite obtener los colores de las caras frontal y posterior del cubo correspondiente. Por ejemplo:
La tercera imagen muestra la pila de cubos derivada que es la solución al problema.
Es importante tener en cuenta que:
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.