Sudoku enumeration: the symmetry groupFirst Faved : May 21 2008 by darrellpFaved : 2 times with notesViewed : 20 timesFave It!
Faves for this Web page
- mike - May 22 2008 | sudoku, math, group theory, puzzles
There are only 5 billion essentially distinct Sudoku puzzles (solutions) (proof here using Group Theory and Burnside's Lemma).
- darrellp - May 21 2008 | sudoku math puzzles
Mike was asking how many essentially different sudoku grids there are. Here's the answer...
Votes for this web page
Already a user? Sign In
Add a Fave for this Web page
- What happens when I press Publish?
- Your Fave for this Web page gets shared with the Faves community. You can access it at any time by selecting "My Faves" from the menu above.
- Why do you ask for my email address?
- We use your email address to create an account, so you can easily find your Fave again at a later time.
Related Content from Around Faves
puzzle
-
Custom wooden jigsawa puzzles
1 FaverViewed: 6 TimesQuoted: Michele Wilson wooden jigsaw puzzles are handcut along color lines by highly qualified artisans. This gives the amateur even more difficulty and pleasure in building the jigsaw puzzle. Once ready, the jigsaw puzzle is thus very decorative.
- mohit - Oct 22 20081 FaverViewed: 4 Times
- royleban - Sep 12 20081 FaverViewed: 4 Times
This does not make sense to me. If they allow relabeling and permutations, it seems to me that all Sudoku answer grids are the same, so the answer is 1.
If the question is how many different Sudoku puzzles there are, then there are a number of things they haven't stated. What is the range of the number of givens? Are there requirements on the givens? (like symmetry) As an example, take a Sudoku puzzle and add another given or a pair, for symmetry) and you have a new puzzle, albeit one with the same answer.
I can make some guesses as to all the things they're not stating, but any of my guesses lead me to the conclusion that the answer, if relabeling and permutations are allowed, is a lot lower, perhaps orders of magnitude lower, than they are suggesting.
I gotta say, I was a little surprised by the size of the number. I've looked at their paper and they use Burnside's lemma with some funny business regarding relabelling which I'm not sure I believe - I'll have to think about it a bit to convince myself.
However, even though my initial take was the same as yours - there's only one solution, that turns out not to be the case. And whether they're wrong or right, their heart is in the right place - i.e., they really are considering exactly what you or I would call all essentially different solutions as you can see by reading their paper at http://www.afjarvis.staff.shef.ac.uk/sudoku/russell_jarvis_spec2.pdf. Whether or not their fast play with relabelling is valid there definitely is more than one effectively different solution. For instance, the following solution grid:
123 | 456 | 789
456 | 789 | 123
789 | 123 | 456
---------------
234 | 567 | 891
567 | 891 | 234
891 | 234 | 567
---------------
345 | 678 | 912
678 | 912 | 345
912 | 345 | 678
has 147, 369 and 582 in some permutation for every vertical "mini-column" within a subsquare. Any symmetry/relabelling you apply will leave either all mini-rows or all mini-columns with identical sets in this way. This is most definitely not a characteristic of every sudoku solution so there is more than one solution after allowing for all symmetries and relabellings.
Given that, I find the number surprisingly large, but I'd have to think carefully to refute it. Incidentally, there is a good artilcle in this month's American Mathematical Monthly which describes various sudoku solution grids in terms of linear algebra over finite fields. That's where I found the reference for this web page.
@Roy - They are counting unique SOLUTIONS, not PUZZLES. I do think it's fair so say that re-labeling and row/column/block permutations are essentially just recasting the same Sudoku into another form.
The reason the answer isn't "1" - is that the perumutations that are allowed are quite limited - swapping whole rows (columns) within a block and swapping a whole row (column) of blocks. You can't reach arbitrary re-ordering of the elements of the grid with such a limited set of transformations.
@Mike - Also reflections, rotations and relabellings. But these are exactly the set of symmetries they are calling "equivalent" in the number they give. Whether the number is accurate is another question, but that's what it's purported to be.
Good explanation, Darrell. When I was in college (and two courses shy of a math major), I might have been able to follow their math. Now, I don't know if I could. It reminds me a bit of the mathematical papers around Rubik's cube back in the '70s and '80s. I could understand them then, but would probably struggle now.
Interestingly, this also explains a significant failure with some sudoku generators, which generate solutions by swapping rows and columns. It's fast and simple but will not generate all possibilities. My own generator uses a fairly complex random algorithm.
Well, I can't say that I'm not struggling with the article but even if I don't catch everything, there was some interesting stuff in the MAA article. There's a preprint on the web that I couldn't fave for some reason but sent to Mike. Google "Cameron sudoku" if you're interested (cameron as you might guess is noe of the authors).