Sunday 11 August 2013

An engineer's approach to the Instant Insanity puzzle

Last month we had the pleasure of a visit from my old friends Colm Mulcahy and Vicki Powers, both US maths professors. Vicki had been attending a meeting at the Isaac Newton Institute and Colm was giving talks based on his new book Mathematical Card Magic including one, at my suggestion, at Winchester Science Festival where I was speaking on "How Science Shaped Music". It was great to catch up and for my family to meet them, and Colm kindly brought several puzzles for David, including the one I want to write about here. 

Instant Insanity is the usual name for a set of four cubes with each face having one of four colours. The challenge is to pile them up so that each side of the stack shows each colour once. When I'd first heard of it as a child I'd mistaken it for Charles Hinton's four colour cubes, which he claimed helped develop intuition about four-dimensional shapes, mentioned in Martin Gardner's Mathematical Carnival. Gardner quotes a correspondent who claims Hinton's cunes drove him to the edge of madness; I must have heard that a four-colour cube puzzle was called Instant Insanity and conlcluded that this was it. But it isn't.

There's an analysis here (ppt) by Patrick K Asaba that uses a decomposition pronciple and graph theory to find a solution and show that it's unique for a particular set of cubes (how many different sets are out there, I wonder?) I've nothing against it, but not being a graph theorist I preferred to attack it with more basic tools and, possibly, more of an engineering approach.

First, how hard is the puzzle? As Asaba observes, each cube has 24 symmetries, though rotating the stack about its axis doesn't destroy a solution so I'd count the configurations to be chosen from as 82,944 rather than 331,776. That's still a lot, and suggests that brute force won't be any use so some thing elegant (like graph theory) will be needed. On the other hand, imagine that each cube had been drilled through, and a rod inserted through them. From that point, it would be fairly easy to either turn the cubes so that they solved the puzzle or to conclude that the wrong faces had been drilled and that no solution is possible. In fact here's a short piece of Mathematica code that allows you to 'turn' the (unfolded) cubes, and to reverse them, since they can be slid onto the rod either way up.

s = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
cols = {Red, Blue, Green, Yellow};
f = {{2, 3, 1, 4}, {3, 2, 4, 1}, {1, 4, 4, 2}, {2, 3, 1, 3}};
Grid[Table[
  Module[{q = j}, {Button["<", f[[q]] = RotateLeft[f[[q]]]],
    Graphics[
     Dynamic@Table[{cols[[f[[q, i]]]],
        Translate[Polygon[s], {i, 0}]}, {i, 1, 4}]],
    Button[">", f[[q]] = RotateRight[f[[q]]]],
    Button["<>", f[[q]] = Reverse[f[[q]]]]}], {j, 1, 4}]]


So how many ways of drilling and sliding the cubes are there? Each cube can be drilled three ways, and once the first one is on the rod each subsequent one can be oriented two ways, so 3 x 6 x 6 x 6 = 648. Still more than I'd care to try individually but a lot less daunting than 82,944. Here are the four sets of three choices for our set of cubes:


B G R Y
G G R Y
B G R R




Y B Y R
Y G Y Y
G B Y R




R Y G B
R R G Y
R Y Y B




B B R Y
B G R G
G B G Y

(the set Colm gave us had yellow faces rather than white ones.) Our task, then, is to pick one line from each group, each of which can then be flipped and rotated until a solution is found. There are only 81 ways of doing this; can we exclude some at this stage?

Once we've chosen our four rows there have to be four of each colour, and that's by no means guaranteed with a random choice. We can exclude the Y G Y Y row from the second row from further consideration, because that would mean that only one other row can have a Y in it, so that the first and fourth cubes would have to show B G R R and B G R G. The remaining row from the third cube would have to one Y and no G, which none of them do. 

We can tabulate the number of times each colour appears on each row:




R B G Y
B G R Y 1 1 1 1
G G R Y 1 0 2 1
B G R R 2 1 1 0








Y B Y R 1 1 0 2
Y G Y Y 0 0 1 3
G B Y R 1 1 1 1








R Y G B 1 1 1 1
R R G Y 2 0 1 1
R Y Y B 1 1 0 2








B B R Y 1 2 0 1
B G R G 1 1 2 0
G B G Y 0 1 2 1

We can't choose four lots of 1 1 1 1 because the fourth cube doesn't have any. We could interpret rows of numbers as the digits of single numbers and try the 54 remaining ways of adding them up to see how many give 4444. As it happens there are five. This might be a little too much brute force for your tastes but the chances you'd go insane before you found them are reasonably slender.

[to be continued]