freaking puzzle!

This is one for the engineers who read my blog.

Have you ever had one of those days when you can't stop thinking about something totally un-work related, so you decide to just figure it out and get it out of your head...only it ends up taking most of the day? Today was one of those days. Worst of all, after spending way too many hours trying to figure it out, I still couldn't so now I feel both dumb and unproductive!

My officemate has a little wooden puzzle, pictured here:

In this picture, it has been solved. However, normally, it sits in some level of disarray. It lays on the side-table next to my desk and every once-in-a-while, someone will pass by and fidget with it for a few minutes, then give up and go on their merry way.

Yesterday, while driving back from class, I started to think about a possible mathematical solution to this puzzle. When I got to work this morning, I tried for a few hours to resist the temptation to put it to the test, then finally gave up and set out to solve this damn puzzle once and for all.

My theory was simple. The puzzle can be represented by a 10 by 6 element matrix in which a '1' represents a square of wood and a '0' indicates an empty slot. Naturally, when the puzzle is all put together, the matrix would be a 10 by 6 matrix of ones. Each individual piece can be represented in the same way as shown in the following figure:

Matrix (a) shows the numerical representation of the top-left piece in the puzzle alone on the board. If I were to move it to position (4,2) on the board, it would be represented by matrix (b). Of course, each piece has up to eight possible orientations (four directions, two sides if it's not symmetric), so matrix (c) shows this piece rotated to the left by 90 degrees. Using this method, I developed three dimensional matrices to represent each piece in each possible position and orientation on the board. Within these matrices, each layer represented the portion of the board which one piece took up in a particular position and orientation. Using a simple for-loop, I created twelve such matrices, one for each piece, and I was ready to start calculating.

The calculation is rather simple. Using a twelve layered for-loop, add every possible combination of layers from these twelve 3D matrices until the sum yields our goal of a 10 by 6 matrix of ones. When this occurs, break out of the for-loops and query the code for the layers used out of each of the matrices and display them on the screen. Then place the pieces on the board and begin gloating.

...not so fast...

I wrote up the code, started it off and continued working, thinking I would check back in a few minutes and find the answer waiting for me. Instead, I found a blank screen and a very slow computer. It was at this time that I decided to do a quick back-of-the-envelope calculation.

Although it varies with the shape of the piece, each piece can be placed in approximately 30 different positions on the board for each of its eight orientations. Six of the pieces are symmetric about at least one axis, so flipping them yields no new orientations, so half the pieces can take up 30 x 8 = 240 different portions of the board and half of them can take up 30 x 4 = 120 different portions...we'll assume an average of 30 x 6 = 180 portions/piece. There are twelve pieces, and I have to add every possible combination to guarantee a solution.

180^12 = 10^27

10^27 calculations required. On my computer, MATLAB is able to process about 16,000 calculations each second - pretty fast, right? So assuming there are no power outages, hurricanes or other such hindrances, I will have the answer in 1,900 trillion years. That's right, trillion. Raise your hand if you feel stupid...anyone else with their hand up...no, just me? Ok, sounds about right.

So my brilliant little plan to solve the simple wooden puzzle will end up coming to fruition about the same time I have all my student loans paid off - pretty nifty. Now I know how Arthur Dent felt. To add insult to injury, a few minutes after I realized how ridiculous my method was, my officemate solved the GD puzzle. Maybe I should stick to dance!