Vast Search Space
The Bedlam / Crazee cube is
composed of a subset of the possible 3-D pieces derived from the twelve
2-D pentominos, each having 5 cubes, plus a single 4-cube piece. Of the 13 puzzle pieces,
7 may be rotated into 24 possible orientations, 5 may be rotated into 12
possible orientations, and 1 may be rotated into 3 possible orientations. This means there are 247 x 125
x 31
= 3,423,782,572,130,304 (over 3 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 42,639,930,582,665,806,636,646,400 (over
42 million quadrillion, or over 42 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 Bedlam 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 0,1,2,3,4,5,6,7,8,9,10,11,12. The next is
1,0,2,3,4,5,6,7,8,9,10,11,12 and then 2,0,1,3,4,5,6,7,8,9,10,11,12 etc.
When the permutations are fully exhausted the piece order is, finally,
12,11,10,9,8,7,6,5,4,3,2,1,0. For the initial permutation, say pieces
0 and 1 are already in the box but none of the orientations for piece 2
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 42 million quadrillion
figure above, bringing it into reach of a software program.
Of the 6,227,020,800
possible piece ordering permutations only 460,464 produce a completed
cube (see below, Search Results). This means you have about 1 chance
in 13,523 that a random lineup of the pieces can be put into a cube.
No wonder it's not so easy! The Bedlam cube is therefore about 6.7 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, 0 to 12 (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 and build a quick reference
lookup table. The piece order permutation order is initialized to
0,1,2,3,4,5,6,7,8,9,10,11,12 and the orientations of each piece are reset.
A 4x4x4 3-dimensional box is encoded and the initial empty cube is
scanned starting at (x,y,z) coordinates (1,1,1).
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
Bedlam/Crazee Cube pieces
and the arbitrary numbers 0 to 12 assigned to each in the
software program and solutions catalog.
Pieces 0 to 9 are labeled by their
own numbers but 10, 11 and 12 are labeled A, B and C, respectively, in
the solutions catalog.
Piece 0 has 5 cubes, labeled blue 'flat-R'
Piece 1 has 5 cubes, labeled red 'flat-X-plus'
Piece 2 has 5 cubes, labeled yellow 'flat-W'
Piece 3 has 5 cubes, labeled red 'bent-W-tip'
Piece 4 has 5 cubes, labeled yellow 'folded-X'
Piece 5 has 5 cubes, labeled red 'z-bump'
Piece 6 has 5 cubes, labeled yellow 'bent-T'
Piece 7 has 5 cubes, labeled red 'tall-L-bump'
Piece 8 has 5 cubes, labeled yellow 'twisted-Z'
Piece 9 has 5 cubes, labeled yellow 'L-bump-end'
Piece 10 has 5 cubes, labeled blue 'squiggle'
Piece 11 has 5 cubes, labeled blue 'bent-R-tip'
Piece 12 has 4 cubes, labeled yellow 'squiggle' |
Search Results
Exactly
19,186 unique
solutions were found. Because of rotational symmetry my software
actually assembled 24 x 19,186 = 460,464 cube solutions but it discarded
exactly 441,278 duplicates as 23 additional rotational copies of each
unique solution. The software search completed in 86 hours on my
old 2 GHz Pentium 4 laptop. The 19,186 unique solutions, however, were
found within the first 30 hours and the remaining 56 hours completed
permutations that resulted in rotational copies. The search space was,
as expected, enormously reduced to a 'mere' total of exactly
166,604,324,836 (166.6 billion) piece order permutations visited,
including dead-end orientation paths. The program attempted to fit
pieces into the box exactly 2,407,717,843,902 (2.4 trillion) times and
succeeded fitting them exactly 66,924,356,081 (66.9 billion) times.
Indeed, 2.4 trillion is MUCH smaller than 42 million quadrillion!
Bedlam / Crazee 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 0-12 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 0 to 9 are given
in the solutions by those numbers, and pieces 10, 11 and 12 are given as
A, B,
and C 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 B (blue 'bent-R-tip'),
which in the outlined example in Solution 1 has the 'bent-tip' on the end of
the 'R' in the third layer next to the A cubes,
and two cubes going up into the second layer, and finally a single cube
in the (leftmost) top layer. Get out your Bedlam cube and
try it... it's rather easy once you get the hang of it.
Bedlam Cube Solver, (c)2008 www.scottkurowski.com
Piece 0 has 5 cubes, labeled blue 'flat-R'
Piece 1 has 5 cubes, labeled red 'flat-X-plus'
Piece 2 has 5 cubes, labeled yellow 'flat-W'
Piece 3 has 5 cubes, labeled red 'bent-W-tip'
Piece 4 has 5 cubes, labeled yellow 'folded-X'
Piece 5 has 5 cubes, labeled red 'z-bump'
Piece 6 has 5 cubes, labeled yellow 'bent-T'
Piece 7 has 5 cubes, labeled red 'tall-L-bump'
Piece 8 has 5 cubes, labeled yellow 'twisted-Z'
Piece 9 has 5 cubes, labeled yellow 'L-bump-end'
Piece 10 has 5 cubes, labeled blue 'squiggle'
Piece 11 has 5 cubes, labeled blue 'bent-R-tip'
Piece 12 has 4 cubes, labeled yellow 'squiggle'
Piece 0 has 24 unique rotational orientations
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 24 unique rotational orientations
Piece 8 has 12 unique rotational orientations
Piece 9 has 24 unique rotational orientations
Piece 10 has 12 unique rotational orientations
Piece 11 has 24 unique rotational orientations
[ NOTE: The remaining 19,183 solutions are omitted here.
To download the full catalog click BedlamCubeSolved.zip ]
All permutations exhausted, 19186 unique solutions found, 441278 duplicate rotations discarded
Total permutations = 166604324836, tiles attempted = 2407717843902, tiles succeeded = 66924356081
| Did my cube
solutions help? Aw, you know it did! Toss me a bone
here -- click the donate button!
|
Bedlam / Crazee Cube Solver Software
Download the program
bedlamcube.exe, a
simple console application without buttons or windowing and its 700
lines of C language
source code file bedlamcube.c, in
BedlamCubeSolved.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
480 unique solutions of Piet Hein's Soma cube puzzle
in 10 seconds (note: this linked reference cites only 240 unique
solutions),
both unique solutions of
Hugo Steinhaus' cube in 1 second, all
14,177 solutions of the Brother Cube, and would work for other 3D box-tiling
puzzles. Note there are copyright
restrictions given in the bedlamcube.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 recently challenged me to find 'even one
[Tetris Cube] 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!
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.
