Vast Search Space
The Big Brother cube
(würfel
in German) is
composed of 13 pieces, 12 pieces each having 5 cubes plus a single 4-cube piece. Of the 13 puzzle pieces,
6 may be rotated into 24 possible orientations, 6 may be rotated into 12
possible orientations, and 1 may be rotated into 3 possible orientations. This means there are 246
x 126
x 31 = 1,711,891,286,065,152 (about 1.7 quadrillion) possible
piece orientation combinations to try. The pieces may also be fitted, or
'tiled', into the 4x4x4 cube in 13! = 13x12x11x(...)x2x1 =
6,227,020,800 possible piece ordering permutations. The product of these
numbers is 10,659,982,645,666,451,659,161,600 (over 10 billion trillion) steps to try every possible
orientation of every possible piece order permutation!
Because the cube is a
rather snug 4x4x4 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 Big Brother 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 example, the initial piece
order is 1,2,3,4,5,6,7,8,9,10,11,12,13. The next is
2,1,3,4,5,6,7,8,9,10,11,12,13 and then 3,1,2,4,5,6,7,8,9,10,11,12,13 etc.
When the permutations are fully exhausted the piece order is, finally,
13,12,11,10,9,8,7,6,5,4,3,2,1. For the initial permutation, say pieces
1 and 2 are already in the box but none of the orientations for piece 3
fit. For this example, that would indicate 13!/(13-11)! = 3,113,510,400 permutations 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 10 billion trillion
figure above, bringing it into reach of a software program. NOTE: the
software internally uses piece numbers 0-12 rather than 1-13.
Of the 6,227,020,800
possible piece ordering permutations only 340,248 produce a completed
cube (see below, Search Results). This means you have about 1 chance
in 18,301 that a random lineup of the pieces can be put into a cube.
No wonder it's not so easy! The Big Brother cube is therefore about 1.4 times
harder than the Bedlam cube for which you have about 1 chance in 13,523,
and 9.0 times harder than the Tetris cube, for which you have about 1 chance in 2,028.
Search Algorithm
Each of the 13 pieces is arbitrarily
assigned a unique number, 1 to 13 (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 to
1,2,3,4,5,6,7,8,9,10,11,12,13 and the orientation of each piece is reset
to 1.
A 4x4x4 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-12 rather than 1-13.
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.
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.
Only new unique solutions are then added to the catalog as the
permutation sequence progresses, guaranteeing the correct catalog is
produced.
 |
|
Diagram of the 13
Big Brother Cube pieces
and the arbitrary numbers 1 to 13 assigned to each in the
software program and solutions catalog.
Pieces 1 to 9 are labeled by their
own numbers and 10, 11, 12 and 13 are labeled A, B, C and D, respectively, in
the solutions catalog.
Piece 1 has 5 cubes, labeled
blue 'flat-X-plus'
Piece 2 has 4 cubes, labeled blue 'squiggle'
Piece 3 has 5 cubes, labeled white 'twist-right'
Piece 4 has 5 cubes, labeled blue 'bent-Z'
Piece 5 has 5 cubes, labeled white 'bent-L-right'
Piece 6 has 5 cubes, labeled blue
'bent-club'
Piece 7 has 5 cubes, labeled blue 'Z'
Piece 8 has 5 cubes, labeled white 'twist-left'
Piece 9 has 5 cubes, labeled blue
'bent-L-mirror'
Piece 10 has 5 cubes, labeled blue 'bent-T'
Piece 11 has 5 cubes, labeled white 'flat-U'
Piece 12 has 5 cubes, labeled blue
'dislocated-plus'
Piece 13 has 5 cubes, labeled blue
'twisted-S' |
Search Results
Exactly
14,177 unique
solutions were found. Because of rotational symmetry my software
actually assembled 24 x 14,177 = 340,028 cube solutions but it discarded
exactly 326,071 duplicates as 23 additional rotational copies of each
unique solution. The software search completed in 46 hours on my
old 2 GHz Pentium 4 laptop. The 14,177 unique solutions, however, were
found within the first 16 hours and the remaining 30 hours completed
permutations that resulted in rotational copies. The search space was,
as expected, enormously reduced to a 'mere' total of exactly
154,759,062,293 (154.8 billion) piece order permutations visited,
including dead-end orientation paths. The program attempted to fit
pieces into the box exactly 2,130,086,330,448 (2.1 trillion) times and
succeeded fitting them exactly 61,009,375,371 (61 billion) times.
Indeed, 2.1 trillion is MUCH smaller than 10 billion trillion!
Big Brother Cube Solutions
Below is the software's
startup analysis, the first 3 of the entire
solutions catalog, and the search conclusion outputs, rigorously
determined using 'brute-force' combinatorial techniques (color
added for web page annotation). Pieces are mapped to numbers 1-13 and their
identification is aided by the descriptive cube counts, colors and labeling
in agreement with the diagram above. The solutions are given in layers of the 4x4x4 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, 11, 12 and 13 are given as
A, B, C and
D respectively.
It takes a bit of
visualization to see the pieces in the printed solutions and it helps to
refer to the diagram above. In Solution 1
below piece 1 is outlined, resting entirely in the bottom cube layer. Particularly challenging to visualize are pieces spanning cube
layers, such as piece A (#10) (blue 'bent-T'),
which in the outlined example in Solution 1 spans the top (leftmost)
layer through layers 2 and 3. Get out your Big Brother cube and
try it... it's rather easy once you get the hang of it.
Big Brother Cube Solver, (c)2009 www.scottkurowski.com
Piece 1 has 5 cubes, labeled blue 'flat-X-plus'
Piece 2 has 4 cubes, labeled blue 'squiggle'
Piece 3 has 5 cubes, labeled white 'twist-right'
Piece 4 has 5 cubes, labeled blue 'bent-Z'
Piece 5 has 5 cubes, labeled white 'bent-L-right'
Piece 6 has 5 cubes, labeled blue 'bent-club'
Piece 7 has 5 cubes, labeled blue 'Z'
Piece 8 has 5 cubes, labeled white 'twist-left'
Piece 9 has 5 cubes, labeled blue 'bent-L-mirror'
Piece 10 has 5 cubes, labeled blue 'bent-T'
Piece 11 has 5 cubes, labeled white 'flat-U'
Piece 12 has 5 cubes, labeled blue 'dislocated-plus'
Piece 13 has 5 cubes, labeled blue 'twisted-S'
Piece 1 has 3 unique rotational orientations
Piece 2 has 12 unique rotational orientations
Piece 3 has 24 unique rotational orientations
Piece 4 has 12 unique rotational orientations
Piece 5 has 24 unique rotational orientations
Piece 6 has 24 unique rotational orientations
Piece 7 has 12 unique rotational orientations
Piece 8 has 12 unique rotational orientations
Piece 9 has 24 unique rotational orientations
Piece 10 has 24 unique rotational orientations
Piece 11 has 12 unique rotational orientations
Piece 12 has 24 unique rotational orientations
Piece 13 has 12 unique rotational orientations
[ NOTE: The remaining 14,174 solutions are omitted here.
To download the full catalog click BigBrotherCubeSolved.zip ]
All permutations exhausted, 14177 unique solutions found, 326071 duplicate rotations discarded
Total permutations = 154759062293, tiles attempted = 2130086330448, tiles succeeded = 61009375371
| Did my cube
solutions help? Aw, you know it did! Toss me a bone
here -- click the donate button!
|
Big Brother Cube Solver Software
Download the program
BigBrotherCube.exe, a
simple console application without buttons or windowing and its 700
lines of C language
source code file BigBrotherCube.c, in
BigBrotherCubeSolved.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
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 bigbrothercube.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 also to Jörg Gehrmann in Oberhausen Germany for
bringing the Big Brother cube ("würfel") puzzle to my attention, providing the photo of the
product, the pieces diagram, and verifying the program produced actual
solutions.
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.
