Posts Tagged ‘polysticks’

A Polyformist’s Toolkit: Symmetry Variations

May 25th, 2012

It lately occurred to me that there are concepts that I use (and see used by others) in creating variations on polyform puzzles that I haven’t seen explained very thoroughly, and it might be helpful if I used this space for just that purpose.

Some polyomino puzzles using symmetry variations

The first of these is the use of different kinds of symmetry in defining the set of pieces used in a puzzle. (I touched on this in my post on rectangular-cell pentominoes.) Normally, all combinations of rotations, translations, and reflections of a polyomino in a grid are considered to be equivalent. Leaving aside translations for the moment, the possible rotations and reflections of a polyomino are equivalent to the group of symmetries of a square. We can find variations on polyominoes by restricting the allowed symmetries to subgroups of that group. For example, the one-sided polyominoes are the result of allowing only rotations, not reflections. Rhombic cell pentominoes (which Kadon sells) allow 180° rotations, plus diagonal reflections. My Agincourt puzzle allows only reflections over vertical axes, assuming that the arrows are pointing vertically. Notice that it doesn’t matter which direction the arrows point as long as they point in the same direction; this suggests that what we are interested in isn’t symmetry subgroups per se, but classes of subgroups where two subgroups that are related to each other by symmetries of the square are equivalent.

What are all of the possible variations with different allowed transformations? We can generate a representative subgroup of every class by using some combination of reflection over a particular axis parallel to the grid, a particular diagonal axis, and 90° and 180° rotations. Here’s a chart of the symmetry variations this produces.

  Polyomino Type Reflection Rotation # of Symmetries
Free Either 90° 8
Parallel (a.k.a. Rectangular) y axis 180° 4
Diagonal (a.k.a. Rhombic) x=y 180° 4
One-sided None 90° 4
Oriented Parallel y axis None 2
Oriented Diagonal x=y None 2
Polar One-sided None 180° 2
Fixed None None 1

I chose the above terminology for the types (after keeping “free”, “one-sided”, and “fixed” as established terms) in order to build in some helpful mnemonics. The types with four symmetries have short names. The types with two symmetries have longer names based on the names of the types whose symmetry groups their symmetries are subgroups of. The odd duck here is “polar one-sided”, which is a subgroup of all of the larger symmetry groups, but putting “one-sided” in its name makes the types with two symmetries nicely echo the names of those with four.

Here’s a chart of the number of polyominoes of each type for a given size:

Polyomino Type 1 2 3 4 5 6 7 OEIS #
Free 1 1 2 5 12 35 108 A000105
Parallel 1 2 3 9 21 68 208 A056780
Diagonal 1 1 3 7 20 62 204 A056783
One-sided 1 1 2 7 18 60 196 A000988
Oriented Parallel 1 2 4 12 35 116 392 A151525
Oriented Diagonal 1 1 4 10 34 110 388 A182645
Polar One-sided 1 2 4 13 35 120 392 A151522
Fixed 1 2 6 19 63 216 760 A001168

(The odd entries for the polar one-sided polyominoes track those for the oriented parallel polyominoes exactly for several terms, before eventually diverging. There are 4998 9-ominoes for both, and 67792 polar one-sided, and 67791 oriented parallel 11-ominoes. It seems unlikely that this is a coincidence. Does anyone know why this occurs?)

These types can be realized geometrically by replacing square cells in a planar tiling with cells with the appropriate symmetry. Another way they can be realized is by keeping the cells square and marking them with a figure with the appropriate symmetry. This is essentially what I did by cutting arrow shaped holes in the Agincourt pieces. The latter method allows the possibility of mixing different symmetry types in the same tiling. I don’t believe I’ve seen such a problem before, so let me be the first to fill what may be a much needed gap:

Problem #28: Tile a 6×6 square with the oriented parallel, oriented diagonal, and polar one-sided trominoes. No tromino should touch another of the same type.

With these symmetry subgroup based polyform variations in mind, any type of polyform on a square grid can be transformed into an entire family of polyforms. In particular, polysticks would reward exploration in this light, which does not seem to have occurred yet. A similar analysis to the one above can be made for symmetry based variations of polyiamonds and polyhexes. Bringing translation symmetry subgroups into the picture leads to things like checkered polyominoes. I may get to these in later posts; this one was getting long enough that I needed to wrap it up.

I should note that Peter Esser’s pages on polyforms cover these variations, and that his polyomino solver program can work with any of the 8 symmetry types (but not with mixed types.) (It is, sadly, a Windows binary, but I’ve been able to make it work under Wine on Linux.)

Polyform Link Roundup

March 25th, 2012

There have been a few recent developments worth noting in the world of polyform puzzles:

Rodolfo Kurchan has posted Puzzle Fun #25. Some good new coloring problems using multiple sets of polyominoes.

David Goodger has been doing some good work on triangular and hexagonal grid polysticks.

George Sicherman is continuing to make advances in the realm of polyform compatibility problems. He also recently posted a catalog of the polypennies up to order 6.

KSO Glorieux Ronse is a school in Belgium that has, over the past decade, conducted a wonderful educational experiment by posting contests based on polyomino problems that could be engaged with by their own students just as much as the world’s puzzle solving elite. (The latter tended to win, of course.) Their 50th contest, which they state was their final one, was held late last year. They solicited the polyform puzzle community for problems to use in the contest and got quite a few, including one from me. No word yet on the results of the contest, (or their previous one for that matter) but the problems there are still pretty interesting.

I’ll be at the 10th Gathering for Gardner (G4G10) this week, and I expect that I’ll come back with quite a lot to think and post about. If you’re going to be there, my talk on Flexible Polyforms has tentatively been scheduled for the Thursday morning session. I hope to see some of you there!

HEY, A BOGUS 9

July 8th, 2011

Dave Harper’s Polyomino Patterns page has some good stuff, looking at patterns of connections between squares in polyominoes, and processes of “integration” and “differentiation” on polyominoes. He enumerates all the possible patterns of connections of the cells in a 2×3 rectangular hexomino that make a connected whole. (There are ten.) These could also be considered as polysticks that touch all six vertices in a 2×3 lattice. The polysticks on a 2×3 lattice are precisely those that can be represented on a 7-segment LED, hence my presentation of them below:

It might be nice to have some puzzle using these. So here is one! Fill in segments on the figure below so that each of the ten patterns above is represented on a 7-segment LED shaped subsection of the figure.

Reflections and rotations of the patterns are considered equivalent. There are 13 7-segment LED shaped subsections of the figure, so three of them either can have other patterns, or can be duplicates.

Are there any other puzzle grids that would make for a puzzle using these patterns that is as good or better than this one?

Hamiltonian and Eulerian Snakes

March 7th, 2011

George Sicherman recently sent in a solution to problem #17, tiling a Hamiltonian circuit of a 6×8 grid of vertices using the linear 3- and 4-sticks. In fact, he found all 51 solutions. Two of them have the property that all of the joints between polysticks occur at 90° angles. Here’s one, in the form of snakes:

(The other is a variation on this one where the order of two of the polysticks in the center of the top of the figure is swapped.)

Later, I saw that the same set of polysticks would fit into a 3×4 array of diamonds. All of the vertices in this figure have even degree, which means that it is possible to make Eulerian circuits on it. Sicherman sent in a solution to this one too:

Sorry, I was too lazy to turn it into snakes. For this problem, solutions like the above with no point where four polysticks meet are preferable, otherwise there would be more than one direction for a path to take. Although it would be nice if it could be done without any points where two polysticks cross, this is impossible. (The pieces contain 14 straight joints; if there are no crossings, each straight joint must also be the locus of two end points. Since each piece has two end points, and there are 13 pieces, there aren’t enough end points to go around.)

Polysticks on a Regular Spanning Subgraph

December 24th, 2010

If any of you haven’t seen them yet, Vi Hart’s “Doodling in Math Class” videos are some of the best expressions I’ve seen of the joy of Recreational Mathematics. The Snakes and Graphs one is especially good, and it contains, despite all of the Internet Meme Years that have passed, a Snakes on a Plane reference.

Ed Pegg wrote a Math Games column in 2006 riffing on the notion of Snakes on a Plane. There’s some great stuff in there, but one could probably fill another column with material that didn’t make the cut. For example, he includes strip polyominoes, which have squares on each end that border only one other square, and are connected by a path of squares that border exactly two others. But linear polysticks, despite being at least as snakey, are absent. What can we do with linear polysticks? To me, they seem to cry out to be tiled onto some closed curve on the square grid. One could imagine some variant of Slitherlink (A Japanese puzzle type described in Ed Pegg’s column) where one would use linear polysticks to form the solution. (For another example of polysticks being used to tile figures on a square grid, see my previous post, Polystick Problems from Polyomino Solutions.)

I was, however, drawn to another source of closed curves. You can move a rook on a rectangular board in a series of single steps that visits every square once and returns to its starting point. Such a sequence is called a closed rook tour, and is the subject of an excellent article by George Jeliss. In graph theory terminology, a closed rook tour is a Hamiltonian of the graph with vertices that correspond to the squares on the board, and edges that connect vertices of neighboring squares. Closed rook tours have been enumerated for small rectangular boards, and it looked like there were enough of them to make it reasonable to hope that one of them could be tiled by a set of polysticks.

The nine linear tetrasticks seemed like a good place to start, and have a convenient total length of 36, which is just right for a 6×6 square. Sadly, the linear tetrasticks have a parity problem that prevents them from forming a closed curve. (A closed curve must have even numbers of both horizontal and vertical segments. Three of the tetrasticks have odd horizontal / vertical parity, and so the full set must have odd numbers of each.) But we can repair this parity problem by adding the 4 linear tristicks to the mix, giving us a total length of 48, which should work on a 6×8 rectangle. Adding the tristicks also improves the flexibility of the set and should make solutions easier to find, which was welcome as I was trying to solve the puzzle manually.

#17: Put these ——ing snakes on a ——ing closed rook tour of a 6×8 rectangular grid.

As you can see, I didn’t quite find a solution myself, but I got close! Perhaps you will be luckier, more persistent, or smarter than I.

Update, 2011-2-4: George Sicherman has found a solution!

Where to go next? Well, a reasonable extension would be to look at grids where every vertex has three edges instead of two. Unfortunately, any finite section of a square grid has to have corners which can only have two edges. We can get around this by looking at infinite repeating tilings instead, or equivalently, tilings of a torus. Here are the 5 tristicks tiling a 2×5 torus:

#18: Excluding (as we must) the “+” tetrastick, the remaining 15 tetrasticks have area 60. Place them on a 5×8 toroidal grid so that every point is connected to three others. (I don’t think the parity issue should be a problem in this context, but I could be wrong. See comments).)

Going back to graph theory terms, what we want is a 3-regular (each vertex has degree 3, that is, it has three edges connecting it to other vertices) spanning subgraph (a graph containing all of the vertices of the original, but not necessarily all of the edges.) A Hamiltonian could be called a 2-regular spanning subgraph, with the added provision that it must have a single connected component. I’m not worried about our solutions breaking into disconnected components in our 3-regular problems here. 3-regular graphs are also called “cubic”, but that term seems confusing in the context of polyforms, so I’ll avoid it.

Another way to make 3-regular spanning subgraphs of a grid is to use a triangular grid. Because corners can connect to three other points, we can use finite sections of the grid this time.

There are 12 tristicks on the triangular grid. The section of the triangular grid in the shape of the hexagon shown below has spanning 3-regular subgraphs with 36 edges.

#19: Find a tiling of the 12 triangular tristicks on a 3-regular subgraph of a section of the triangular grid bounded by a convex hexagon with side lengths 2,3,2,2,3,2.

Again, I got pretty close before I gave up; maybe you’ll have better luck. I’m pleased to have a problem that showcases the triangular tristicks. If the square polysticks don’t get the respect they deserve, this is doubly true for the triangular polysticks. Livio Zucca has a page with some triangular polystick solutions, (scroll most of the way to the bottom) but I can’t say that I’ve seen them elsewhere.

Got any other ideas for figures of segments in a grid that could profitably be tiled with polysticks? Any ideas for interesting triangular polystick problems? If you do, please share them in the comments.

Polystick Problems from Polyomino Solutions

September 7th, 2010

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.