Tag: polysticks

Touring Tilings

~ munizao ~ Leave a comment

A few months ago, I noticed that a king can tour a pentomino tiling so that every cell in each pentomino is visited exactly once in an uninterrupted sequence, and the tour forms a closed loop.

Not every pentomino tiling admits such a tour, but it’s not hard to find one that does. A more restricted form of loop could be made using a wazir (an archaic chess piece that moves one cell orthogonally, W for short) instead of a king. Such loops would be more challenging to find. They also restrict the polyominoes that can occur, for example, only 8 of the pentominoes are available.

There are 18 hexominoes that can be traversed by a wazir without visiting the same cell twice. They can make a W-tourable tiling of a 9×12 rectangle:

When I posted this to the Puzzle Fun Facebook group, Rodolfo Kurchan referred me to a previous exploration of similar pieces in the Journal of Recreational Mathematics. It covered the W-traversable 2- through 5-ominoes, (called “rookominoes” in that source) which have an area of 64, and can tile an 8×8 square. But the passage that Kurchan shared only mentioned tiling the pieces, and didn’t consider tours at all! Could they really have been that close to discovering tours on tilings, and just missed them? I adapted my PolySolver model that I used for the above hexomino tiling to find tilings of these pieces instead. Polysolver could find solutions for this set about 10,000 times faster than for the hexominoes. That made me feel that these toured tilings ought to be well within range of manual solving. Surely the JRM contributors could have found them.

I was intrigued, and wanted to find out if there was more about these rookominoes in the JRM than just that brief passage. I looked up the JRM on WorldCat, and found that there was a copy at Reed College, only about 10 miles away from me.

So I drove over, and found where the JRM bound volumes were kept in the basement of the Reed College library. The material I wanted wasn’t in an article per se, but in a section titled “Solutions to Problems and Conjectures”. I found the piece that Kurchan shared from 1990, but also several more from later issues over the next several years. It turned out that the JRM contributors did indeed consider W-tours on these pieces, and Brian Barwell found the first solution. Another variation considered was maximizing the number of loops. Barwell and Michael Reid found a seven loop solution:

They note that the I pentomino cannot be part of a loop of fewer than three pieces. All of the 12 remaining polyominoes, excepting the square tetromino, cannot make a loop alone. So for all of the pieces to be used, there must be at most six more loops, so seven is the maximum.

These problems are related to the snake polystick Hamiltonian circuit problem I posted some time ago. The paths that the tours take within polyominoes are in fact snake polysticks. One difference is that there are extra monosticks connecting these snakes where the path crosses from one polyomino to the next. Another is that we are taking a complete set of polyominoes rather than a complete set of polysticks. For example, we only use one of the two tetrasticks that can traverse a P pentomino. We could instead use an extra P pentomino, and require that both snake tetrasticks occur.

I’ve left this exercise in library spelunking excited about the possibilities for tours on polyform tilings, but a little saddened about the state of polyform knowledge in the world generally. When I did a web search on “rookominoes”, the only results were indices to Stanford’s archive of Martin Gardner’s papers. (There’s something in Box 54, folder 18. It is highly unlikely that I will ever see the contents of that box.) The Journal of Recreational Mathematics wasn’t too hard to track down, given Kurchan’s tip, but who would even know where to look? With the original publisher defunct, I couldn’t find even an index of article titles not behind a paywall, not that that would help me find material strewn between different “Solutions to Problems and Conjectures” columns over several years. Cubism For Fun has an online index, and back issues are purportedly available, but ordering very many of them would be prohibitive. As for the Polyforms Yahoo group, there I’m up on the rest of the world; I have everything since I joined on my hard drive. Good luck to the next poor soul looking for anything to be found there though. The Puzzle Fun Facebook group should stay around for as long as it takes for Meta to go the way of Yahoo. And everything here? Once I’m no longer around to pay for hosting, it goes into the limbo of stuff you can only find via the Wayback Machine, and only if you already know where to look.

Polysticks and Polyominoes, Together at Last

~ munizao ~ Leave a comment

Back in my 11th post on this blog, I posed a problem involving tiling a figure with tetrominoes, and then tiling the edges of the tetrominoes with tetrasticks. Now I’m on my — well, look at that. This is my 100th post here! Anyway, recently I was playing around with Jaap Scherphuis’ PolySolver program, looking to see if there were any of my old problems that it could solve, and that one looked like a good fit. It turned out to have a unique solution, according to the solver.

As it happened, this problem was already at the front of my mind, after meeting William Waite of puzzlemist.com at Gathering 4 Gardner 15 this February. He gave me a copy of a combined polyomino/polystick puzzle he designed after a previous conversation at a G4G where I mentioned the problem above.

I think it’s worth examining how this puzzle differs from my take on the type, and why. I used a complete set of tetrasticks, and the closest thing I could get to a complete set of polyominoes, doubling up on tetrominoes and throwing in a monomino hole only because one of the tetrasticks required it. It’s just my aesthetic as a polyomino problemist to want to use complete sets when I can. Waite has a different objective; this was a puzzle produced for sale, with the object of the customer feeling that they got good value for the purchase price. Thus, where I didn’t care if the puzzle required computer assistance to solve, Waite wants a human puzzler to have a good chance of getting there on their own.

Because of this, both the polyomino set and the polystick set consist of easier pieces to tile. The polyominoes are the full set of 2–4-ominoes, which is at least as nice of a set as what I chose. The polysticks, however, are a mix of 3-sticks and 4-sticks, and neither set is complete. The polystick pieces seem to have been chosen for ease of tiling. The qualities that would make a more tilable piece are having little symmetry, having a smaller bounding box, and having a shape that fits nicely on the edges of the board. These pieces all have at least one of these features. The puzzle claims to have 4326 solutions, so finding one of them should be tractable.

Having a single unique solution doesn’t make a problem better than any other, but it does seem like a remarkable occurrence. Doubly so when lightning strikes again near another instance. Here I adjusted the shape from the first problem to one that had biaxial symmetry rather than quarter-turn rotation symmetry. This too has a unique solution!

Polykingsticks

~ munizao ~ Leave a comment

I noted a while back that triangular polysticks hadn’t received the study they deserved. Perhaps we can say more generally that a fruitful way to find understudied polyforms is to take the polysticks that correspond to connections between cells in some other polyform set. Since I was recently looking at polykings, it makes sense to ask what nice sets we can make out of polykingsticks, and what we can do with them. There are only six dikingsticks. Here are the 41 trikingsticks: [Edit: numbers fixed per communication from GS]

That’s a lot! We can distinguish some categories. First, “proper” polykingsticks (in red) exclude those that have only one type of connection. “Snakes” (bolder lines) are polysticks for which there is a single path that visits each vertex once. Most of the non-snake trikingsticks are branched. There are a couple of oddballs, a right triangle and one self crossing snake, which you might need to omit if you have a problem where you want to avoid crossings.

What kinds of problems can we explore with these? They’re a bit awkward for tiling. Compatibility problems should work, as long as the pieces have the same balance between diagonal and orthogonal segments. Common superform problems should also be doable.

We can also try Hamiltonian circuit problems like the one that I looked at with regular polystick snakes. There is a parity issue here. If we checker the vertices of the grid, we require an even number of snakes where the two ends are opposite colors in order to make a circuit. This means we can’t use the set of proper trikingstick snakes with the self-crossing snake omitted. Perhaps with it included, we could do a Hamiltonian circuit of a 6×11 grid. If we just make a path, rather than a circuit, and exclude the self-crossing snake, visiting all of the points on an 8×8 grid might be possible.

With so many trikingsticks, tetrakingsticks might seem too large of a set to contemplate, but I have a couple of ideas for interesting reasonably sized subsets. These will have to wait for another post, however.

A Polyformist’s Toolkit: Symmetry Variations

~ munizao ~ 3 Comments

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

~ munizao ~ Leave a comment

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

~ munizao ~ 4 Comments

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

~ munizao ~ Leave a comment

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

~ munizao ~ 3 Comments

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

~ munizao ~ 5 Comments

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.