One morning, Grady walks into the office and leaves a couple of wooden puzzles on the shared table in the Data Management Team area. Many of us were nerd-sniped that day. This is a tale of how one single puzzle frustrated Developers, Software Architects, and even a Director of Engineering.

The puzzle is Calibron 12, named for the number of pieces it has (twelve). The instruction reads:

Put all the pieces in the large opening. A very difficult puzzle invented in 1933 by Theodore Edison, son of inventor Thomas Edison.

The goal of the puzzle is to create a perfect square from the 12 rectangular pieces, fitting inside the square opening. (The original version was even harder; it did not give you the size of the final solution, nor did it tell you that it would be square, only rectangular!)

A nerd is sniped every 42 minutes. Please think of the nerds

Throughout the day, people would come by to try it, and inevitably give up. It is a very hard puzzle and it has some nefarious elements. For example, some of the pieces differ in their dimensions by just 1 unit (the creators were nice enough to label the dimensions of each piece). There is both a 28 * 7 piece and a 28 * 6 piece. There is both a 32 * 10 and a 32 * 11 piece. There are also duplicates: two 21 * 18 and two 21 * 14 pieces!

By the end of the first day, someone in the office had measured the size of the board to be 56 * 56 square. Noticing that 56 is a multiple of 7, Pat thought about grouping pieces by their side length modulo 7. Independently, Sheri tried grouping side lengths into even and odd values. Neither strategy seemed to help much. Later, I would understand why – there are 668 ways to get 56 by choosing at most one side from each piece!

I tried to get into the mind of the creator. “If I were Theodore Edison, how would I break up a square into smaller rectangles?” A few whiteboard scribbles suggested that it was easier to have smaller rectangles on the inside than the outside. We also had a hunch that most of the pieces would be staggered, i.e. pieces would never form any partial rectangle in the final solution. One of these hunches would be right.

At one point, there were three of us crowded around the puzzle. While Mike was trying to fit pieces onto the board, I wrote down the dimensions of all the pieces onto an index card. I was hoping to be solve it “offline” – without the physical pieces. Here they are:

• 21 * 18 (2)
• 21 * 14 (2)
• 28 * 14
• 17 * 14
• 4 * 14
• 7 * 10
• 32 * 10
• 32 * 11
• 28 * 6
• 28 * 7

Goal: Make a 56 * 56 square using these pieces.

If all else fails, brute force it

At some point, every programmer inevitably thinks: “How about I just write a program to solve it?” The first thing that comes to mind is a brute force search. We call it brute force when a program simply tries every single possibility without strategy. Brute force is dumb and slow, but it can work if the number of possibilities is small enough. And it only works because computers are decently fast at doing mind-numbingly repetitive tasks.

Brute force programs are really easy to write! If you had 3 things (i, j, k) that each had a set of possible values to choose from, to test all possible combinations is simply a triply nested for loop, like so:

for i in i_values:  
   for j in j_values:
      for k in k_values:
          test(i, j, k) // does (i, j, k) work?

But you have to be careful – the number of combinations is combinatoric (obvious sentence is obvious). The code above runs in n³ time. Why? If each of our 3 variables had 10 values to choose from, there would be 10³ combinations. If they each had 100 values, there would be 100³. If we had 12 variables (say for a certain 12-piece puzzle…) with n possible values each, there would be n¹² combinations! That gets big fast.

Back to our puzzle. Consider this problem formulation:

• There are 12 pieces that need to be placed.
• Every piece must be in one of 2 orientations (horizontal or vertical).
• Every piece must have a position inside the square opening (the board).
• Define a piece’s position (x, y) as the coordinates of its upper-left corner. We can assume integer coordinates because all the pieces have integer dimensions. So let’s restrict x and y to integers between 0 and 55.

With this formulation, every piece has 2 * 56² = 6272 position-orientation pairs to choose from. Alone, that’s a piece of cake for a computer. But with 12 total pieces needing a position and orientation, that’s a total search space of6272¹²
= 3.7 * 10⁴⁵

combinations to try! A brute force search on all these possible solutions would never finish. As a guideline, at 1 GHz, computers can do 10⁹ operations a second, ignoring parallelism. Say your computer was 10 times that fast and it only took 1 cycle to test one combination. This program would still take 10³⁵ seconds, or 10²⁷ years to finish! (For comparison, the age of the universe is estimated at 13 billion = 10¹⁰ years.)

A better solution – What would a human do?

The brute force formulation above is silly. Of course you wouldn’t try all 56 * 56 positions for a single piece. Many of those positions would leave gaps of the wrong size, or would overlap with other already placed pieces, etc. Brute force is dumb, but we knew that.

If you were solving this puzzle by hand, you would pick a piece and try to place it next to an edge, or more likely in one of the corners. Then you would pick another piece and slide it next to the first one, and so on.

We can model this as making a few choices at each step:

1. Choose a piece.
2. Choose an orientation (horizontal or vertical).
3. Place it in the upper-most, left-most corner that hasn’t been occupied yet.

Note that by always selecting the upper-most, left-most corner, we’ve eliminated the choice of where to put the piece. We can do this because in the final solution, we know the entire board will be filled anyway, so it does not matter which location we decide first. This will greatly simplify the search.

But will this search finish? With an empty board, we have 24 choices to choose from – 12 pieces times 2 orientations. (This is already much smaller than the 6272 above.) At each subsequent step, if there are n pieces remaining, then we have 2n values to choose from. There are 12 steps in a complete solution. The total search space is:24 * 22 * … * 2
= 2¹² * 12!
= 1,961,990,553,600

That’s about 1.9 * 10¹² possible combinations to try, which is still huge, but more reasonable than before. There’s that n¹² term again, but this time, n is much smaller. Assuming 10⁹ combinations tested per second, that’s “only” 2000 seconds, or about 33 minutes. In theory, this could work!

Blasted Geometry

But wait! All the calculations above assume that testing a single combination is constant time. We’ve glossed over how to do that as well as how to find the “top-most, left-most” corner. If we’re not careful, we could end up introducing another n² factor by doing something naïve like iterate over a 56 * 56 array of bits to figure out if we filled the board fully. Imagine if we had to do 3136 operations every test – that 33 minutes would become 100,000 minutes….

The hardest part of writing this program is now figuring out how to do the geometry efficiently. How do we find the top-most, left-most corner of a (partially-filled) board? And how do we determine that a piece will or will not fit into that corner? Stay tuned for the answers to those questions in Part 2!

(TO BE CONTINUED…)

• Category: Vena Engineering
• Tag: algorithms, constraint programming, puzzles