Early last year I became aware of a paper by Jamie Tucker-Foltz on Locked Polyomino Tilings. It defines a recombination move on a tiling of n-ominoes as creating a new tiling by removing an adjacent pair of tiles and replacing them with a pair of tiles in different positions. Locked tilings are those that admit no recombination moves. Remarkably, for both 4- and 5-ominoes, there is a unique smallest square locked tiling:

The concept of moves between tilings seemed like a promising source of puzzles. Given a tiling, we could try to find a recombination path to a different tiling with specified properties. For example, starting with a tiling of 12 P pentominoes in a 6×10 rectangle, our goal might be to make recombination moves until we arrive at a tiling with all 12 pentominoes.

But from the perspective of designing a physical puzzle, removing and replacing pieces two at a time seems unnecessarily complicated. A better puzzling experience ought to result from removing and replacing pieces one at a time. This doesn’t create a move between tilings, but works just fine as a move between packings. (In fact, sliding block puzzles can be seen as using just such a move.)

After some experimentation with various sets of polyforms, I came up with one that was very promising. There are 10 one-sided tetrahexes. We can pack 9 copies of one of them in a hexagonal figure, leaving a one-hex hole. Now our goal is to form a packing of the other nine pieces in the same frame. These pieces begin in our unused supply, and at every move, we return one piece from the tiling to the supply, and then take one piece from the supply and put it in the frame. The removed and replaced piece can be the same; there are some positions where we might want to change the orientation of a piece, moving the hole. Notice that we can never have more than one of the pieces in yellow below. This was not a restriction in the original problem from the Tucker-Foltz paper, but it seems like a reasonable one for a physical puzzle where we want to limit the production cost of the pieces.

Here are a couple of representative packings of each set. Can a chain of moves be made from a packing of the first type to one of the second? (Not necessarily the packings shown.) This is Problem #63. I got very close while trying to solve it manually, but I couldn’t get all the way there.

Finally, there was another direction I went in exploring this type of problem which was very fruitful indeed. At one point, before I tried the tetrahexes, I was having difficulty finding any polyform that might work. I decided to try the simplest set of polyforms I could come up with: one-dimensional polyominoes. Of course, 1D polyominoes can be represented as integers, and a tiling is simply an ordered list of integers.

Then I needed moves that could be made on this such a list, and a goal to be achieved by a chain of moves. The simplest moves I could think of were splitting a number into two smaller positive integers that sum to it, and merging two adjacent numbers to produce their sum. Since these moves are inverses of each other, we can backtrack through the space of lists if we need to, which is a nice feature in a puzzle. For a goal, I decided to use reversing the list, at least until I could think of something better.

Now, it’s clear that there are a couple of trivial strategies that prevent this from being any kind of puzzle at all. One is to decompose all of our integers into 1’s, and then recombine them to make our desired list. A simple rule to prevent that is to disallow making a list that contains more than one of the same integer. Another is to combine all of the list into one big number, and then split it down from there. The simple rule I found to prevent that strategy was to disallow any number greater than the greatest number in the original list. As an example, with the list [7, 2], the following chain would be a valid solution: [7, 2] → [6, 1, 2] → [6, 3] → [2, 4, 3] → [2, 7].

After playing with a few lists using these rules, I was surprised to discover that some of them made decidedly non-trivial puzzles. (And I stuck with reversing the list as a goal, as I never did come up with something better.) I wrote up the puzzle as a post on my Mastodon account. And then some funny things happened.

My Mastodon post was picked up by Hacker News, a popular bulletin board site for programmers, where it briefly was ranked high enough to make the front page. Some commenters wrote code to explore different lists, looking for ones with long minimal length solution paths. Others wrote interactive playable versions. Arthur O’Dwyer wrote a blog post about the puzzle. (Read that one for a deeper look at the puzzle and the behavior of different lists. I’m not writing that post here, because it already exists.) Tomas Rokicki submitted an integer sequence related to the behavior of the puzzle to the OEIS. I gave an informal talk about the puzzle at a Gathering 4 Gardner Zoom Social, and I started writing my own snazzy interactive version of the game. With Skona Brittain, who used the puzzle as an activity for young math learners, I presented the puzzle to a group of folks who study mathematical puzzles and pedagogy. This little puzzle that I dashed off a quick Mastodon post about has gotten as much engagement as all of my other explorations in recreational math put together.

And now I must segue to a real world concern. I am very underemployed, and I am looking for work. Part of my motivation for writing that snazzy interactive version was to have a portfolio piece to show off my skills in Javascript, React, and CSS. I am generally looking for web development positions, but I’m also interested in other software development positions. I live in the Portland, Oregon area, but I’m willing to consider remote positions.