Often during the holidays, I do a little programming project based on something that just strikes my fancy. For example, one year I merged a bunch of dictionaries and then ran the words through DNS to see if they were available as domain names.
This year, my Mother -- Provider of Perfect Presents -- gave one of my sons an interesting puzzle called the "Complex Cube". It has 54 T-shaped wooden parts, each made of 4 unit cubes, and the challenge is to assemble them into a 6x6x6 cube.
I played with it a little bit, and soon got to the point where I realized it might be faster to write a program to analyse the problem, so given that I am a lazy person, I wrote a python script to solve it. It's really pretty simple, you just start at the bottom and scan across the rows and columns in each row, placing blocks in each empty position.
There are some easy optimizations you can do, like realizing there are only 12 possible block rotations you need to try because of assumptions you can make about positions you have already filled in, but the script still took anywhere from 5 minutes to 5 hours to generate a solution, even after doing some cute hacks to make it faster (like not using recursion, but keeping track of things with a state stack).
Then I realized that if I limit the search to solutions that are reflectively symmetric, the search space becomes much smaller, because I'm only solving a puzzle with 27 blocks instead of 54. Solution time goes down to under a minute and the solution looks nicer.
However, the output left a little to be desired...
Level 1
+-------------+
| P I N N N Q |
| L I M N H O |
| E I J K H H |
| E E G F H D |
| E A F F F D |
| A A A B C D |
+-------------+
Level 2
+-------------+
| P P M Z Q Q |
| L I M K X O |
| L J J K X O |
| V W G K X Y |
| T U G B C D |
| R R R B C S |
+-------------+
...and so on. So I got the idea of playing around with the Processing language to see if I could visualize it better. The result was a little script that displays the cube in 3D, lets you rotate and zoom it, and animates the solutions.
Needless to say, it took me twice as long to write the Processing visualization script as it did to write the Python solvers, and it probably took me twice as long to write the solvers as it would have taken to just solve the puzzle by hand.
But then, as I said above, I'm lazy... :)
You can find the scripts here if you'd like to play with them. Processing is built on top of Java and quite fun to play with.
Posts
