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.
Like Sudoku.
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?
Not quite.
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.
As an avid sudoku fan (my fav: http://samurai-sudoku.com/) I found this highly amusing 🙂
Thank you
Reblogged this on O LADO ESCURO DA LUA.
I love the post, however I was thrown for a loop and had to re-read to follow the explanation when you got to “Or, if we want, we can consider not just individual columns, but bands of columns, like this:”.
Personally I think it would have been clearer if the diagrams you did after that used unique colors [not yellow, blue & purple] from the prior set of puzzles and/or a statement to the effect of, “Thus, just bY rearranging columns, we’ve got 6” MORE possibilities to combine with the 6^3 from rearranging columns giving, “6 x 6 x 6 x 6 new possibilities. That’s 6^4, or 1,296.”
Thanks for the edit! Incorporated. I’ll change the color int he diagrams if I get a chance, too
The switching of columns and/or rows may result in legal Sudoku variations but it would likely break the expected symmetry of a Sudoku puzzle. For example if the starting grid has cell (1,1) filled in with a number, then aesthetics dictate that cell (9,9) also be provided. Most Sudoku puzzle publishers would frown on a book that had asymmetric puzzles. You could still do certain swapping to retain symmetry and have more than enough variations, but then the next question would solvers notice this and feel like every puzzle had about the same solving strategy and difficulty? It would be interesting to test.
It’s funny, I hadn’t really paid attention the aesthetics of Sudoku before, but you’re totally right. If you look at the initial position of Sudoku as a collection of “filled” squares and “empty” squares (ignoring the specific numbers), then it seems like the puzzle is supposed to be preserved under a 180 degree rotation (and ideally under a 90 degree rotation as well). That would cut down pretty dramatically on the number of possibilities (though how many orders of magnitude you lose, I’m not sure).
As for the solving question, my pet hypothesis is that the different permutations of an “easy” puzzle would actually feel different to solvers, because such puzzles permit multiple strategies to solution, and a random change is likely to elicit a new strategy from you. But I’d expect that different permutations of a “hard” puzzle would feel dully repetitive, because you really would be using the same solving strategy over and over. But you’re probably right that an actual test would be in order!
Similarly, crossword puzzles always have 180 degree rotational symmetry, and furthermore are invariably odd squares. This has always been so, but nobody knows why: the diagramless word puzzles they descend from generally used symmetrical shapes, such as squares and diamonds (the first true crossword puzzle was a symmetrical diamond). Cryptic crosswords also have a convention that about half the letters in each word overlap with some other word: in American-style puzzles, of course, all the letters overlap.
One thing you need to consider is the stabilizer of the Sudoku board. Some symmetries might give back the same Sudoku. Then you need to divide by the order of the stabilizer group to get the actual number of different Sudoku boards. It’s possible that the stabilizer is trivial, but this would require some proof.
Yeah, that’s a good point. My hunch is that the “generic” Sudoku would have a small stabilizer (maybe just the identity) but that you could probably construct special cases with much larger stabilizers. Merits further thought.
I did this calculation a few years back (and came to the same answer, and glibbly skipped over the stabiliser. My feeling is that non-trivial stabilisers are quite rare both in general, and for those puzzles with given clues in a symmetric pattern (as is the “norm”).
I’m not sure it’s possible to get stabilisers bigger than order 2 (a 180 degree rotation being the same thing as a permutation of the symbols) where the puzzle has a unique solution – by uniqueness the non trivial stabiliser would also have to preserve the fully solved grid which feels like a fairly unlikely thing to do.
Actually, these calculations were all done a few years ago – see http://www.afjarvis.staff.shef.ac.uk/sudoku/. The total number of grids was worked out, and the total number of “essentially different” grids – and when you divide the first by the second, you get 1218935174261.0998…., which is very near your 1218998108160. And the page http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html works out all the stabilisers – it looks like the orders of permutations in the stabiliser must be 1, 2, 3, 4, 6 or 9, although perhaps some grids have stabilisers whose size is a product of some of these.
i wonder about Sudoku too, here are a few things:
If the puzzle does not have a unique solution then it probably is never included in the newspaper or in a puzzle book. And I expect that any of the symmetries above would never produce a puzzle that did not have a unique solution if it started with a unique solution, and conversely no symmetry would change a puzzle that had no unique solution to one that did.
There are different ‘difficulty’ ratings. I wonder how they are determined. For example the one in the post seems to have a pretty easy rating. I could solve it by just working my way through the numbers in a straightforward way.
I wonder if any of the symmetries of the above puzzle would result in a change to the difficulty level.
I think the answer is no.
I’ve read different strategies and some are most definitely more complex than just looking at the numbers in turn and filling in the obvious choices.
The symmetric puzzle would have the exact same clues to solve it and so should be the exact same difficulty. From one point of view it is the same puzzle. It just looks different.
Regarding unique solutions, it is a tactic to assume that there is a unique solution. There are times where the choice of a number to go in one box would leave you in a place were it will be impossible to find a unique solution. And since we assume there is a unique solution we can reject that choice.
A detailed description of yesterday!
I know, I’m a big yesterday fan! I miss the days when “yesterday” was still seen as fresh stuff.
Thanks for the interesting post! I’ve often wondered how a game designer knows just how many (and which) numbers to give as clues in a Sudoku puzzle, to ensure that there’s enough information to solve it and that there is only one solution. Is this determinable by mathematical analysis, too?
When I first read “different ways to play the same Sudoko” I was thinking about a different kind of variation. Instead of considering how you can shuffle the starting, non-filled-in Sudoku, I was thinking about how many different puzzles you can make given one solution. That’s not really enough to well define the question, I guess; a Sudoko with just one cell blank shouldn’t count. But perhaps you see what I am driving at.
I thought the same! How many ways to remove numbers while still leaving a unique solution.
I can tell you how I generate Sudokus in my Android App. It is done on the device itself.
I fill in very few random numbers, and find a solution of this Sudoku “problem”. I then remove numbers from the solution until it gets non-unique. Surprisingly, this is fast enough to be done on a handheld.
Rene
In case you’re curious, one of the professors in my group at UC Irvine wrote his own program to generate Sudoku puzzles: http://11011110.livejournal.com/335.html.
I haven’t looked at it in detail, but I believe it does the following:
– Generate a random Sudoku puzzle.
– Check that it has exactly one solution.
– Check that that solution can be reached by following various common strategies used by humans, so it can be solved without trial and error.
Sudoku game is not for everybody. You need to have sense and be pretty smart for solving Sudoku games. Otherwise, you will be solving only easy Sudoku games forever.
This makes me wonder: if roughly 10^12 puzzles can be generated from any puzzle, how many unique puzzles are there? I.e., given the space of all Sudoku puzzles, how many seed puzzles (or archetypes, or whatever you want to call them) does it take to generate that space? Wouldn’t it be fascinating if the answer is 1? (I doubt that’s the case, but it would be fascinating.)
Wouldn’t there be a gazillion more if you chose how many numbers to provide each time? (Would be difficult to know exactly which numbers and how many numbers to take away, but mentioning this would emphasize your point waaaaa…y more.) And wouldn’t you have to subtract overlapping puzzles from that total? If some puzzles are rotated, can’t they end up like other puzzles?
I’m not a sudoku player (More of a logic person, really. No numbers, ever.), but that’s really interesting.
Sudoku is pure logic. As he mentioned, you can switch the numbers out for any collection of nine symbols.
I just found your blog today, and I love it. It’s xkcd, but with math instead of physics and tech.
Not everyone has the sense to understand it quite easily. But your post seems to be quite easy to understand the symmetrical sudoku. 🙂 Maybe we should get a post on Rubik’s cube?
I have developed a new sudoku puzzle game “Sudoku Octangles” for iPads and iPhones:
https://apps.apple.com/us/app/sudoku-octangles-numbers-game/id1480851707
I hope you like
I note that your swapping columns and rows misses the combination of not swapping. On its own this seems perverse but combined with the swapping of the other sets of columns adds another set so your 6^4 becomes 7^3×6.
Love the blog and books