Posts Tagged ‘Polyforms’

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!

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.

Holy Hyperbolic Heptagons!

February 19th, 2010

Recently, MathPuzzle highlighted a program called MagicTile for playing with Rubik’s Cube variants on various tessellations in spherical, Euclidean, and hyperbolic geometries. One interesting hyperbolic tessellation is the {7, 3} tessellation, composed of heptagons, with three meeting at every corner. Twenty-four of these heptagons can be wrapped up into a genus-3 (that is, topologically like a torus but with three loops instead of one) “Platonic solid” called Klein’s Quartic, which John Baez has a fascinating page about.

Polyforms based on hyperbolic tessellations appear to be a relatively unexplored area. I’ve come across a couple of references on counting the n-cell polyforms for a given tessellation, but I haven’t found evidence that anyone has actually used them for puzzles. So I set myself this one. There are ten tetrahepts on the {7, 3} tessellation. Could they tile two copies of the same shape?

An implicit constraint in my solution of this problem was that the shapes could extend no farther than the second ring around a central heptagon. I searched for a solution using plastic game counters that would not have fit on any heptagons farther out on the diagrams I used as solving boards. I also knew that I was going to make images to show on my blog, and they would be clearer if there were no relatively tiny heptagons in the solution. In fact, the decision to find a puzzle in two pieces was affected by the observation that using an extra Poincaré disk would remove the need to use the tiny outer heptagons.

This was a pretty difficult puzzle to solve by hand, so I feel like I’m being a little mean using an even harder, (and perhaps impossible) variant as the numbered puzzle for this post:

#8: Find a symmetrical shape for which two copies can be tiled by the ten {7, 3}-tetrahepts. In addition to mirror symmetry, 180° rotational symmetry around the midpoint of an edge could work. (The other modes of rotational symmetry of the tessellation won’t work for a 20 cell shape.)

I would also love to see what other puzzles people can come up with on this or any other hyperbolic tessellation.

Hexiamonds on an Octahedron

January 26th, 2010

Here’s an interesting problem that seems not to have gotten as much attention as I think it deserves. The twelve hexiamonds contain a total of 72 triangular units. A regular octahedron with edges 3 units long can fit 9 triangles on each of its 8 faces, exactly enough to tile with the hexiamonds. Some individual solutions to this problem have been found. A solution at Livio Zucca’s site bears the label “Adrian Struyk 1963?” so we may assume the problem has been around at least since then. Another solution by Michael Dowle is here.

Notice that you can unfold an octahedron to produce a net in the form of an octiamond. This provides another source for solutions. The octahedron has 11 different octiamond nets. Pieter Torbijn found that 24 enlarged octiamonds could be tiled with the hexiamonds; of these, 5 are nets of an octahedron.

As far as I know, nobody has made an exhaustive computerized search for solutions to this problem. You can be the first!

#4: How many distinct ways can the hexiamonds tile an octahedron?

The octahedron has a large amount of symmetry compared to any planar figure that these pieces can tile. It has 48 automorphisms, or ways to map the solid onto itself. This would indicate a relatively small number of different solutions, since many solutions will be mappings of each other over the various ways of rotating and reflecting the octahedron. On the other hand, the shape lacks external borders, which ought to greatly increase the number of possibilities.

Some solutions have a piece that wraps around and caps a vertex. This could be considered an aesthetic flaw, because it would be impossible to tell which hexiamond the capping piece is just from knowing what triangles it occupies; you must also know its edges.

There are 7 different pieces that can cap a vertex, one of which, the pistol, can cap it in two distinct ways. Notice that due to the symmetry of the shape it makes when it caps a vertex, only the orientation of the sphinx is a riddle; its identity is never in question.

#5: How many solutions have a capped vertex?

#6: What is the largest number of vertices that can be capped in a solution? The ideal would be for all six vertices to be capped with all of the above hexiamonds except the sphinx.

The octahedron has twelve edges, the same as the number of hexiamonds. This suggests another problem:

#7: Is it possible to tile the octahedron so that each of the twelve hexiamonds is folded across exactly one of the edges of the octahedron?