Sometimes life imitates art, as they say; this is a case where life
imitates code.
It started a half-century ago at least (the story, not the code).
Way back when I was in elementary school, Dad gave me the idea of
making “Soma cube”s out of wood. I don’t
know how many of these I made back in grade school, but a few years ago I started doing
it again.
Then about this time last year, I wondered what it would be like to write
a program to solve the puzzle. This page
has links to the source code
for a solver written in C++; I couldn’t
run it because I don’t do Windows. I soon decided to keep the data
representation but otherwise write a new solver in Python.
The solver places the “T” piece in the only way possible (as
explained here in the wikipedia article), then places the “L” piece
in one of 28 unique positions. Here “unique” means never having
to say “that’s a reflection of a previously-described solution”;
ask me for details or see the code if you’re hungry for details.
Anyway, the other pieces—V, Z, A, B, P (wikipedia’s
nomenclature)— get placed after T and L.
Consulting a recent output, I discovered that the “V” has
103 possible placements (by “possible” I mean given the position
of “T”), whereas the “P” has only 42. For some
reason I had the intuition that placing the “P” first would use
less CPU time.
I ended up coding a sort step so that the solver would place the
“hardest” piece (the “P”) first, and then the pieces
with increasing numbers of possible placements, and finally the “V”
last. How much of a difference does it make? I don’t recall, but I’ll
just try it now on a 2.4GHz Intel Q6600:
$ time ./soma2-unsorted.py > s2-unsorted.out
real 3m46.587s
user 3m46.564s
sys 0m0.004s
$ time ./soma2.py > s2-sorted.out
real 0m38.732s
user 0m38.720s
sys 0m0.008s
$
That’s 226.6 seconds
vs. 38.7 seconds, a nontrivial difference.
Fast-forward to earlier this month. I was thinking again about wooden
puzzles and wikipedia told me about the “diabolical cube”,
with only 13 solutions, and it’s here that life imitates code.
Because of my experience with the Soma cube solver, I immediately
started by placing the
“hard”est-to-place pieces first, and then try to place the
easier ones. By proceeding that way, I figured out the first several
solutions. But to get the rest of them, I modified the Soma cube
solver… after a few tries it worked, completing in about a second.
Here’s an actual run on the same box as above:
$ time ./diacube.py > d.out
real 0m0.978s
user 0m0.976s
sys 0m0.000s
$
The 7-cube piece must be placed parallel to a face of the desired
3x3 cube; it can be
- actually on a face—in this case, the rest of the
pieces determine a unique solution; or
- between two faces—in this case, it’s possible to create solutions that are reflections
of each other. I could have avoided this by coding for placement of the
second piece (I would have done this to the 6-cube piece) but instead
opted to write a little code to keep only one solution out of a pair of
reflections.
There wouldn’t be many of these, because my program produced
17 solutions, whereas Wikipedia told me there were only 13. So it computed
only 4 redundant solutions, and it would take longer to think about unique
placements than it would be to write the code to find reflections.
Or so I thought. I goofed up the code that looked for reflections,
because I had forgotten that my solutions contained references to
each polycube’s placement. In computing a reflection, I trashed the
original polycube. A rookie error.
Anyway, if you ever get your hands on a “Diabolical cube,”
it’ll be a lot easier to solve if you place the 7-cube piece and the
6-cube piece and the 5-cube piece first.
For reference, I’ll give you the 13 solutions, after some blank space
if you want to avoid the spoiler :)
No comments:
Post a Comment