Vast Search Space?
The Super IQ cube, by
Horst Heinz at Profi-Produkte (Professional Products), is composed of 17
wooden pieces of 3 different basic kinds: six composed of 12 cubes in a
2x2x3 block and half of which are blue and half red, six composed of 8
cubes in a 2x1x4 block and half of which are red and half yellow, and 5
having a single 1x1x1 light-blue cube. This cube puzzle is very unlike
the 4x4x4 Tetris, Bedlam and Big Brother cubes, which each have a set of
unique pieces. I have not seen the packing but it allegedly indicates
that of 1,001 possible piece combinations, only 1 fits into the box. The
assembled cube photo below was tiled by Jörg Gehrmann from my software
solution.
|
The 3 different kinds of pieces |
All 17 pieces |
Assembled Super IQ cube
|
|
Photos courtesy
of Jörg Gehrmann |
Of the 17 puzzle pieces,
6 may be rotated into 6 possible orientations, 6 may be rotated into 3
possible orientations, and 5 may be rotated into 1 possible orientation.
This means there are at most 66
x 63 x 51 = 50,388,480 possible
piece orientation combinations to try. If the pieces were unique it
would be possible attempt to fit them into the 5x5x5 cube in at most 17! = 17x16x15x(...)x2x1 = 355,687,428,096,000
possible piece ordering permutations, however because of many identical
pieces there are only 17!/(6!x6!x5!) = 5,717,712 unique piece order
permutations to try, significantly more than the 1,001 figure alleged to
be on the product package.
The product of these numbers is 288,106,816,757,760 (288 trillion) steps
to try every possible orientation of every possible piece order
permutation!
I had to modify my
solver code, which was originally written for puzzles having all-unique
pieces, to allow it to take advantage of the identical pieces by
maximally advancing the piece order permutation sequence.
Normally, the initial piece
order would be 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17 so the next becomes
2,1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17 and then 3,1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17 etc.
When the permutations are fully exhausted the piece order is, finally,
17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1. But since pieces 1-6
are identical, and 7-12 are identical, and 13-17 are identical, whenever
the permutation order has two or more identical pieces adjacent in the
sequence it is possible to skip all the useless permutations that would
therefore be the same. For example, for the Super IQ cube the
initial piece order permutation order is instead
{6,5,4,3,2,1}{12,11,10,9,8,7}{17,16,15,14,13} where the identical pieces
within their brace-enclosed groups are sorted descending.
Moreover, for any new permutation we always move the largest piece
number of the identical group into the ordered position for any
lower-numbered piece in that same group.
Because the cube is a
rather snug 5x5x5 box there are many
piece orientations that simply will not fit into the box with other
pieces in their own various orientations, as anyone who tries to
manually assemble a Super IQ cube knows from personal experience!
Consequently, the number of permutations and therefore the number of
piece orientations to attempt to tile into the box are drastically
diminished. For the initial permutation, say pieces
6 and 5 are already in the box but none of the orientations for piece 4
fit. Therefore, all the piece order permutations that would have
followed piece 4 having pieces 6 and 5 in the box are immediately
eliminated from having to be attempted, multiplied by the number of
possible orientations for each of those pieces in all those discarded
orientations. This can happen at any stage of the search, so the search
space is in practice vastly smaller than the 288 trillion
steps figure above, bringing it into reach of a software program. NOTE: the
software internally uses piece numbers 0-16 rather than 1-17.
Of the 5,717,712
possible piece ordering permutations only 3 produce a completed
cube (see below, Search Results). This means you have about 1 chance
in 1,905,904 that a random lineup of the pieces can be put into a cube.
No wonder it's not so easy! The Super IQ cube is therefore about 140 times
harder than the Bedlam cube for which you have about 1 chance in 13,523,
and 940 times harder than the Tetris cube, for which you have about 1 chance in 2,028,
and 104 times harder than the Big Brother cube, for which you have about
1 chance in 18,301.
There is, however,
a trick that makes solving it without technology
rather easy, and therefore perhaps it's not so difficult after all!
Search Algorithm
Each of the 17 pieces is arbitrarily
assigned a unique number, 1 to 9 continuing with A to H (see diagram below). The software encodes the
3-dimensional coordinates of each cube of each piece, and
then rotates them in 4 possible positions around each of the 3 axes (x,y,z)
to generate every possible unique orientation, eliminate mirror image
symmetry piece orientations, and build a quick reference
lookup table. The piece order permutation order is initialized
(for reasons given above, and to bias the tiling of the largest pieces
first and allow the small single cube pieces to fill in the remaining
holes) to 6,5,4,3,2,1,12,11,10,9,8,7,17,16,15,14,13 and the orientation of each piece is reset
to 1.
A 5x5x5 3-dimensional box is encoded and the initial empty cube is
scanned starting at (x,y,z) coordinates (1,1,1). NOTE: the software
internally uses piece numbers 0-16 rather than 1-9 continuing with A-H.
The first orientation of
the first piece in the permutation is fitted (or not) into the box. If
it doesn't fit, the next orientation is tried, etc. If the piece fits,
the next empty cube in the box is scanned along the x-axis, then y-axis,
then z-axis. If the next empty cube is isolated, the last piece
orientation fitted into the box is removed and its remaining
orientations are tried. If the next empty cube is not isolated, the next
piece in the permutation order is attempted the same way. If none
of the orientations of a piece fit into the box without isolating the
next empty cube, the piece order permutation is advanced so the next
piece in the ordering becomes the next piece to try, and it's first
orientation is attempted, etc. Note the permutation algorithm is
different from the solver for cubes having all-unique pieces to attempt
to maximally advance the sequence due to the identical pieces.
By repeating this process,
literally every possible orientation of every possible ordering of pieces is
visited by my search software program, an undeniably rigorous method.
This method will produce multiple rotated copies of each unique
solution, so a further step in the program spins the solved cube around
each axis and compares each rotation with a catalog of saved solutions.
Because of the identical pieces in the Super IQ cube, the duplicate
solution detection algorithm code was also modified to treat all the
pieces of an identical group as though they were a single unique piece. Only new unique solutions are then added to the catalog as the
permutation sequence progresses, guaranteeing the correct catalog is
produced.
 |
|
Diagram of the 17 Super
IQ Cube pieces, as 3 distinct 'kinds'
and the arbitrary numbers 1 to 17 assigned to each in the
software program and solutions catalog. Pieces 1 to 9 are labeled by their
own numbers and 10 through 17 are labeled A through H, respectively.
Note that three yellow pieces are
identical to three red pieces among the pieces labeled 7-C and are
treated here and by the software cube solver indistinguishably and
interchangeably.
Similarly, three red pieces are
identical to three blue pieces among the pieces labeled 1-6 and
are treated here and by the software cube solver indistinguishably
and interchangeably. |
Search Results
Exactly
1 unique
solution was found. Because of diagonal symmetry, one for
each possible opposing-corner diagonal axis through the cube, my software
actually assembled 3 cube solutions but it discarded
2 duplicates as copies of the single
unique solution. The software search completed in 29 seconds on my
old 2 GHz Pentium 4 laptop. The 1 unique solution, however, was
found within the first 10 seconds and the remaining 19 seconds completed
permutations that resulted in 2 non-unique copies. The search space was,
as expected, enormously reduced to a 'mere' total of exactly 35,941,923
piece order permutations visited, including dead-end orientation paths.
The program attempted to fit pieces into the box exactly 116,432,571
times and succeeded fitting them exactly 16,405,961 times. Indeed, 116
million is MUCH smaller than 288 trillion!
Super IQ Cube Solution
Below is the software's
startup analysis, the single possible solution, and the search conclusion outputs, rigorously
determined using 'brute-force' combinatorial techniques. Pieces are mapped to numbers 1-17 and their
identification is aided by the descriptive cube counts and labeling
in agreement with the diagram above. The solutions are given in layers of the
5x5x5 box, with the
top
layer of the cube on the left and ending with the bottom layer on the
right. Pieces 1 to 9 are given
in the solutions by those numbers, and pieces 10 through 17 are given as
A through H respectively.
It takes a bit of
visualization to see the pieces in the printed solution and it helps to
refer to the diagram above. In the solution
below, particularly challenging to visualize are pieces spanning cube
layers, which in the outlined examples of blue piece
3 and red piece
9 in the solution span the top
(leftmost) layer through layers 2, 3 and 4, and the light-blue single
cube pieces D, E, F, G, H run
diagonally through the cube. Get out your Super IQ
cube and try it... it's rather easy once you get the hang of it.
The trick seen by the astute observer might appear obvious. A cube
having so many like kinds of pieces suggests the piece tiling would
necessarily include 'crystal-like' symmetry that renders the solution
rather trivial to find. And indeed, that is in fact the case.
The pieces form a diagonal corner-to-opposite-corner spiral-flower-like
symmetrical tiling, forming two triangular pyramids that meet at their
jagged bases to make the assembled cube, with the light-blue single-cube
pieces starting at the top of each pyramid and going straight 'down' the
assembled cube's diagonal and meeting at a shared light-blue single-cube
piece in the center of the assembled cube, between the two jagged
pyramid bases. So a software solution is not necessary, but it
was, at least, correct!
Heinz IQ Cube Solver, (c)2009 www.scottkurowski.com
Piece 6 has 12 cubes, labeled 2x2x3
Piece 5 has 12 cubes, labeled 2x2x3
Piece 4 has 12 cubes, labeled 2x2x3
Piece 3 has 12 cubes, labeled 2x2x3
Piece 2 has 12 cubes, labeled 2x2x3
Piece 1 has 12 cubes, labeled 2x2x3
Piece 12 has 8 cubes, labeled 2x1x4
Piece 11 has 8 cubes, labeled 2x1x4
Piece 10 has 8 cubes, labeled 2x1x4
Piece 9 has 8 cubes, labeled 2x1x4
Piece 8 has 8 cubes, labeled 2x1x4
Piece 7 has 8 cubes, labeled 2x1x4
Piece 17 has 1 cubes, labeled 1x1x1
Piece 16 has 1 cubes, labeled 1x1x1
Piece 15 has 1 cubes, labeled 1x1x1
Piece 14 has 1 cubes, labeled 1x1x1
Piece 13 has 1 cubes, labeled 1x1x1
Piece 1 has 3 unique rotational orientations
Piece 2 has 3 unique rotational orientations
Piece 3 has 3 unique rotational orientations
Piece 4 has 3 unique rotational orientations
Piece 5 has 3 unique rotational orientations
Piece 6 has 3 unique rotational orientations
Piece 7 has 6 unique rotational orientations
Piece 8 has 6 unique rotational orientations
Piece 9 has 6 unique rotational orientations
Piece 10 has 6 unique rotational orientations
Piece 11 has 6 unique rotational orientations
Piece 12 has 6 unique rotational orientations
Piece 13 has 1 unique rotational orientations
Piece 14 has 1 unique rotational orientations
Piece 15 has 1 unique rotational orientations
Piece 16 has 1 unique rotational orientations
Piece 17 has 1 unique rotational orientations
Solution 1
TOP BOTTOM
All permutations exhausted, 1 unique solutions found, 2 duplicate rotations/piece-exchanges discarded
Total permutations = 35941923, tiles attempted = 116432571, tiles succeeded = 16405961
Total run time = 00:00:29, Total time to find last unique solution = 00:00:10
Average piece order permutation rate = 1239376 / second
Super IQ Cube Solver Software
Download the program
HeinzIQcube.exe, a simple console application without buttons or windowing and its 800
lines of C language source code file HeinzIQcube.c, in
HeinzIQcubeSolved.zip. Run it yourself!
Every 1,000,000 piece order permutations are output to the console screen. Email
me at the address at the bottom of the page and tell me the kind of
computer you used and how long it took to run. This code was
originally written to solve all 9,839 solutions
of the Tetris
cube and with a few trivial tweaks determined all 19,186 unique
solutions of the Bedlam cube puzzle, all
14,177 unique solutions of the Big Brother cube puzzle, all
480 unique solutions of Piet Hein's
Soma cube puzzle
in 10 seconds (note: this linked reference cites only 240 unique
solutions, a mystery for which I'd appreciate a solution from any reader),
both unique solutions of
Hugo Steinhaus' cube in 1 second, and would work for other 3D box-tiling
puzzles. Note there are copyright
restrictions given in the HeinzIQcube.c source module and
readme.txt files to observe
regarding modification of the source code and/or re-publishing the code
or output data file.
Background and Credits
I owe this particular puzzle-solving
adventure to my son Dylan, who had challenged me in March 2008 to find
"even one
solution,
daddy!" and witnessed my struggle to manually restore his Tetris Cube to
its plastic box. I told him there was a way to use a computer to
find every possible solution, so we encoded the cube coordinate
positions of the 12 Tetris cube pieces on paper, and I later put that into this
software over the span of a handful of days. Thank you, Dylan!
Thanks to Jörg Gehrmann in Oberhausen Germany for
bringing the Super IQ cube ("würfel") puzzle to my attention,
and providing the photos of the
product box and pieces, and for verifying the program produced the
correct actual
solution.
In 1986 I wrote a
software program to exhaustively solve and
catalog all solutions of the
2-dimensional pentomino puzzle, to the later
delight of Stanford Professor Emeritus
Donald Knuth, which has
tens of thousands of solutions in various box dimensions (3x20, 4x15,
5x12, 6x10 and 8x8 with several 2x2 hole positions) even after sifting
out reflected and rotated copies. I also have over a
decade of experience creating
and running
supercomputer-capacity
research projects so I was fully prepared to organize any "heavy
duty processing power" required to catalog all the
solutions and verify their number as claimed by the Tetris Cube's creators,
but a laptop computer was enough.
