How do you solve Instant Insanity: stack four cubes, whose faces are colored red, white, blue and green, so...

Here's my technique:

1.  Count how many faces of each color are on your cubes.  Your
    solution will use four faces of each color.  Figure out how
    many *extra* faces of each color there are.

    Find a pair of opposing faces on each cube such that the total
    number of faces of each color in this set of faces equals the
    number of extra faces of that color.  Align your cubes so that
    these faces are all along the axis of the stack of four cubes.
    Throughout your solution, keep the same faces on the axis.

2.  Choose two opposing (not on the axis) sides of the stack of
    cubes.  By spinning cubes about the axis, align them such that
    the two sides you have chosen contain a total of two faces of
    each color.

    This will automatically put two faces of each color on the
    *other* two sides of the stack, as well.  From here on, keep
    all pairs of opposing sides on the pairs of opposing faces they
    are now on.

3.  Again choose two opposing sides of the stack.  Using the faces
    that are already assigned to those sides, and by using *only*
    180 degree spins about the axis of the stack, align the cubes
    such that there is one face of each color on each of these sides.

    These two sides are now solved.  From here on, leave the faces on
    these sides where they are.

4.  Look at the last pair of opposing sides of the stack.  Using
    *only* 180 degree spins *perpendicular* to the axis of the stack,
    align the cubes such that there is one face of each color on each
    of the last two faces.

    The puzzle is now solved!

This algorithm will always work, no matter how the colors appear on
your cubes (as long as there are at least four faces of each color).

[Editor: the table of the poster's cubes that followed here is given in
the problem statement.]

-- Angi Long (angilong@bach.seattleu.edu)

In article <3558rj$32j@scapa.cs.ualberta.ca> eric@cs.ualberta.ca (Eric
Holleman) writes:
>Many years ago, my Graph Theory prof used Instant Insanity as a
>demonstration of the power of Graph Theory.  It was really cool at the
>time (still is, really).  I think that the
>solution(s) was a Hamiltonian circuit in a graph derived from the cubes.

The technique I've seen is:

(1) Label four nodes with the four colors R, W, B, G.

(2) Select a cube.  Select two opposite faces.  Draw an arc on your
graph starting at the color of one face and ending at the color of the
other.  (If the faces are the same color, this will be a loop.)  Label
this arc "1".

(3) Draw the arcs for the two other sets of opposing faces of the first
cube.  Label them "1".

(4) Repeat with the remaining cubes, but label the arcs for the second
cube "2", for the third cube "3", and for the fourth cube "4".

(5) Find two cycles on the graph each of which visits all four colors
once (a Hamiltonian cycle), uses arcs from all four cubes, and shares
no arcs with the other cycle.

(6) Put arrowheads on the arcs to make both cycles directed cycles.

(7) Line up cubes 1 through 4 in a row.

(8) Orient each cube so the color at the head end of the corresponding
arc in the first cycle is on top.  For example, if the arc labeled "1"
in the first cycle points to the red node, the red face of cube 1 goes
on top.

(9) Put the colors at the heads of the arcs in the second cycle in
front.  You're done!

Note that the graph is a complete description of the cube set, up
to mirror reflection of the cubes.  But you can easily replace a cube in
a solved puzzle by its mirror reflection (just swap the hidden faces),
so the graph contains all possible relevant data.

But also note that step (5) is not completely general: it doesn't
always find a solution when one exists.  That is, it works for the
Instant Insanity puzzles I've seen, but not for every set of cubes
that might constitute a puzzle of this sort.  For example, suppose we
have a red cube, a blue cube, a green cube, and a white cube (each
cube is one color on all 6 faces).  The graph of this cube set is four
isolated nodes with three loops each.  Obviously there is no
Hamiltonian cycle on this graph, yet the cube set is easily
solvable---just line them up and you're done.

ObPuzzle:  Generalize step (5) so it works with any set of cubes.

-- David A. Karr (karr@cs.cornell.edu)

angilong@bach.seattleu.edu (Angi Long) writes:
> I thought that there was no way the right number of colors could
> appear on the outside of the stack and not be solvable.  But it's
> been brought to my attention that this is indeed possible, so if
> you have cubes that differ from mine, you might have to go back
> to step #1 and choose another set of faces for the axis.

Yes, you might.  Might you also have to go back to step 2 if step 3 or
4 fails?  (The answer is no, but why?)

> This is one advantage of my technique over the graphic one somebody
> else described -- this one will definitely give *all* solutions.

Well, if you are going to go for _all_ solutions, then you had better
be explicit about backtracking over different choices in steps 2, 3,
and 4 as well as different choices for step 1.

Also, if you think that O'Beirne's method, as described by David A.
Karr [Editor: the original gives his address, karr@cs.cornell.edu],
does not give all solutions, then you haven't solved the
ObPuzzle he posed:

  Generalize step (5) so it works with any set of cubes.

The solution to that is to allow, in place of a Hamiltonian cycle, any
system of disjoint cycles that visit all four colors.  As with the
Hamiltonian cycles, we will require that arcs from all four cubes be
used.  If you do it that way, you definitely get [Editor: the original has "you get definitely
get"] all solutions.
Using this method, I found all the solutions for your cubes:

       Sol I       Sol II      Sol III     Sol IV      Sol V
cube   1 2 3 4     1 2 3 4     1 2 3 4     1 2 3 4     1 2 3 4
top    R B G W     B R W G     B R W G     B G R W     R G B W
down   B W G R     R G B W     R G B W     R W B G     B W R G
front  G R W B     W G R B     W G B R     R W G B     R W G B
back   W G B R     G W B R     G W R B     W B G R     W B G R

Of course, all of these can be modified trivially by permuting the
sides {top,down,front,back} in any way that preserves opposite [Editor: the original has "opposites"] sides.
Also, they can be modified by exchanging the roles of cubes 1 and 4,
which are colored identically.  Under this system, the solutions found
by euagwd@eua.ericsson.se (Goran Wicklund) are Sols I' and V, while
the ones you found are Sols IV', I, II, and III', where the prime
marks those in which cubes 1 and 4 have been swapped.  [Editor: those
postings are not in the collection.]

You also said:

> This algorithm will always work, no matter how the colors appear on
> your cubes (as long as there are at least four faces of each color).

You shouldn't make such claims when you are just guessing.  In this
case, you are guessing wrong.  The presence of at least four faces of
each color, while necessary, is not even close to sufficient for there
to be an Instant Insanity solution.  For instance, in each of the
following sets of cubes, you are allowed to mark the Green, Blue and
White faces any way you like.  Each set is insoluble, in spite of
having at least four red faces, and plenty of space for the others.
The reasons for insolubility are pretty obvious, but rot13'd in case
you want to consider them an ObPuzzle.

cube   1 2 3 4        1 2 3 4        1 2 3 4             1 2 3 4
top    R R x x        R R x x        R R R R             R x R x
down   R R x x        R R x x        x R R R             x x x x
front  R R x x        R R x x        R x x R             x x R x
back   R x x x        R x x x        x x x R             x x x x
left   R x x x        R R x x        x x x x             x x R x
right  R x x x        x x x x        x x x x             x x x x

Why:   Gbb znal Ef    Gbb znal Ef    Bqq ahzore bs Ef    Gbb srj Ef

If we generalize the problem to an arbitrary number of cubes, then
determining whether there is a solution is NP-complete [see Garey and
Johnson].  This does not prove it's all that hard for four cubes, but
it suggests there will not be a trivial criterion.  In fact, I'll pose
the ObPuzzles:

1. How many possible sets of Instant Insanity cubes are solvable?
   What percentage of all possible sets?  (It is necessary to
   carefully define what you consider to be "different" sets of cubes.
   For instance, if one cube is reflected in a mirror, does that make
   it, and its set, "different"?  Are you counting the order of the
   cubes with each set?)

2. What is the average number of solutions for those sets that are
   solvable?

-- Dan Hoey (Hoey@AIC.NRL.Navy.Mil)

A book which deals with this type of problem in a very nice way
(together [Editor: the original has "togther"] with the 12-coin
problem which is such a regular visitor to these newsgroups) is Puzzles and Paradoxes by T. H.
O'Beirne, published originally by Oxford University Press in 1965 but
reprinted by Dover in 1984.

-- Robin Chapman (rjc@maths.ex.ac.uk)