Counting Rounded Pentominoes

In mid-June 2010 I got interested in a variation on the pieces: "rounded polyominoes". I found some information and diagrams of them on Miroslav Vicher's Puzzles Pages. The last image on this page (the 22 rounded tetrominoes packed into a corner-cut square) I used as inspiration to make yet another laser cut puzzle:

[IMAGE]

As one can see, rounded polyominoes differ significantly from the standard pieces. Using circles as the unit cells instead of full squares, when laid out in a lattice/grid, there is space between diagonal neighbors. One can then connect diagonally adjacent cells with a "bridge" (standard polyominoes only use squares connected orthogonally). This yields many more possible shapes for pieces. Here is a comparison between standard polyominoes and their rounded cousins based on their sizes/orders:

Order	Standard	Rounded	Polyplets
1	1	1	1
2	1	2	2
3	2	5	5
4	5	22	22
5	12	99	94
6	35	580	524

In addition to the much greater number of pieces formed at each order, there are some other interesting things one should note about rounded polyominoes. First, these are not the same thing as constructing augmented polyominoes by allowing corner-to-corner connections instead of only edge-to-edge. Those shapes, known as "polyplets", "polykings" (since they represent the eight directions a king can move on a chessboard) or "pseudo-polyominoes", are similar in idea to rounded polyominoes, but there is an important difference.

A polyplet is defined only by the cells/squares used to form the shape (like the original, standard polyomino). A rounded polyomino, however, has its character defined by the bridges or links used to join those cells. The filled-in cells come along for the ride in the design of the pieces, but it's the bridges between the cells that are critical. It is quite possible for two rounded polyominoes to use the same cells, but, in fact, be different pieces, as illustrated here (with a pair of rounded pentominoes):

Because of these distinctions, the number of rounded polyominoes is greater than the number of polyplets once the order gets above 4. The first six orders of polyplets are also included in the table above for comparison.

For tangible puzzle pieces the rounded polyominoes are better than the polyplets because the bridges provide an actual, physical link between diagonal cells. When basic square cells are used in the polyplets, they meet only, literally, at the corners, and this does not provide a real link in the physical world. When the corners of these square cells get rounded off, then room for bridges becomes available and the rounded versions of the pieces are generated (using perfectly round circles for the cells in rounded polyominoes is simply an extreme case of rounding the corners off of a square).

Related to the bridge-issue of these pieces is the second important characteristic of rounded polyominoes: the loops that are possible in high-order pieces. In all three types of polyominoes discussed so far, loops (and the holes they form within pieces) will eventually form when enough component cells are linked. In standard polyominoes, one can see a loop and it's associated hole crop up at order-8 (and, actually, the hole appears without the loop fully formed at order-7, also shown):

Holes in pieces are a bit troubling for puzzlers when they are trying to fill or pack an area with pieces. Obviously it would be impossible to completely fill an area with all of the 8-ominoes since that hole cannot be filled. Even the holey 7-omino piece is troublesome within the realm of standard polyominoes, but that one can be filled using a polyplet since diagonal connections are allowed (but again, actually creating a true, physical polyplet with a diagonal connect is impossble).

In the realm of rounded polyominoes, loops and holes can still appear, but some of the problems are avoided. For example, the order-7 holey piece above is avoided all together and replaced by this version in rounded polyominoes (shown schematically with cells as solid circles and bridges as connecting line segments):

It uses the same cells, but the diagonal bridge which could close off the loop is omitted and access to the area within is available to other pieces.

The 8-omino analogy of the holey piece above still causes problems, however since it looks like this:

In that piece, no bridge removal will open up the hole since the cells (not bridges) are all still present.

This brings up the most important issue with loops in the rounded polyomino universe: not all loops are created equal. Avoiding loops and unreachable holes is one of the main advantages of working with these pieces, but obviously it does not solve all of the problems. So then, the question is, which loops are avoidable, and which are not?

This was one of the trickiest issues to address when writing a program to generate all of the pieces of a given order. Being able to codify which loops could be broken without destroy the cell integrity and over structure of the polyform while also knowing which loops had to remain.

The answer boils down to this: if a candidate piece has a loop in it and that loop has a "weak diagonal bridge" anywhere in it, then that bridge can be omitted and the loop opened up. What is a "weak diagonal bridge"? It is a diagonal bridge between two cells of a rounded polyomino which has not "support" from either of the remain two cells in the associated 2x2 subset of cells which the diagonal bridge is a part of. If either of those two other cells is occupied by a cell in the form, then the diagonal is not weak, it is "strong" and omitting the diagonal would not open up any loops. Here are some diagrams to help illustrate the difference between weak and strong loops:

[IMAGE]

One should be aware of the degenerate loop case formed by three adjacent cells forming a small, right angle "L":

[IMAGE]

This is technically a loop formed by the three bridges, but since there is not an interior cell being surrounded, we shouldn't consider it a loop that needs to be opened up.

All of these issues came up when I started to write a computer application to generate the rounded polyominoes of various orders. I found that, while many variations of standard polyominoes have been studied ad nauseum, very little information seemed to be available (on the public internet, at least) on these rounded versions.

I had found the numbers of rounded polyominoes for the orders up through 6 (as listed above); they, in fact, form the On-line Integer Sequence A056840. And Vicher's website, above, even gave diagrams of all of the pieces up through order 5.

But, by this point, I was very curious to know more. Namely, what do the 580 rounded hexomino pieces looks like as a complete set, and could they possible fill a rectangular area of dimension 58x60 (the area calculations suggest that might be possible, but there are many other factors which could potentially prevent the 580 pieces from packing to that area perfectly).

And beyond order 6, what were the counts for larger sets of pieces. How many rounded heptominoes (7-ominoes) are there? how many octominoes? and so forth. The number of standard pentominoes have been calculated (though not always confirmed) up to much higher orders (about order 45, I think), so why were these rounded polyominoes being neglected?

My writing of a program was meant to address this somewhat.

- Eric Harshbarger, 27 Jun 2010