Don’t connect four

Dave Budd

17 November 2025

• X
• Facebook
• Reddit
• LinkedIn
• Threads
• Mastodon

Every month, people from all over the world meet up locally for MathsJam, where we share cool puzzles, games and problems. There is also an annual gathering of all of us maths enthusiasts, and at last year’s event this was one of the many puzzle competitions:

Place the most points on the vertices of a triangular lattice such that all points are connected, but no more than three points are allowed to be collinear.

For example:

The blue and green dots are not connected so this is not allowed.

The four orange dots are collinear so this is not allowed.

This is allowed

Polyominoes

Alternatively, the puzzle could have been framed to say:

Make a single pattern of tiled hexagons where no more than three tile centres are allowed to be collinear.

The same example images could look like this:

The blue and green hexagons are not connected so this is not allowed.

The centres of the four orange hexagons are collinear so this is not allowed

This is allowed

Patterns of connected tiles such as these are called polyominoes, and the tiles themselves are called cells. The examples on the previous page use a hexagon as the cell type, and the hexagonal polyominoes produced are sometimes called polyhexes. Other shapes can be used as the cell type, and it’s most likely that you will come across square polyominoes. The unqualified term polyomino is often used on its own to assume square cells.

Just like polygons, we name the subsets based on their size, so a domino is a polyomino of two cells, a triomino has three cells, and then there are the familiar tetrominoes used in the game of Tetris.

Keeping in the context of the square, the next size, of five cells, are the pentominoes. There are 12 of them, and there is also a nice puzzle here: Can you fit them all inside a rectangle, say $6\times10$, without them overlapping each other?

The five tetrominoes (if reflections are treated as the same)

The 12 petrominoes

As we increase the number of cells, the number of possible shapes grows exponentially, and it is not easy to count how many there are of a given size. We also have to be clear about what we are counting. If we rotate or reflect the pattern and it looks different, should we count it as a genuine new instance or ignore it as a duplication because of symmetry? The terms free and fixed have been adopted to make this distinction. Here’s an example of a free pentomino:

And here are the eight fixed symmetrical versions of it:

So when counting free polyominoes, we ignore the symmetrically equivalent ones as duplicates. People interested in counting the number of each size have got up to working out that there are 2,150,182,610,161,041,739,167,164,220 free polynomials that can be made with 50 squares and 18,500,792,645,885,711,270,652,890,811,942,343,400,814 fixed polynomials that can be made with 70 squares.

These huge numbers are sourced from the On-Line Encyclopedia of Integer Sequences (OEIS), which is a great resource I recommend checking out if it’s new to you (see sequences A000105 for free and A001168 for fixed).

Polyomino collinearity

So far, we have seen two attributes of a polyomino, the type (cell shape) and the size (number of cells). Inspired by the opening puzzle, I decided to explore cellular collinearity. If we say that a subset of cells within a given polyomino are collinear if their centres are on the same line, then I define the collinearity of the polyomino to be the size of the largest possible subset. In other words, the maximum number of cells that are collinear. I’ve not come across any standard way of notating polyomino meta data, so the following notation to describe this breakdown more algebraically is purely something I’ve made up for this context. \begin{align*} P(n) &= \text{set of all polyominoes with $n$ cells},\\ P(n,k) &= \text{set of all polyominoes with $n$ cells}\\[-0.8mm]&\hspace{4.2mm}\text{and a collinearity of $k$}. \end{align*}

So $P(n)$ is made from the union of disjoint sets $P(n,k)$: \begin{align*} P(n) = P(n,1)\cup P(n,2)\cup \cdots \cup P(n,k). \end{align*} The cardinality of a set is the number of members it contains. So, for example, in the diagram below the cardinality of $P(4)$ is $|P(4)|=5$ because there are five free polyominoes that have four cells (the Tetris shapes).

Breaking up the sets by collinearity

Computer search

As mentioned earlier, the counting of free polyominoes is not a simple task for several reasons:

• the nature of how they evolve,
• the possibility of symmetric duplicates,
• being completely sure none have been missed out.

I love writing code to investigate maths stuff and this exploration had a lot of great challenges. Deciding how to model the polyominoes, handle the symmetry (especially the hexagon), determine the collinearity, visualise the results, ensure a complete search and all running in an optimal time meant there was a rich stew of consideration to stir during my idle thoughts over that autumn.

Finding every member of $P(n,k)$: adding a cell increase $n$ by 1, and either increases $k$ by 1 or leaves it unchanged.

To be sure that I was counting all possibilities, I took the iterative approach of getting a result for $P(n)$ by using what I had already found for $P(n-1)$. For example, starting with the tetrominoes, for each one, add a new cell at every possible new location to get all the possible pentominoes.

We can further refine this method for collinearity, on the basis that adding a new cell can only ever increase the collinearity by one, or leave it unchanged. So in order to find $P(n,k)$, we only need to consider polyominoes in $P(n-1,k-1)$ and $P(n-1,k)$ as the starting point for adding a new cell.

Flowchart of the algorithm

If adding this new cell does not give a polyomino with the collinearity we require, then we discard and try another new cell. But if it does, then we need to be sure that we are not double counting a previously found shape that is a symmetric or translated equivalent of it. To stop that happening, there is a normalisation step which orients newly discovered polyominoes in a consistent fashion to make it easy to tell if any two shapes are the same. In other words, if a set of fixed polyominoes are all actually the same shape, just symmetrically different, then normalisation will orient them all to the same shape, so then comparing them for being the same becomes an easy task.

To the right, there is a flowchart explaining how the algorithm works.

If you want to look at the Python code, it’s at github.com/daveisagit/collinear-polyominoes. The results of the searches are available on the OEIS: A377942 is the sequence for square cells, and A378015 is the sequence for hexagonal cells. The first ten rows of A377942 are shown below.

The first ten rows of A377942: $|P(n,k)|$ for square cells

Square polyominoes

Before heading back to the motivation for looking at collinearity (the puzzle), which was to find the largest hexagonal polyomino with a collinearity of 3, let us look at the square as it is a simpler case. You’ll see from the example data in A377942 and just looking at the vertical sequence where $k=3$ that it starts to descend when $n=10$, $P(10,3)=78$ as highlighted. In other words, there comes a point when the polyominoes become so large that finding ones with collinearity $k \leq 3$ gets harder, and there are fewer of them as we increase the size.
It turns out that for $k \leq 3$ the sequence is finite (A378169), having just 15 terms and the last term being 1 means that there’s only one largest square polyomino with a collinearity of 3. It looks like this:

It seems unnecessary now to separate the lower values of $k$ since they are mostly zeros, and so let’s just consider the cumulative amount for $k$, or in other words, where the collinearity of the polyomino $\leq k$. Extending our notation to express this cumulative amount as

\begin{align*} C(n,k) = P(n,1) \cup P(n,2) \cup \cdots \cup P(n,k). \end{align*}

The number of polyominoes with collinearity of 3 or less ($T_n$) as the number of cells ($n$) increases resembles a bell curve

That is, $C(n,k)$ is the set of all polyominoes with $n$ cells, and a collinearity $\leq k$. We can then make a sequence using $T_{n}=|C(n,3)|$ where $T_{n}$ is the $n$th term of it (using $T_n$ to notate the $n$th term of a sequence is a typical notation). Charting the values of $T_n$ forms something close to a bell curve: 1, 1, 2, 4, 9, 18, 37, 62, 86, 78, 61, 34, 14, 4, 1.

The largest square polyomino with a collinearity of 3 being made by the algorithm.

Playomino

Screenshot of playomino.pages.dev

I like a good (and preferably simple) proof and so wanted to prove that there would be an upper bound for $n$ based on the maximum allowed collinearity $k$. Internet searches return a few papers that may fit the bill, but I cannot easily digest and regurgitate them into something palatable. So instead of putting effort into trying to concoct some hard to follow proof, I spent the time developing a little web app that allows you to explore things for yourself. I invite you to visit playomino.pages.dev to get a feel for how collinearity becomes a restrictive attribute in creating both square and hexagon polyominoes.

Trying to use thin steps still runs into the collinearity restriction

It seems that whatever you do, after a while, you run out of space. Staying in a local area hits a limit, and if you try to escape to another local area, then the path you take to get there becomes a problem too.

OK, so what about increasing the collinearity limit to $k\leq 4$? I soon discovered that it would take a long time to compute using my current approach and code, but in the spirit of adventure I thought it was worth the risk of burning out my laptop processor. Three months later, after analysing 150 million polyominoes, I had a result! It turns out to be a polyomino of size 48, but I am deliberately holding back on what it looks like for now, as I don’t want to create spoilers for what might be a future competition somewhere. There are \num{135629410647775553284438364} polyominoes of size 48, but only one of them has no more than four collinear cells!

Again, it gives a similar bell curve weighted to the right but with a significant leap in the number of polyominoes found (A380990).

Number of polyominoes with a collinearity of 4 or less

So we now have the beginnings of another new sequence, the largest number of cells of a polyomino with at most $n$ collinear cell centres. (A380991) It starts $1,4,15,48,\dots$ but will we ever know what comes next? In terms of where to next, I think it would be amazing if someone could come up with a formula for a good upper bound (let alone a least upper bound) for a given collinearity $k$ and I would love to know if this collinearity attribute of polyominoes has any relevant application outside of puzzle land.

Thank you

Before wrapping up, I want to emphasise that this whole journey down this rabbit hole has been epic! I am sure without the MathsJam community, Chalkdust and OEIS, I would still be maths-curious, but without them it would certainly not be as joyous. Thank you all. Special thanks to Declan O’Donnell for coming up with his elegant competition entry, `Dots on a tiling’: without it, none of this would have happened. I also apologies to him, too, for giving away (close the magazine now, to avoid reading) the answer.

Hexagonal polyominoes

So, we come full circle back to the puzzle. What is the largest hexagonal polyomino with a collinearity of 3? Like the square, the sequence (A377756) is finite and forms a sort of bell curve. But unlike the square, there are two different, but similar looking answers for the largest size.

The answer is 23!

For me personally, their twin-like nature and constellation-like appearance have a lot of character, and I named them Elliott and Isaac.

Twenty years ago, we lost our newborn twins a couple of days after their birth. Despite all the water under the bridge since then, I still think of them, and usually when noticing something in an abstract way, like a couple of butterflies dancing on the breeze or a pair of polyominoes presented on a page. Thank you Chalkdust for allowing me to remember them in this way.

Elliott

Isaac

Dave Budd

Dave is a recreational mathematician, tutor and software engineer in Bristol, and when he is not in the pub solving puzzles with his MathsJam friends, you can find him playing guitar with The Faraway Things (a local jazz band).

All articles by Dave