»  Solutions to puzzles in my National Review Online Diary

  September 2011

—————————

In my September diary I posed this brain-teaser, from a reader claiming: "This puzzle arose out of work I was doing for a client, Solyndra."

It is a tiling problem of sorts, arising out of placing solar panels on a roof.

We wish to mount a group of solar panels on a roof. Let's use 15 as an example. The mounting system requires that each panel touch at least one other along an edge. The panels are rectangular, and all must be oriented the same way.

Obviously we could create a 3×5 grid. We could simply string the 15 panels in a row. We could create a 4×4 grid with one hole. There are many, many combinations that meet the constraints. But, for a given number of panels, exactly how many?

(On a practical basis, this comes up because roofs have projections — chimneys, vents, etc, and you must install around them. We usually solve it empirically.)

After a fair amount of noodling, I decided I didn't have enough math to solve it. It's easy, for example, to determine the number of ways you can select 15 items from a set of 225 (15×15) but many of those selections are illegal. Panels must be coterminous along at least one edge.

Is this trivially simple? Or interesting? Or brute-force only?

—————————

Solution

For sure not trivially simple: in fact, no general solution is known.

The topic here is polyominoes — assemblies of squares, each joined to at least one other along an edge. It's a large and much-explored topic. The answers you get depend on various conditions: e.g. do enantiomorphs (mirror-images, like a pair of gloves) count as two solutions, or only one?

There's a good summary here. Note that the first and the fifth of the Tetris pieces shown are enantiomorphs; so are the second and the sixth.

Note also that the various columns of numbers in that link can all be found on the Online Enyclopedia of Integer Sequences. The first column is sequence A071764, the second is A000105, etc. That second one is probably the best match for what my reader seeks.