Tag: polyominoes

Four Square Sequels

~ munizao ~ Leave a comment

In planning out blog posts, I typically use the rule of thumb that a post should contain between two and four images. If I have five or more images, I try to break the material up into multiple posts, and if I have only one I will usually wait until I have more material. A single image is a still life; when there are more, I can tell a small story. Unfortunately, this means that over time I build up a number of “orphans”, perfectly good results left to gather dust because I have nothing else that is closely related. I recently noticed that several of my orphans were square shaped. Perhaps I could use this to tie some disparate results that normally wouldn’t belong together into the same post.

1) I noticed last year that the tetrakis grid 4- and 5-tans had a combined area that could make a square. This seemed like a pretty basic result that had to have been known years before. I asked (and looked) around, but I couldn’t find any instances of it being found previously. Then in preparing this post, I discovered that I was almost right. It had, in fact, been found months before, by Thimo Rosenkranz. (That page isn’t visibly dated, but a timestamp in the html code indicates it was published in July of 2023.) For all I know, these pieces may have been studied many times previously, but having done the important step of preventing myself from falsely claiming primacy, I am content to leave off further historical research.

2) I claimed that I couldn’t do anything elegant with just the set of single-striped tetrominoes, but shortly after I posted that, I found the figure below. Here, I relaxed the rule that the stripes must form an unbroken line from one edge of a figure to another. Instead the stripes may have a singe-cell gap in order to allow a perpendicular stripe to pass through. A woven pattern, where each stripe crosses one other and allows another to cross it, seemed like the nicest possibility. (The faded dashed lines are artistic license on my part, not actual markings on the pieces.)

3) The pieces here are based on those in my L-Topia puzzle. That puzzle contained every way to mark two cells of an L tetromino with a circular and a square hole. When I had access to a laser cutter in 2009, I made a variation where, instead, the holes were double headed arrows that could point horizontally or vertically. I was recently reconsidering “pilings”, (tilings with overlap) and wondered what could be done with pieces with marking sites where the markings have two possible orientations by symmetry, and the overlaps must match one orientation with the other. My L-Topia variation came to mind, but I had better results with a similar variation, where the arrows would be diagonal instead. Here, instead of cutting out arrow-shaped holes, I cut out triangles on opposite corners, leaving a bar to overlap. There is a unique piling where the overlaps form a single loop joining all of the pieces.

4) At G4G15, I gave a talk on polykings and other polyomino variations where cells are connected in different ways from standard polyominoes. I based the talk on a couple of earlier blog posts, but I did throw in one additional result. One of my usual creative tricks is “mix ideas, even if they aren’t meant to be mixed.” In the context of tiling problems, that can work out to “tile with sets of pieces that aren’t meant to be mixed.” If we build the five tetrominoes with each of the five shortest cell connection types, we get 100 total cells. Why not throw them together into a 10×10 square? In the diagram below, each tetromino form is represented by a different color, while the crosses indicate the directions and magnitudes of the connection vectors.

Problem #64: Well, everything is always nicer if you can make things of the same kind not touch. Here that means both tetrominoes of the same form, and tetrominoes with the same connection type. But asking for both may be too much, so we may have to accept just one or the other. But wait! What exactly do we mean by not touching here? Simply using Wazirwise adjacency seems contrary to the spirit of the thing. Let us say that two pieces touch if the connection type of one of the pieces can reach, from one of its cells, a cell in the other piece.

We might like there to be some theme that we can tease out from these unrelated square tilings that can retroactively justify shoveling them into the same post. If there is, it might be parity of elegance. A square has high elegance, having maximal symmetry in a smooth, convex shell. But as a consequence of this elegance, we don’t have many sizes of squares available, just one for each integer, so we have to contrive somewhat inelegant sets of pieces to tile them. In the case of the striped tetrominoes, the fixed dimensions of the square forced me to fudge the stripe placement rules to get the stripes to fit.

Of course, there is no such thing as parity of elegance in the universe of possible tilings; many very inelegant tilings may be found. What we see is the effect of me selecting the most elegant tilings that I can find to share on my blog. In these cases, the elegance of the square justified less elegance in other aspects of the tilings.

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.

Stripe Club

~ munizao ~ Leave a comment

I posted last year about a path puzzle using polyiamond tiles. Those tiles were marked with a complete set of paths between cell edges on the perimeters of diamonds and triamonds. Recently I’ve been exploring a variation on tiles with marked paths. In these tile sets, the paths are constrained to straight lines aligned with the grid and connecting the midpoints of opposite cell edges. By this scheme, there are 16 ways to stripe the tetrominoes. I wasn’t able to come up with any elegant tiling using just these pieces, but with a set of unstriped trominoes, they can make a rectangle with four stripes. We follow the typical rule of path puzzles: the stripes must connect between pieces.

There are nine distinct ways to stripe the three trihexes. There is an arrangement of parallel stripes on the figure below that looks like it could have a solution, but it proved to have none when I checked it with a solver. Luckily, non-parallel stripe lines are perfectly acceptable — as long as their intersections occur outside the tiling!

Striping polyiamonds brings a new complication: the line connecting cell edge midpoints is not perpendicular to the cell edge. That means we can change the direction of paths at piece boundaries. The solution below takes advantage of this feature:

Fortuitously, the striped 2-, 3-, and 4-iamonds together contain 49 triangular cells, allowing us to tile a triangle of side length 7. The striped 4-iamonds alone contain 36 cells, but they are not able to tile the triangle of side length 6.

Where else can we go with stripe problems? Todor Tchervenkov, Roel Huisman, and Edo Timmermans looked at tetrominoes with diagonal stripes on the Puzzle Fun Facebook group. (There are 17, which makes them awkward for tiling with the full set, but there are workarounds.) We could try other stripe orientations on polyiamonds and polyhexes as well. Polytans (or polyominoes with tans added or subtracted) could have line bends at diagonal boundaries similar to what happened with the polyiamonds. Another variation I’m looking at is what can be done with multiple stripes per piece. Stay tuned for more stripe content! (Does that count as a stripe tease?)

Notation Notions: Operations on Ominoes

~ munizao ~ Leave a comment

Here’s a tiling of the 3+2-ominoes:

This use of a plus sign seems natural enough, but we might want to think a bit more about what it implies. We have established an operation on polyform sets, and a notation for that operation. This raises some questions: what other operations might we want to use? How should we notate them? And finally, can we design a notation system that readably describes a wide variety of polyform sets? (And should we?)

After addition, a notation for multiplication would be handy. We’ve recently looked at di-triamonds and tri-diamonds. We can call these 2·3-iamonds and 3·2-iamonds respectively. Notice that this multiplication, unlike the addition, doesn’t commute. But it does decompose into addition in the natural way; the 3·2-iamonds are the same as the 2+2+2-iamonds.

In a way, we were already using polyform multiplication to define n-forms in the first place. The pentominoes are essentially the 5·monominoes. In the interest of brevity, we can use symbols for common base monoforms:▲, ■, ⬣, and ◣ for the moniamond, monomino, monohex and monotan respectively. If we are consistent with the above examples, a n■ has subdivisions for the individual cells. That may seem a little weird, but it can be useful; a 2×1 rectangle could be either a domino or a tetratan, and we’d like to be able to know which. I won’t show these subdivisions in my graphics unless it aids with clarity.

We would also like to combine sets together into a larger one. This is multiset addition rather than set union, because we could want to work with multiple copies of the same polyform. I’ll use circled operator symbols for multiset operations, even though that’s a little nonstandard. They’re nicely readable, and the circle will be our mnemonic that we’re doing multiset things. The tetrominoes and pentominoes together would be 4⊕5■. We can read the ‘⊕’ as “and”, so 4⊕5■ is read as “the four and five -ominoes”. Making a set from multiple copies of the same set is the same as scalar multiset multiplication. So five copies of the tetrominoes is 5⊙4■. As before, this is non-commutative left multiplication; the dot is our mnemonic for that. And it decomposes as expected into multiset addition: 5⊙4■ = 4⊕4⊕4⊕4⊕4■. I can’t think of any reason I would ever want to do element-wise multiset multiplication with polyforms, but ⊗ is there if I ever need it.

Now that we have multiset operations and polyform connection operations, we can start to combine them. There are 22 4+1■. I hope to share more problems involving them soon, but one thing I noticed was that with some smaller pieces included I could get an area of 144, and make a square. With my notation system, I can call these 2+1⊕3+1⊕4+1■. Or I could write that as (2⊕3⊕4)+1■. Polyform addition distributes over multiset operations!

(Well, I could have made a square. I’m showing this shape instead because PolySolver wasn’t finding solutions for the square with separated monominoes. Thanks to Bryce Herdt for showing me a technique for getting PolySolver to find solutions with this property.)

Finally, I must address the final question from the start of this post. Is a notation system for polyform sets actually a reasonable thing to develop, given that I am a lone crank and nobody else is likely to use this stuff? And I think that I am finding, for my own explorations with polyforms, that the answer is yes. With algebraic notation, the concepts behind the notation can be expressed with words, and were for a long time. But symbols are easier to mentally manipulate, and formulas that could not fit into working memory as a paragraph can do so as a modest number of symbols. I am already finding it easier to think about polyform sets because I have symbolic notation for them. As I hinted in my fuzzy polyominoes post, I’m working on notation for related concepts, so more posts on polyform notation are sure to follow.

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!

Border Marking

~ munizao ~ Leave a comment

This might, at first glance, appear to just be a random tiling of a bunch of dominoes and trominoes.

But what would be the point of such a thing? In fact, it’s a complete* set of dominoes and trominoes where edges may be marked, and the marked edges are exactly the ones that can occur on the border of this tiling. That thick rectangle around the tiling is part of the pieces!

*There is, in fact, one more tromino with markings that could fit in that rectangle. But if we included it, there would be a single cell in a corner that would be unfillable, since we’ve specified that the tiling has only dominoes and trominoes. Therefore, by the rule of exclusion of things that would be awkward to keep around, it has to go.

That this works at all, even with this minor fudge, feels like a pretty bit of luck. Not only do we have a perimeter and area that are compatible, we have exactly the usual number of corners for a rectangle.

With polyiamonds, I thought my luck ran out. No combination of sizes gave me compatible perimeter, area, and corners. But when I abandoned corners entirely, and focused on pieces with only one marked side, I found that a parallelogram with opposite sides marked could be made using the 2-, 3-, and 4-iamonds. Since it wouldn’t do to have any unmarked edges lying bare to the outside world, I wrapped that parallelogram into a cylinder:

And here are the pieces individually:

Sometimes when I have a novel polyform puzzle idea, I feel like I’m tapping into a rich vein of possibilities. Here, I’m not so sure. The problem is that when you move up to sets with larger sizes of polyforms, the area and border segment length are unlikely to scale in a way that gives you tilings with completely marked borders. But I would love to be surprised!

Extremal Structure-Excluding Polyforms

~ munizao ~ 1 Comment

Here’s a problem that Ed Pegg posted on the Puzzle Fun Facebook group recently: how large can a polyomino be where no line connects four cells? (Diagonal lines in any direction count, and we require the lines to pass though the centers of cells, for this problem and all that follow.)

This turns out to have been an old problem, which was included in Rodolfo Kurchan’s book, Mesmerizing Math Puzzles. The maximum size is 15 cells, as shown.

It reminded me that I had seen a couple of similar problems. Jan Kristian Haugland found the largest polyominoes with no four equally spaced cells on any line, and detailed his discovery and proof of maximality in a paper. Here’s one; the others are minor variants on this one:

I’d also seen a no three equally spaced cells on a line problem for polykings. I had in my notes that it was studied on a bulletin board called Zompist and the maximum size was conjectured to be 48, but the post is gone and was not archived by the Wayback Machine. So I set myself the puzzle of reconstructing a 48-king with the desired property.

The gray squares here are not just an aesthetic flourish. I used them as a tool to keep track of cells adjacent to the figure that were excluded from being added. That way, when all squares adjacent to the figure were gray, I’d know that I’d found a local maximum. I could have taken them out afterward, but I think it’s fun to share and learn about how we work on problems. Or I’m just lazy, your pick.

With the no four equally spaced in a line problem leading to such a visually distinctive maximal polyomino, you might think (I did) that no n equally spaced in a line problems would give ever more intricate ones for higher n, if we could manage to find them. When I posted about the above problems on Ma(th)stodon, Dömötör Pálvölgyi (name order westernized) asked if there is always a maximum size of poloyomino for any n. I didn’t know, so Pálvölgyi took the next reasonable step, and asked on MathOverflow. Renan Gross answered in the negative; in fact, the maximum n which gives a maximal polyomino is 4, as in Haugland’s solution!

To show this, Gross first restricts his scope to Monotone Path Polyominoes: ones that can be formed by always taking steps up or to the right after placing the first cell. Every MPP can then be represented by a sequence of two symbols, one that means “go right” and one that means, “go up”. (We could use → and ↑. Then, for example, the W pentomino could be represented as →↑→↑.) Gross’s key realization was that any segment of an MPP starting with the first and ending with the nth equally spaced point in a line would have n – 1 consecutive blocks where each has the same number of →’s and ↑’s as the others.

At this point, Gross consulted the literature to find out whether someone had found a construction for a binary sequence where, for some number of consecutive blocks, this never happens, and a paper by F. M. Dekking from 1978 had just such a construction. Gross has written a blog post where he discusses his process in finding this result, which I highly recommend reading.

Where does this leave a recreational mathematician such as myself, whose major motivation is seeing results that make pretty pictures? Well, one direction we can go is to try this problem with other polyforms. With polyhexes, it looks like we can get 9 cells for n = 3. Because there is an affine transformation between the centers of the squares in a regular square tessellation and the centers of hexagons in a regular hexagon tessellation, we know that there is no maximal polyhex for n = 5, but n = 4 is open. One point to be careful about is the definition of the center of the cell that we’re using. For polyplets, (polyforms based on unit right triangles) we could get different results depending on what triangle center we use.

Another option would be to change the set of structures that must be excluded. If we think of 5 equally spaced points in a line as an exploded I pentomino, can we add other exploded pentominoes to our exclusion list to get interesting finite maximal examples? (I plan a post in the near future about exploded polyominoes, so I won’t define them formally for now, but you catch my drift. We may consider an unexploded polyomino to be a trivially exploded polyomino.)

A third direction would be to add cell coloring. If we have two colors, we can consider only lines containing the same color of cell. I’m a little pessimistic about there being maximal polyforms to be had here. Even n = 3 may generally be enough to escape confinement. But I’m optimistic in general about there being much more to be discovered in this area!

Tilings and Reconstructions

~ munizao ~ Leave a comment

There are nine proper 4-WFD-ominoes:

Recall that a proper WFD-omino is one where every spanning tree of W, F or D connections between the cells includes at least one of each. Recall that W, F, and D connections correspond to the moves of the Wazir, Ferz, and Dabbaba in historical chess variants. And recall that these moves are, respectively, a one space orthogonal move, a one space diagonal move, and a two space orthogonal jump respectively. (It’s fine if you don’t recall these things. I’ll recall them for you. Or you can read this post, and then recall them.) The full set is the right size to tile a 6×6 square. And indeed, it can!

And yet, you might find that graphic just a little unsatisfying. The solver that I use for polyomino tilings displays results with all of the pieces in the same color. This is fine for standard polyominoes, but for disconnected (or differently connected) polyominoes, it’s hard to see where all of the loose monominoes fit. But that just turns reconstructing the tiling into a logic puzzle. Indeed, there are entry points where a domino is constrained to be in a particular proper 4-WFD-omino, which removes certain monominoes from consideration and forces other dominoes to belong with their monominoes, and like a sudoku, the chain of logic eventually forces a complete solution. Try it!

But a 6×6 puzzle may feel a little small if you’re used to Sudoku or other puzzles in the Nikoli mold. So let’s try out the proper 4-WFA-ominoes. (Recall that the A (Alfil) is a two space diagonal jump.) There are 15 of these:

They have area 60, so they can tile a 8×8 square with corners removed, just like the 12 pentominoes.

Reconstructing the tiling here is a substantially harder puzzle than the previous one. The monominoes belonging with particular dominoes can be farther flung, which makes it harder to constrain which bits must be connected. I had to try out a large number of tilings before I found one where I could make some headway in the reconstruction puzzle. But rest assured that I did indeed solve this one.

Where to go from here? There are 21 proper 4-WFN-ominoes, (recall that N is for knight) but they have odd checkerboard parity, which interferes with trying to find a nice thing for them to tile. Another possibility would be to combine the proper 4-WFDs and 4-WFAs in a single puzzle. Either way would make it even more difficult to constrain which monominoes go with the dominoes. There may be solvable reconstruction puzzles in the space of tilings, but the strategy of picking tilings at random to find solvable ones will probably break down. I suspect that there are more good puzzles in this vein waiting to be discovered, but they may require more creativity in coming up with new piece sets that will work, or in puzzle design or discovery techniques.

A Polyformist’s Toolkit: Connections

~ munizao ~ Leave a comment

We may say that a polyomino is a connected set of squares in a grid; now I want to examine what we mean by “connected,” and what we can mean.

The usual definition requires cells to be connected along their edges. A common variation allows cells to connect either with neighbors either by edges or by corners. These have been variously called polykings, polyplets, and pseudo-polyominoes. My personal preference is polykings: I know what a chess king does, and it immediately suggests how a polyomino variation based on the concept would work. I don’t know what a plet is, and pseudo is both wrong, (there’s nothing fake or false about them) and unspecific, (if we are going to go around calling things false polyominoes, we have plenty of options.)

The 22 tetrakings.

Wikipedia titles its page on them Pseudo-polyominoes, because Golomb called them that in his book, and printed books override all other forms of knowledge. Except, at the time I am writing this, everywhere on that page except for the title, where Wikipedia continues to calls them polykings.

Unfortunately, rather than leave well enough alone and stick with just “polykings”, I’m going to introduce my own confusing and awkward terminology. Because there are actually many more choices for ways to associate pairs of connected cells on a square grid, and we’re going to need a systematic method to keep track of them. As with “polykings”, chess piece moves more generally can correspond to allowed connections between cells in a type of polyomino. And we may turn to a standard notation for chess piece moves, which was developed by Ralph Betza and adopted more widely by chess variant designers.

The initials used to designate short piece moves mainly come from pieces in historical versions of chess. W, for Wazir, (Persian, minister or vizier) is the one orthogonal space move,. F, for Ferz, (Persian, counselor) is the one diagonal space move. D and A are for Dabbaba (Arabic, siege engine) and Alfil (Arabic, elephant) respectively. N is the standard initial for a chess knight, since the king takes the K. Instead of polykings, now we may speak of poly-WF-ominoes. Likewise, we can construct poly-WD-ominoes, and poly-WFD-ominoes, etc. Peter Esser has looked at the poly-WFD-ominoes, which he calls “Far-Bridged Polyominoes”, and also some symmetry variants based on them.

Not every possibility is equally interesting. For example, the poly-F-ominoes are equivalent in a way to the poly-W-ominoes: by rotating and dilating the positions of the cells, you can uniquely transform any of the former to one of the latter.

There is a practical problem with the poly-WF-ominoes and some of the other connection based variants we can come up with. The sets generally grow so fast with the size of polyomino that they skip right past the domain of practical manual solvability. Twenty-two 4-WF-ominoes is just too many, but five 3-WF-ominoes is trivial. But if we observe that just 12 of the 4-WF-ominoes aren’t W-ominoes or F-ominoes, we get a set that is manageable. We can call these the proper 4-WF-ominoes, and define them more formally as all of the 4-WF-ominoes for which every spanning tree of connections contains at least one W-connection and one one F-connection.

Unfortunately, the proper 4-WF-ominoes have odd checkerboard parity, so we can’t use them to tile a rectangle. I did however manually find a tiling of a 7×7 square torus with the proper 4-WF-ominoes plus a monomino.

Problem #51: There are some improvements upon that solution I’d like to see. How many of the following can be achieved, either individually or together?

  1. Avoid any “Fault lines”, or runs of border segments that pass all the way through a tiling. With standard polyominoes, this is rarely difficult. These pieces have fewer orthogonal connections that can block a fault line. There are 14 rows and columns, and only 18 orthogonal connections, so they must be spent somewhat carefully.
  2. “Crossroads”, or vertices that join four border segments are unavoidable due to the diagonal connections. A constraint that would be equivalent to “No crossroads” for standard polyominoes is “No four-piece corners”. Here, this constraint is weaker than the original, and should be achievable.
  3. No crossed bridges. Physical sets of polykings require “bridges” joining cells across diagonal connections, and rounded corners that allow bridges to pass. Tilings where two bridges cross could not be made from such pieces. Bernd Karl Rennhak has explored bridged polyforms in depth. Kadon’s Roundominoes are another variation on the theme, where some “bridges” aren’t connected to cells on both sides.
  4. Reduce the number of required colors. Since there are diagonal connections, same color pieces should also not meet at diagonals. (What I had previously called “strict” colorings.) But with rounded bridged pieces, that would not necessarily be visually confusing. Balanced colorings are nice.

Another way around the checkerboard parity issue is to use flexible rhombus based proper polykings. These can tile the following figure:

Problem #52: The same features that were desired in Problem #51 are also missing here. Can you improve it?

It seems that having spent so much time introducing Betza notation, I’m past my ideal post length, so I’ll have to close without using it enough to justify it for now. I hope to rectify this not too far in the future, when I intend to post about the proper poly-WFD-ominoes and other connection-based polyform variations.

Sparse and Magic Squares

~ munizao ~ Leave a comment

A while back, I had the insight that the 3×3 magic square could be transformed into a sparse square, or a set of cells within a square in a grid where every row and column contains the same number of cells. The converse transformation of turning a sparse square into a magic figure is not original to me, but applying it to the sparse square from the first transformation gave a pleasing result. And then I stopped there.

Or I almost did:

Right, so if I had set the 1 where the 34 is, and the 6 where the 26 is before running the solver, (and likewise the 4 and 9) that would have been more elegant.

This is a figure I came up with before my blogging hiatus that never made it into a post. The rows, columns, main diagonals, and 3×3 blocks all sum to 115. This could be seen as a version of my doubly transformed magic square on a slightly degenerate 3×3 magic square whose entries are all 5’s.

But it was hard to see where to go from there. The next size up, the 4×4 square, was unsuitable. Its magic sum is 34, and since we’d be using a 4×4 block, we wouldn’t be able to evenly split the squares from each row and column into four lines. And 5×5 seemed big enough to be a mess to work with. So I was done.

But it turns out we can do something nice with the 4×4 after all. Suppose we number the squares starting with 0 instead of 1. We still can’t use 4×4 blocks, but since the highest value is now 15, 3×5 blocks look like a possibility. And indeed, our magic sum is now 30, of which 3 and 5 are both factors, so it works:

There was an interesting bug in the code I used to produce this. I was looking for figures that are single, hole free polyrects. One way to help filter these out from other solutions is to check for 2×2 blocks with checkered corners. If one is present, you must have either a hole or more than one polyrect. But by accident the constraint I added was more broad; it applied to any 2×2 block with two dark and two light rects. I was not able to get a single polyrect solution with this constraint, but I did find something at least as interesting. Notice that every 3×5 block is the same, after swapping dark and light, as the complimentary block with the number that you get by subtracting from 15. This was not an explicit constraint in my code, so it’s interesting that this property managed to emerge. I still haven’t found a single hole-free polyrect solution without the buggy constraint, but I’m confident they are out there. My solver code is just too inefficient to find them in a reasonable amount of time.

Once I was back on the trail of magic sparse squares, I came back to the magic partition square I discussed in a previous post. (There are four ways to partition the numbers from 1 to 8 into two subsets of four numbers that sum to 18. Each of the 8 subsets is present as a row or column in the square.) Since this figure uses smaller blocks, my solver had no trouble with it.

My work on magic sparse squares is ongoing, and I hope to have more to share with you soon. I’ve put my solver code up on GitHub. I know I’ve had a long hiatus without coming up with new material, but I expect to have a few more blog posts in the coming months, and I hope you’ll enjoy the shiny objects that I find and share.

More pentomino coloring problems on torus tilings

~ munizao ~ Leave a comment

Recently I revisited one of my old pentomino coloring problems, modified to apply to a tiling of a torus rather than a rectangle. That worked out well, so I might as well shamelessly continue to mine this vein.

There are 18 one-sided pentominoes. Six of them have reflection symmetry, and the other 12 are 6 sets of mirror pairs. A while back, I asked if there was a tiling with a three-coloring where the 6 with reflection symmetry share a color, and each mirror pair has one pentomino of each of the remaining two colors. Patrick Hamlyn found that there was no rectangle tiling that could be colored in this way, but there was such a tiling of the shape below:

The one-sided pentominoes have area 90, which is the area of a tilted square on a grid:

Problem #47: Find a tiling of a torus with this tilted square as its fundamental domain by the one-sided pentominoes with a three-coloring as described above. If possible, find a tiling with no crossroads.

Another older problem that could be adapted to a torus is the minimal 2-colored packing problem. Here’s my conjectured minimal 2-colored pentomino packing of a rectangle:

(I had forgotten that this was problem #1 on this very blog!)

Problem #48: Find a two-colored packing by the pentominoes of a torus with minimal area.

Obviously, you could just take the rectangular packing above and add a one unit “moat” around it to get a torus with a 14×6 rectangle as its fundamental domain, but surely we can do better.

The Devil’s in the Angles

~ munizao ~ Leave a comment

Recently, while I was considering possible designs for a puzzle for my exchange gift for the next Gathering for Gardner, I thought about doing something with multiple layers of clear plastic, where interactions of markings on the layers define the puzzle. When you’re going to lasercut a large quantity of puzzles, keeping down the cost, and therefore the cut length, is paramount. So I wanted to be able to use the simplest possible markings on the pieces.

A straight line segment looked like a pretty good candidate, and it leads to an obvious puzzle goal: make the segments on two layers perpendicular. I still needed to choose pieces for these markings, but after a little trial and error, I landed on dominoes, with a segment centered in each square. For these, given some reasonable restriction on the allowable angles of the segments, the number of different pieces possible would land somewhere in the range of what would make for a good puzzle.

I ended up using segments that were turned either 15° or 45° off from the edges of the pieces. These admit exactly 12 different pieces, which can tile two layers of a 3×4 rectangle:


What makes this set particularly nice is that you can get two more puzzle challenges by changing the goal angle for the crossing segments. In addition to making them all perpendicular, you can make them all cross at 30° or 60°. These challenges should be easier, as there are two ways for an angle to differ from another one by 30° or 60°, but only one way to be perpendicular.

I also found a related puzzle that uses 10 dihexes. There are 13 pieces possible in this scheme, but I’ve omitted the ones with a lengthwise axis of symmetry from the puzzle:

In the end, I decided not to make either of these my exchange gift. I had a couple of prototypes made of the first puzzle, and it was clear to me that it needed to be larger than I could afford to make it and give away a few hundred copies. It also works best with a frame to hold the pieces and keep them neatly aligned, which adds considerably to the time and expense per copy. But even though I won’t be able to give this away at G4G13, I hope to be able to be able to sell a few copies at my vendor table there!

Isolating small pieces: submitted solutions

~ munizao ~ 1 Comment

A couple of submitted solutions on the theme of isolating small pieces in tilings of polyominoes of mixed sizes:

George Sicherman solved problem #44. (Tile a certain torus with the 1–5-ominoes such that the 1–4-ominoes do not touch each other. Finding a solution where none of the smaller pieces even meet at corners was optional, but well appreciated!) This solution contains four “crossroads”, or points where four polyominoes meet. These are sometimes considered an aesthetic flaw in a polyomino tiling, and whether or not you agree with that, finding solutions without them tends to be good for an extra challenge.

Problem #44a: find a solution for problem #44 without crossroads.

Jaap Scherphuis analyzed this challenge that was included with my Agincourt puzzle: find a tiling of an 8×8 square where none of the dominoes and trominoes touch each other or the outer edge. He found that there were 32 solutions. In just one of these, none of the smaller pieces meet at a corner:

I don’t feel that I acknowledge other puzzle creators enough in this space, so I want to give a shout out to Kadon for their Mini-Iamond Ring puzzle, which contains all of the 2–5-iamonds, and includes as a challenge isolating all of the different sizes of pieces:

Tiling tilted tori

~ munizao ~ 4 Comments

A friend of mine recently complained about not being able to tile anything nice with the full set of polyominoes of size 1 though 5. (No, I didn’t make that up! I have weird friends. Who are not made up.) The area of these pieces is 89, which is prime. So our usual tactic of making a rectangle using divisors of the area won’t work.

But there is in fact something highly symmetrical that these pieces can tile. And its existence follows from the fact that while 89 may not be composite, it is the sum of two squares. 89 = 25 + 64 = 52 + 82.

Taking the sum of two squares may remind you of the Pythagorean Theorem, and that is exactly where I was headed. Make a right triangle where the legs have length 5 and 8, and the hypotenuse will have a length of sqrt(89). And then, naturally, if you make a square out of four sides with that length, it will have an area of 89:
area-89-square

So I have something that indeed has the desired area, but you might complain that having sides that slice obliquely to the square grid makes it entirely unsuitable for tiling with a set of polyominoes. But suppose we stitched the pairs of opposite sides together. That would turn the figure into a torus, which “unwraps” into a repeated, plane-filling pattern:
1-5-ominoes-torus
Which we can tile! If fact, tori are generally relatively easy to tile because they have no edges, and the edge is typically the hardest part of a pattern to tile. Having small pieces in the mix, as we do here, also tends to make tiling easier. So for a challenge, we could try something harder.

Problem #44:

Find a a tiling of the torus above with the 1–5-ominoes where none of the pieces of size 4 or smaller are adjacent to each other. Touching at corners is okay, but if you can find a solution without that, that’s even better. (Weird, it’s been three years since I’ve posed a numbered problem on this blog.)

This problem runs into a wall in my current setup for solving polyform tiling problems. I typically add ugly hacks to my copy of David Googer’s Polyform Puzzler. It’s reasonably handy because it’s open source and written in my language of choice, Python. But it doesn’t include a hook for pruning the search tree when you come to a configuration that doesn’t meet a desired condition. For problems with a small enough search space this doesn’t matter; you can just filter finished solutions as long as the time needed to run a complete search is reasonable. But here the high tilability is actually a curse: the solver starts in an area of the search space where the adjacency condition isn’t met, and because the pieces are so numerous and so tilable, it can stay there for an extremely long time before it decides to change out any of the tiles placed early on. (There are technical reasons why hacking in the hook I would need appears to be difficult, but I won’t get into those here.)

Coincidentally, the area of the 1–4-ominoes, 29, is also a sum of squares:
1-4-ominoes-torus
Any parallelogram can be used as the fundamental domain of a torus. Rectangle and rhombus shaped fundamental domains can have just as much symmetry as a tilted square. (Because the square is tilted, flipping it over isn’t a valid symmetry action, though rotating it still is.) But the tilted square tori still strike me as particularly pleasing and unexpected patterns for tiling.

A Polyformist’s Toolkit: Practical Topology

~ munizao ~ 6 Comments

In polyomino puzzles, we would frequently like to tile the simplest shape possible, and a rectangle usually seems to fit the bill. But sometimes a rectangle isn’t possible. For example, we can never make a 4×5 rectangle with the five tetrominoes. One way to prove this is with a checkerboard parity argument. Four of the 5 tetrominoes must always occupy even numbers of both black and white squares if they are placed on a checkerboard. The T tetromino must occupy odd numbers of each color. Therefore a rectangle must have odd numbers of each color, but any rectangle of size 20 will have colors evenly divided, 10 and 10. A similar argument can be made to show that the 35 hexominoes cannot tile a rectangle.

The tetrominoes, and a 5×4 rectangle.
This will never work…

Rather than give up and accept that we’ll need to find a less elegant shape to tile, we have another option. If we wrap the edges of a 5×4 rectangle around to form a cylinder, (so that the cylinder is 4 squares tall and 5 squares in circumference) tiling is once again possible. To see why this might be so, imagine that you are coloring the squares as in a checkerboard. Once you got back around to where you began, you would find that in order to continue the pattern, you would need to use the opposite colors from those you already used. Note that this would not work if you wrapped the rectangle in the other direction; because the other side has even length, the checkering colors remain consistent.

The tetrominoes tiling a 5×4 cylinder a cylinder
…until we wrap the rectangle into a cylinder.

There is a video by Edo Timmermans showing how a tetromino cylinder can be made with toy magnets. He claims that there are seven distinct tilings of a cylinder with the tetrominoes, and poses an interesting puzzle involving them. A commercially produced cylindrical polyomino puzzle is Logiq Tower, designed by Marko Pavlović, which uses wooden pentomino-based pieces that form a cylinder together with some other pieces. Because these pieces are inflexible, they lack some of the allowable symmetry actions of free pentominoes.

A cylinder isn’t our only option. We could give the rectangle a half-twist before connecting the ends; this gives us a Möbius strip. We could also connect both pairs of sides instead of one; this gives a structure that is topologically equivalent to a torus or doughnut. And then we could add twists to that— well, at this point it would be nice to be systematic so we can be sure that we’ve found all of the possibilities. One thing to note is that adding more twists doesn’t actually give us more possibilities. A strip with two twists will have exactly the same tilings as a strip with no twists, and in general, a strip with an even number of half-twists will have the same tilings as the no-twist strip, and a strip with an odd number of half-twists will have the same tilings as the Möbius strip. So for each dimension, we have three options: no connection, connection without a twist, and connection with a half-twist. This gives us the following matrix of possibilities:
Topologies for polyomino tilings
Only six possibilities here, not nine, because the ones in the lower left are equivalent to the ones across the main diagonal from them. Note that the Möbius strip, Klein bottle, and projective plane are nonorientable surfaces, which means that they effectively have only one side.

An important consideration when working with these is that one-sided polyominoes don’t exist on nonorientable surfaces. With one-sided polyominoes, translation is allowed, but reflection isn’t. However, on a non-orientable surface, translating far enough leaves an object in a reflected state.

Another consideration is that coloring is harder when we leave the plane behind. On the plane, we have a theorem stating that we never need to use more than four colors to make all of the tiles differ in color from all of their neighbors. On a torus, this may require seven colors. In 2001, Roger Phillips found 18 heptominoes that could tile a 7×7 torus, and sent these tilings to MathPuzzle.com. Here’s one:

7-colored 7-omino torus

Depending on the dimensions of the torus, it may be possible for a polyomino to wrap around and touch itself. In a strict sense, this makes any coloring impossible, since we don’t let tiles of the same color touch. However, we can follow a looser standard, and allow self-touching polyominoes in our colored tilings. Patrick Hamlyn found a 3-coloring of a tiling of the 35 hexominoes in 7 3×10 tori using this scheme in 2003:

The 35 hexominoes in 7 3×10 tori, 3-colored

This problem has no solutions if the tori are replaced with rectangles or cylinders.

Problems #31-37:
Though it seems like a pretty basic problem, if anyone has counted the number of pentomino tilings of cylinders, I am not aware of it. Wrapping the short sides of the 3×20 together should not give any solutions beyond the two obtained by wrapping the solutions on the 3×20 rectangle. That leaves the 3×20 wrapped the other way, and both ways of wrapping the 4×15, the 5×12, and the 6×10 rectangles.

Problems #38-40: Find the solution counts for the 4×15, 5×12, and 6×10 tori. I don’t know if these are all computationally tractable, but I can hope. (The 3×20 will be the same as the 3×20 cylinder with long sides wrapped together.)

Even more possibilities for tiling become available when you choose parallelograms with diagonal sides to wrap around, but this post is long enough, so that will have to be a matter for another post.