Instant Insanity

Instant Insanity is the name given by Parker Brothers to their 1967 version of a puzzle which has existed since antiquity, and which has been marketed many toy and puzzle makers under a variety of names, including: Devil's Dice (Pressman); DamBlocks (Schaper); Logi-Qubes (Schaeffer); Logi Cubes (ThinkinGames); Daffy Dots (Reiss); Those Blocks (Austin); PsykoNosis (A to Z Ideas), and many others.[1]

Instant Insanity puzzle in the "solved" configuration. The colors (from left to right) on the rear of the cubes are blue, red, green, and white. On the bottom, (L-R) WGBR.

The puzzle consists of four cubes with faces colored with four colors (commonly red, blue, green, and white). The objective of the puzzle is to stack these cubes in a column so that each side of the stack (front, back, left, and right) shows each of the four colors. The distribution of colors on each cube is unique.

This problem has a graph-theoretic solution in which a graph with four vertices labeled B, G, R, W (for blue, green, red, and white) can be used to represent each cube; there is an edge between two vertices if the two colors are on the opposite sides of the cube, and a loop at a vertex if the opposite sides have the same color. Trial and error is a slow way to solve this problem, as there are 331,776 possible arrangements of the four cubes (6 faces, 4 turns = 24 positions of each cube, times four cubes, totalling 331,776). And the solution is symmetrical 8 ways (if you have a solution, and you flip all of the four cubes forward, you have another valid solution. You can do that move 4 times multiplied by the rotation of every cube 180 degrees around its vertical axe, which gives 8 symmetries in total), so therefore the odds are 331,776 divided by 8 equals 41,472 chance of randomly tossing the cubes into a solution. The puzzle is studied by D. E. Knuth in an article on estimating the running time of exhaustive search procedures with backtracking. [2]

Every position of the puzzle can be solved in eight moves or less.[3]

The first known patented version of the puzzle was created by Frederick A. Schossow in 1900, and marketed as the Katzenjammer puzzle.[4] The puzzle was recreated by Franz Owen Armbruster, also known as Frank Armbruster, and independently published by Parker Brothers and Pressman, in 1967. Over 12 million puzzles were sold by Parker Brothers alone. The puzzle is similar or identical to numerous other puzzles[5][6] (e.g., The Great Tantalizer, circa 1940, and the most popular name prior to Instant Insanity).

One version of the puzzle is currently being marketed by Winning Moves.

Solution

Given the already colored cubes and the four distinct colors are (Red, Green, Blue, White), we will try to generate a graph which gives a clear picture of all the positions of colors in all the cubes. The resultant graph will contain four vertices one for each color and we will number each edge from one through four (one number for each cube). If an edge connects two vertices (Red and Green) and the number of the edge is three, then it means that the third cube has Red and Green faces opposite to each other.

Four cubes and their colors
The graph generated by the four cubes

To find a solution to this problem we need the arrangement of four faces of each of the cubes. To represent the information of two opposite faces of all the four cubes we need a directed subgraph instead of an undirected one because two directions can only represent two opposite faces, but not whether a face should be at the front or at the back.

So if we have two directed subgraphs, we can actually represent all the four faces (which matter) of all the four cubes.

  • First directed graph will represent the front and rear faces.
  • Second directed graph will represent the left and right faces.

We cannot randomly select any two subgraphs - so what are the criteria for selecting?

We need to choose graphs such that:

  1. the two subgraphs have no edges in common, because if there is an edge which is common that means at least one cube has the pair of opposite faces of exactly same color. Which means, A cube has Red and Blue as front and rear face as well as left and right face.
  2. a subgraph contains only one edge from each cube, because the sub graph has to account for all the cubes and one edge can completely represent a pair of opposite faces.
  3. a subgraph can contain only vertices of degree two, because a degree of two means a color can only be present at faces of two cubes. Easy way to understand is that there are eight faces to be equally divided into four colors. So, two per color.

After understanding these restrictions if we try to derive the two sub graphs, we may end up with one possible set as shown in Image 3. Each edge color represents a cube.

The images are steps to solve the instant insanity problem

From the first sub graph we will derive the front and the rear face colors of the corresponding cube. For e.g.:

  1. The black arrow from White to Blue says that the first cube will have White in the front face and Blue at the Rear.
  2. The blue arrow from Green to White says that the second cube will have Green in the front face and White at the Rear.
  3. The orange arrow from Blue to Red says that the third cube will have Blue in the front face and Red at the Rear.
  4. The purple arrow from Red to Green says that the fourth cube will have Red in the front face and Green at the Rear.

From the second sub graph we will derive the left and the right face colors of the corresponding cube. For e.g.:

  1. The black arrow from Red to Green says that the first cube will have Red in the left face and Green at the Right.
  2. The blue arrow from Blue to Red says that the second cube will have Blue in the left face and Red at the Right.
  3. The orange arrow from Yellow to Blue says that the third cube will have White in the left face and Blue at the Right.
  4. The purple arrow from Green to White says that the fourth cube will have Green in the left face and White at the Right.

The third image shows the derived stack of cube which is the solution to the problem.

It is important to note that:

  1. You can arbitrarily label the cubes as one such solution will render 23 more by swapping the positions of the cubes but not changing their configurations.
  2. The two directed subgraphs can represent front-to-back, and left-to-right interchangeably, i.e. one of them can represent front-to-rear or left-to-right. This is because one such solution also render 3 more just by rotating. Adding the effect in 1., we generate 95 more solutions by providing only one. To put it into perspective, such four cubes can generate 243 × 3 = 41472 configurations.
  3. It is not important to take notice of the top and the bottom of the stack of cubes.[7]

Generalizations

Given n cubes, with the faces of each cube coloured with one of n colours, determining if it's possible to stack the cubes so that each colour appears exactly once on each of the 4 sides of the stack is NP-complete. [8][9]

The cube stacking game is a two-player game version of this puzzle. Given an ordered list of cubes, the players take turns adding the next cube to the top of a growing stack of cubes. The loser is the first player to add a cube that causes one of the four sides of the stack to have a color repeated more than once. Robertson and Munro[10] proved that this game is PSPACE-complete, which illustrates the observation that NP-complete puzzles tend to lead to PSPACE-complete games.

References
  1. Devil's Dice
  2. Knuth, D. E. (1975), "Estimating the efficiency of backtrack programs", Math. Comp., 29: 132–136, doi:10.1090/S0025-5718-1975-0373371-6
  3. https://habrahabr.ru/post/336858/(in+Russian)
  4. US Patent # 646,463
  5. Slocum; Botermans (1986), Puzzles Old & New, p. 38
  6. "Archived copy". Archived from the original on 2007-10-22. Retrieved 2007-08-12.CS1 maint: archived copy as title (link)
  7. Beeler, R.; Instant Insanity: Supplemental Material for Intro to Graph Theory; Depr. of Mathematics & Statistics, East Tennessee State University; Johnson City, Tennessee: 2017
  8. Garey, M. R.; Johnson, D. S. (1979), Computers and Intractibility: a guide to the theory of NP-completeness, W.H. Freeman, p. 258 (problem GP15);
  9. Robertson, E.; Munro, I. (1978), "NP-completeness, puzzles, and games", Util. Math., 13: 99–116.
  10. Robertson, Edward; Munro, Ian (1978). "NP-completeness, puzzles and games". Utilitas Mathematica. 13: 99–116.
  • Slocum; Botermans (1987), Puzzles Old and New, Seattle: University of Washington Press, p. 38, ISBN 0-295-96579-7
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.