Tag: hamiltonian circuits

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.

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.

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.)