Pell Puzzles
Permutations, Probabilities, "Prose"
In exploring my recent obsession1, I was drawn to the 6x6 so-called Pell Tile. It’s made up of 8 strips of squares, each one of a unique length, and fits right in the intersection of small enough to hold in your mind’s eye and large enough to not be trivial.
This to me, at least visually, screams puzzle board. As a not-interested-in-recovering abstract puzzler, it reminds me of some super addicting classics: Rectangles, Palisade, Loopy, many others. What they all have in common is that they are purely deductive, each board is unique, and they don’t require a human being for construction.2 The question becomes… Can we turn this spiral into a puzzle?
Rules
Constraint sets the foundation for emergence.3 Some rules feel more arbitrary than others, like my decision to stop at 6x6 instead of 14x15. Others feel inherent to the definition of the thing, like the incrementing length of each strip. The further I explore mathematics, though, the more I’m reminded that it is fundamentally a volley between definition and deduction. Define this, then that must be the case, which leads to this other idea that demands more of a definition, etc.
So if I’m jumbling up our tile a bit and asking a puzzle-solver to fill in blanks, what deductive rules should I arm them with? Here is the list I came up with, with a big assist from some fellow puzzlers.
Each board is 6x6 squares in size. Each board contains 8 unique contiguous strips of squares that are of sizes 1 through 8. Strips cannot overlap, fill the same space, share an edge with itself,4 or leave the 6x6 boundary.
The endpoints of each strip will be denoted (on an unsolved board) with an X on one side and an O on the other. The 1-unit strip will only be represented with an X. So every board will contain 8 Xs, 7 Os, and 21 blank spaces.
A solved puzzle draws boundaries between strips that result in the 8 uniquely sized strips with an X at one endpoint and an O at the other (again, with the exception to this being the monomino).
Here’s a now familiar example, but in unsolved form:
Mechanics
If your brain is broken wired in the specific way mine also happens to be, you might have immediately started trying to make deductions on that puzzle board. Here’s how I’d step though it with pen and paper. If you feel like you already “get it”, feel free to skip ahead to the next section. I’ll be referring to squares by their row and column in that order, counting from the top left. So the northwest square is (1,1), northeast is (1,6), southwest is (6,1), and southeast is (6,6).
Draw an outer border and separate like symbols. I also notice here that the strip that contains the circle at (6,1) must extend eastward and added a separator from the adjacent (5,2) circle.
Claim the far-flung corners. Notice that (1,1) must belong to the same strip as (1,3). No other X can reach the corner without doubling back or dead-ending. By similar logic, (1,6) must connect to (1,4) and continue at least one square south.
Extend strips while avoiding dead ends and isolated symbols. The strip that “begins” at (1,3) must end at (5,1), or else the circle at (5,1) is cut off from all other Xs. The strip that begins at (1,4) cannot end at (3,4) or else it will create a dead end at (2,5), so it must go all the way to (6,6). We have our 7-strip and 8-strip locked in.
Return to the corner-snatching. (2,5) and (6,5) both need to get picked up, and both can only be picked up one valid way. 5-strip and 6-strip are also locked in. Running downhill now.
This leaves a small but dense cluster in the middle. The O on (3,4) is walled in to a 2-strip with the X on (3,3). The X on (2,2) can only reach one O - the one on (5,2). This checks off our 4-strip. This leaves us with a 1-strip and 3-strip and one last corner to snag. I hope I’m not assuming too much of my audience by leaving the last penstroke as an exercise for the reader.
Tactics
The puzzle board I just stepped through is, unless I made a profound error (which we are not counting out), fully constrained.5 There is one and only one valid solution which fulfills the clues and rules of the puzzle as they are laid out. However, it took some tinkering to find this specific set of Xs and Os.
Each Pell Puzzle solution (the final arrangement of strips) requires markings (or “clues”) at 15 squares. Once the solution is chosen, these locations are locked in. So is the monomino’s6 X, although solvers do not know which of the 8 Xs is the loner to start with. The remaining 14 clues are all members of polarized pairs, which means we make a binary decision about which marking to use 7 times. The “puzzlemaker” then has 2^7, or 128 boards that are all logically consistent ways of representing the eventually solved puzzle. However, they might be consistent with some other solutions as well.
Like any sane person, upon finding this out I scripted up a solver, ran through all 128 of these variations on the Pell Tile, and tallied how many possible solutions were implied by each arrangement of clues.
As much as I am tempted7 to dig hard into the why behind this histogram, I will walk away calmly with the knowledge that 16 of the 128 (exactly 1 in 8… I’m working so hard to leave this alone.) variations are fully constrained. That means in a generic sense, they’d work as purely deductive puzzles.
This is great news for grid deduction fans.8 Starting from an arrangement of these 8 polyomino strips in the 6x6 grid, we have a way of reducing the information down to complete but simple clues that fully constrain the solution. That begs the next question: How do we generate the strip arrangements in the first place?
Strategy
We need to tile the 6x6 grid with polyomino strips of lengths 1 through 8 in such a way that no strip shares an edge with itself. This is one of those statements that seems much more straightforward than it is. It’s very easy to sit down and scribble out a few valid boards pretty quickly, but programmatically generating them is an extremely non-trivial task. The combinatorics are explosive.
There are 440 ways to make an octomino strip with our constraints, which can in total be placed in 3,008 unique ways in the 6x6 grid.9 If we want to start building up valid combinations of strips, we need to intersect this set of 3,008 with the set of possible heptomino placements (1,808) and discard those combinations whose strips intersect. That requires checking 5,438,464 unique pairs and discarding 4,498,584 (~83%) of them.
So far we’re still pretty comfortably within the realm of computation on (my) local hardware over the course of a few hours. It blows up fast, though, because multiplication is so much bigger than that discard rate. If we try to add the hexomino (exactly 1,000 valid ways to place10) to our surviving set of valid combinations, we need to check 939,880,000 possibilities. A few hours becomes a few weeks, and we aren’t even halfway through the levels we need to add to the computation.11
There is a way, though, to keep this computational compound interest from bankrupting us. Employing a depth-first search helps us reject large swaths of the “tree” we’re exploring while searching for perfect leaves.12
It still takes a chunk of time to get through all of these combinations but now we have some solutions without having to wait for every solution to be found. I searched the whole space associated with the 8-7 root pictured above and found 20,884 ways to fill the grid. I have no idea how representative this set of solutions is for the whole space (I suspect not very, as some 8-7 pairings have no solutions), but within it, most can be constrained with X-and-O clues. Many can be fully constrained multiple ways. It’s a pretty long runway for when I start selling subscriptions to the once-daily puzzle. Until then, here’s a freebie:
If there’s a name for this general space, I don’t know it, but I might call it “convex incremental strip construction”.
This is in contrast to crosswords or other popular “authored” puzzles.
I don’t just mean this for math. Although it is true for math and the simplest of games (I’m looking at you, Go), I always return to this concept in art when it stretches genre and medium. Since I’m out of my depth the moment I say the word “art”, I’ll steal from a master and just leave this quote:
“I am sometimes told, ‘Because it is so structured, we have no freedom.’ The opposite is true, however.”
Sort of an aesthetic choice. In other words, no 2x2 pools and (although this is the edgiest of edge cases) the 8-strip can’t form a ring.
It might sound weird but in this context, “fully constrained” is a good thing. It means there is one answer. Saying something is not fully constrained means it requires some additional assumptions or worse, isn’t even a tractable problem.
My jaw was on the ground when I realized “domino” (2-mino) was related to “tetromino” (4-mino). It also gave me a deep appreciation for the game Blokus when I was later introduced to it. Maybe other people found this polyomino etymology to be obvious, but on the other hand, maybe you’re one of today’s 10,000.
As in, a lot.
There are dozens of us!
What an absolutely insane result. There are exactly one thousand ways to place a 1-width hexomino in a 6x6 grid. I will never forget this, and I hate that it’s only because of a numerological coincidence.
There are a lot of cute ways to remember the shift in scale when we talk about millions versus billions versus trillions. My favorite is time: a million seconds is 11.5 days, a billion seconds is 32 years. Use them to combat the (deliberately?) cavalier way these orders of magnitude are dispatched in (usually) political journalism, especially when discussing large sums of money. I wish I could go back and pick words for these numbers that didn’t rhyme.
Further reading: Knuth’s Algo X and Exact Cover