Tag: polykings

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!

Proper Polyking Solutions

~ munizao ~ Leave a comment

George Sicherman sent in some solutions to Problem 51, which was to tile a certain torus with the proper polykings and a monomino hole. There were several optional challenges presented, and each of these solutions met two of them. (For the present post, we’ll pretend that challenge 4 asked specifically for a 4-coloring, rather than vaguely asking for a reduced number of colors.) The first satisfied the no-crossed bridges constraint and the no four-piece corner constraint:

The second is 4-colorable, and has no crossed bridges:

And the third is 4-colorable, and has no “fault lines” passing through it:

These results got me thinking about the combinatorics of independent optional challenges of a given problem. A realizable subset of optional challenges is “optimal” if it isn’t a proper subset of another realizable optional challenge set. From the perspective of a problem designer, a full set of optional challenges might be said to optimize interest if it maximizes the number of optimal realizable subsets. For example, problem 51, with four optional challenges, would be most interesting if all six pairs of challenges were realizable, but no triples of challenges were. In general, a problem with n optional challenges will be optimally interesting if all realizable subsets of size n/2 are optimal, if n is even. For odd n, optimal realizable subsets would have to be all of size (n + 1) / 2 or all of size (n – 1) / 2.

Problem 51a: Make Problem 51 “better” by finding solutions with that satisfy missing pairs of challenges.

Problem 51b: Make Problem 51 “worse” by finding solutions that satisfy a set of challenges that is a superset of two or more of the challenge pairs satisfied by the above solutions.

Metaproblem: Design an optimally interesting puzzle with four or more challenges!

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.