or, Group Theory on the Puzzle Page
Last week, I visited my dad, who still gets the newspaper.
(For my younger readers: that’s a stack of cheap paper printed with a detailed description of yesterday.)
Anyway, for an ungrateful millennial like me, a print newspaper means one thing: puzzles.
You already know the rules: nine rows, nine columns, and nine medium squares, each containing the digits 1 through 9. You’re given some; you fill in the rest. It looks something like this (by which I mean, “here’s an example lifted from the Wikipedia page”):
Now, I’m not much of a Sudoku player. (Crossword guy, to be honest.) But glancing at the puzzle, my dad and I got to wondering: How do they generate these puzzles?
We weren’t sure.
So we found a more tractable question: What if you were a lazy Sudoku maker?
That is, suppose you managed to generate a single Sudoku puzzle. (Or steal it from the Wikipedia page.) And suppose you wanted to make a few bucks selling collections of puzzles in airport bookshops. But there’s a catch: You’re not sure how to make more.
How many “different” puzzles can you get from a single Sudoku?
Well, let’s start with this: the numbers don’t actually matter.
For example, you could switch the 1’s and the 2’s. Nothing really changes. Every row still has a 1 and a 2. So does every column. So does every medium square.
The symbols in Sudoku are meaningless. It doesn’t matter what they are—numbers, letters, emoji. It just matters where they are.
Swapping 1’s and 2’s isn’t all we can do. You could also switch the 3’s and the 4’s. Or scramble the 8’s and 9’s. Or turn the 5’s into 6’s, the 6’s into 7’s, and the 7’s into 5’s.
There are a lot of ways to do this.
To see how many, let’s clean the slate, and turn them all into letters.
Now, for a, we have nine choices. Namely, it can be any digit.
Then, for b, we’ll have eight choices: any digit except the one claimed by a.
And for c we’ll have seven choices: any digit except the two already chosen.
Proceeding that way, we get 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 total possibilities. That’s also known as 9!, and it’s big: to be precise, 362,880.
Here’s an example, drawn at random from those nearly 400,000 possibilities:
We’ve already got a lot of puzzles, and we’ve only begun.
If you want another kind of change, you can switch the first and second column.
As with our number-shuffling above, the change is only superficial. Every column, every row, every medium square—they all still have the digits 1 through 9, precisely once each.
So we haven’t broken the puzzle, just reconfigured it slightly. That’s what we’re going for: costume changes that preserve the structure of the puzzle, while disguising it for human eyes.
How many puzzles does this kind of switcheroo give us?
Well, just focusing on the first three columns, we’ve got six possibilities:
We can also scramble the middle three columns, or the final three columns. That’s 6 x 6 x 6 possibilities so far.
Or, if we want, we can consider not just individual columns, but bands of columns, like this:
As above, these bands can be rearranged in six orders:
Thus, by rearranging these bands of columns, we’ve got 6 more possibilities, to multiply by our early 6 x 6 x 6. That’s a total of 64, or 1,296.
But of course, Sudoku is symmetrical! What we can do for columns, we can just as easily do for rows. So that gives another 1,296 rearrangements, any of which we can do in combination with any of the 1,296 above.
Multiply these together, and you’ve got 68, which is 1,679,616.
And remember: these rearrangements work for every single one of the 362,880 “different” puzzles we generated earlier by resequencing the numbers.
So, are we done?
We can also rotate the puzzles 90o.
Yeah, like that.
Obviously this puts the numbers sideways, but that’s a quick fix. And it gives us a totally new puzzle:
Other rotations are possible, too—we could go 180o, or 90o the other way—but these can be accomplished just as easily by rearranging rows and columns. (The same goes for various reflections.) That leaves us with just one relevant rotation.
This turns each puzzle above into 2 puzzles.
So, what are we left with?
That’s a lot.
Like, a lot a lot.
If your printer could print out one per second, it would take nearly 40,000 years to get them all. The paper would fill 14,000 stacks the height of Everest.
What we’re exploring here are the symmetries of Sudoku. They’re the transformations that don’t really transform, the changes that leave an object fundamentally the same.
Sudoku may be small—only 81 squares—but it has more than a trillion symmetries. All from a single puzzle.
Suffice it to say: That’s a lot of puzzle books.