Polystick Problems from Polyomino Solutions

September 7th, 2010 by munizao Leave a reply »

Polysticks (or polylines) are connected sets of segments in a square grid. (Polysticks on other grids are possible, but haven’t seen much attention.) The tetrasticks, of which there are 16, seem to be the most natural set for puzzle making. Donald Knuth has explored tetrastick problems, and posed the problem of tiling an Aztec Diamond with the 25 one-sided tetrasticks, which was solved by Alfred Wasserman. Here’s one I’ve come up with:

Problem #15: Tile the above shape with two sets of the five tetrominos and one monomino, and tile the borders of these polyominoes with the 16 tetrasticks. Here’s an attempt I made that fell short by a few tetrasticks, but it should give you an idea of the form a solution would take:

The observation that the lines formed by the pieces in a polyomino tiling could themselves be tiled by polysticks seems obvious, but I have not seen it elsewhere. After picking the 16 tetrasticks as my puzzle pieces for the polystick stage, I had to find a set of polyominoes to use. Since one of the tetrasticks is, in fact, the outline of a 1×1 square, or monomino, the monomino had to be present. A double set of tetrominoes plus the monomino gives a good quantity of segments for our tetrasticks to cover, and gives us an area of 2 * (5*4) + 1 = 41. The perimeter of the figure to be tiled is constrained by the following formula:

2 * total segments in the polystick set – sum of perimeters of polyominoes = perimeter of entire figure

In this case, (2 * (4 * 16)) – (4 + 2 * 48) = 28

So I needed a figure to tile with area 41 and perimeter 28, and came up with the shape above.

There are 136 solutions for the tetromino tiling with the monomino in the center as shown. (See these solutions in a Java solver applet.) I’ve experimented a little with the tetrastick stage of the problem by hand, and I’m convinced that there are no tetrastick solutions for most, if not all, of these tetromino solutions. But if it doesn’t work out in the case with the monomino in the center, I suspect there are enough solutions with the monomino elsewhere for it to be very likely that one will work. Many of the tetromino solutions fail to contain a site where the “+” tetrastick can be placed that doesn’t overlap the “□”.

Another issue that surfaces in this problem is horizontal-vertical segment parity. Eleven of the tetrasticks have even parity, that is, however you place them, they will always contain even numbers of both horizontal and vertical segments. Five of them have odd parity, and will always contain three segments of one orientation and one of the other. Because there are an odd number of pieces of odd parity, the parity of the set of tetrasticks as a whole must be odd. This means, without even starting to try placing tetrasticks on a tetromino solution, we can rule out the possibility of tiling it just by counting the number of horizontal or vertical segments. (Because the total is constant, we don’t need to count both.) If that number is even, the tetrasticks can’t tile the figure. The tetromino solution that I used in my attempt above has the correct (odd) parity.

I dredged this problem up from my archive of the polyforms mailing list, where I posted it in February, 2001. It got no takers then, but I thought it an interesting enough problem to deserve a second airing. I looked for other problems of this type in preparing this post, but I didn’t find anything good. Having both the area and the perimeter of the figure to be tiled constrained by the pieces used limits the possibilities a lot.


  1. Lewis says:

    >I dredged this problem up from my archive of the polyforms mailing list,

    Are there any mailing lists or forums relating to polyominoes/polyforms which are still active now?

  2. munizao says:

    The polyforms mailing list I was referring to is the Yahoo group. It’s only mostly comatose, and has had a slight uptick in activity over the last year.

    If there’s anything else out there, I’d certainly like to know about it.

  3. Debbie says:

    The tetrasticks are related to the pentominoes. I would suggest using the pentomino names: FLIPNTUVWXYZ, adding O for the square tetrastick and P1 P2 P3 P4 to refer to the 4 tetrasticks that have vertices at the positions of a P pentomino.

  4. munizao says:

    Actually, I’ve given a bit of thought to the “orthography” of tetrasticks. I do mostly use the pentomino names. For the “P” derived tetrasticks, I prefer using letters that look something like the tetrasticks themselves; if I called them P1 etc., I’d have to memorize which was which without having the shape for a mnemonic. I also find that it’s useful to have a single symbol representing each form.

    For the P derived tetrasticks, I’ve settled on ‘J’, ‘H’, (which is clearer if you think of a lower case ‘h’) ‘?’, (a little unfortunate to have to use a punctuation mark, but the resemblance is very clear compared to any letter I could have used) and ‘F’. The last conflicts with the F pentomino derived tetrastick, but it is so clearly shaped like an ‘F’ that it deserves the title. The F pentomino derived tetrastick I’ve switched to ‘R’, which is what John Conway called it. (O for the square tetrastick is indeed probably best.)

    But for the purpose of the above article I didn’t want to get into introducing an orthography, so I used the ‘+’ and ‘□’ characters, which have the benefit of being immediately recognizable as particular tetrasticks without any explanation required.

Leave a Reply