On the heels of Representation and Uncertainty telling us to think more critically about our ontologies, I’d like to share a success story of ontological remodeling – that is, using new language to describe an existing thing. The existing thing in this case is the puzzle game Sudoku, which might seem a bit too straightforward to be described in a new way. You’re placing the digits 1 to 9 in a 9×9 grid without repeating a digit in a row, column, or box. There doesn’t seem to be space for unrepresented details in the way we’re interested in.

But here’s a quote from a January 2022 video of a man named Simon solving a Sudoku:

I now understand how to explain what’s going on in the puzzle. What I can tell you, what we’re going to end up with here, is that this digit, this digit, and this digit are a 1, 2, 3 triple. And isn’t it amazing? This, to me, is quite beautiful. I can tell you without fear of contradiction, if I had tried this puzzle two years ago…well, unless there is something else here that I’m not spotting, I might never have spotted that. Yet nowadays, because set equivalence theory has become so ingrained and practiced, it’s a very quick spot. And that being a 1, 2, 3 triple is just remarkably gorgeous. So how do we prove this is a 1, 2, 3 triple…? I mean, this puzzle could appear in the World Puzzle Championship now. There’s no way this could have appeared a few years ago, no one would have been able to do it! But now, that break-in is so well-signaled it’s almost fair!

We haven’t made any breaking new discoveries about the digits 1 to 9. But this set equivalence theory, whatever it is, has changed how Simon views puzzles so much that it’s not even comparable to two years ago. It’s all still just digits in a grid, but describing them differently leads you to a new conclusion. And precisely because Sudoku is so simply defined, the case study of set equivalence theory is worth studying. If we can find hidden secrets here, in a 9×9 grid of single digits, we can find them anywhere.

Let’s start by explicating the existing, “normal” ontology for a Sudoku. The rules specify that you have exactly one of each digit from one to nine in every row, column, and box – so it’s no surprise that these are the usual terms used to describe Sudoku puzzles. For example, you might say “I know that row 2 needs a 3, and it can only go in to this square,” or “Box 5 already has a 9, so the 9 can’t be in any of the other cells in box 5.” Because the explicit impact of the rules is based on these sorts of divisions, it’s a very useful ontology to have.

But that’s not the only way you could describe a Sudoku. You could partition the grid into an orange ostrich head and a fat green frog:

There are things you can say about these shapes. No digit can appear in the ostrich head more than three times, because its only in three boxes total. A digit that appears on one of the frog legs won’t appear on the other, because they’re in the same row. While these claims are true, they’re ultimately just pointing back to the words we were comfortable with already. Drawing the ostrich and the frog didn’t really accomplish anything.

Ontologies can’t exactly be wrong, since they’re just methods of description. But it’s pretty obvious that this one isn’t useful. It doesn’t let you state anything new that you couldn’t state using your previous vocabulary. It’s just an unnecessary level of abstraction that has to be peeled away to get to the useful ontology.

Here’s another way you could partition the sudoku: one blue ring in the center, and four orange anchors in the corners.

Is this any better than our frog and ostrich? Does it let us make any statements that we couldn’t easily make with row, column, and box? As it happens, yes. You can truthfully make the following statement: “The digits in the ring are exactly the same as the digits in the four anchors.”

Wait, what?

This surprising fact is called “Phistomofel’s Theorem”, named for the setter who initially popularized it. It’s a specific example of set equivalence theory that helped many people (myself included) understand it. Imagine that the letters 1 to 9 were all on tiles, like in a game of Scrabble. Each row, column, or box has the tiles 1 to 9 once each. Suppose you took the tiles in these two rows and these two boxes and put them in a blue sack:

Row 4, Row 7, Box 4, and Box 7 each have a run of the digits 1-9, so in total the blue sack has 36 tiles, four copies of each digit. Now, take a clone of your puzzle. This time, put these four columns in an orange sack:

Since both sacks have 4 runs of the digits 1 to 9, they have the same composition of digits inside them. But now, let’s superimpose the contents of the two sacks on to one grid, and look at the cells with both colors:

The cells with both colors are in both sacks. If you take the exact same cell out of both sacks, then clearly the two identical sacks will remain identical – you took the same thing out of each of them. You can do this for every cell with two colors. So, removing them all from our superimposed grid, we’re left with this:

That’s how we know that the digit composition of these regions – the ring and the anchors – are identical. And that means that this is a useful upgrade to our ontology, because now we can make statements like “There are two sixes in the ring, and only two spots in the anchors where a six can go, so there must be a six in each of them.” Those statements would be extremely tedious and unintuitive to make solely in terms of rows, columns, and boxes.Once you’ve gotten the hang of Phistomofel’s Theorem, it’s a relatively short jump to using set equivalence theory in general. When we were picking runs of the digits 1-9, we made those particular choices because they happened to have a lot of overlap to them. But the core logic works for any regions that you make out of complete sets of the digits 1 to 9 – you can always eliminate the overlap and say that what’s left of the two regions are equal.

On its own, this is a neat bit of Sudoku trivia that might happen to pop up now and then in a puzzle. But what’s really interesting is when a puzzle is designed around this phenomenon. Setters (the term of art for people who design hand-crafted Sudoku puzzles for solvers to work through) can make a puzzle that’s virtually impossible using just rows, columns, and boxes, and can only be solved by upgrading your ontology. The Youtube channel Cracking the Cryptic has been an excellent source documenting this evolution.

Now I can reveal where that quote up top came from: a video from Cracking the Cryptic called How to Make an Impossible Sudoku Easy. (I’ll