« Boston Python puzzles

Block Party

Another little known use of Python programming is solving real-world block puzzles.

Take for example the notoriously difficult 12-Block Calibron puzzle. It was invented by the son of Thomas Edison. Or at least, he got the credit for it. (Like father, like son.)

It seems simple: you've got 12 rectangular tiles with these dimensions:

or, as a Python-ready list:

tiles = [
    (32, 11),
    (32, 10),
    (28, 14),
    (28, 7),
    (28, 6),
    (21, 18),
    (21, 18),
    (21, 14),
    (21, 14),
    (17, 14),
    (14, 4),
    (10, 7),
]

(Yes, there are duplicates in the list, you have pairs of blocks of the same size.) All you have to do (ha!) is arrange them so they form a single rectangle with no gaps.

The problem is that the search space is very big. So this cries out for a computational approach.

1. What is the total surface area of the final solution?

2. OK that was easy. But how about the height and width of all possible (or let's call them, potential) rectangle solutions? Write a program that generates that list.

3. Finally, the really hard part. Write a program that searches for a solution to the 12-Block Calibron puzzle. (Apparently there is only one.)

4. Bonus: How unique is the 12-Block Calibron within puzzle space? What makes an n-block Calibron a good puzzle, that has one and only one solution? Write a program that generates n-block Calibron puzzles.

Solutions

• Ned Batchelder's solution is calibron.py
• Andrew Ross's solution is calibron.py

If you have a solution you'd like to share see the Solutions page for instructions.