3 ms·
The OP says there are 6x10^21 Sudoku puzzles. If we remove rotations and reflections, there may be (far) fewer unique Sudoku puzzles than we think. In fact, th
by JoeAltmaier 6y ago
The OP says there are 6x10^21 Sudoku puzzles.
If we remove rotations and reflections, there may be (far) fewer unique Sudoku puzzles than we think. In fact, there are many sub-reflections that are essentially the 'same' puzzle:
Take the first three rows as a block, 'rotate' to the bottom of the puzzle - its still 'solved'. In fact permute the blocks of three rows in any order, still the 'same' puzzle in a sense.
Same with the first three columns.
Same with the three rows or columns in a block of three - permute them, the solution is 'unchanged'.
Relabel the digits from 1-9 as 9-1 - another 'reflection' which is the same puzzle pattern.
In fact, permute the digits all different ways - its still solved.
I'm not at all sure there isn't actually just one unique pattern to sudoku. But I don't know how to prove that one way or another.
- jepler 6y agohttps://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_Sudoku_solutions https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerat... I believe these ways of relabeling you mention are all taken into account when numbering the "essentially different" puzzle configurations.
- niftich 6y agoIn 2005, Ed Russell and Frazer Jarvis calculated 5,472,730,538 "essentially different" 9x9 grids [1][2], once they've excluded valid grids that can be derived from another valid grid using relabelling, various permutations, reflection, rotation, etc. [1] http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html [2] (PDF) http://www.afjarvis.staff.shef.ac.uk/sudoku/russell_jarvis_spec2.pdf http://www.afjarvis.staff.shef.ac.uk/sudoku/russell_jarvis_s...
- JoeAltmaier 6y agoOK I read that -very interesting! And now I'm positive I don't know how to prove it myself. Luckily there are smarter people who can address problems like this. Thanks for the link!
- ynik 6y agoWith the extra constraints in this Sudoku variant, there can't be many unique solutions -- otherwise two numbers wouldn't be sufficient to uniquely specify a solution. In fact, there's only a single pattern. Note how along one axis every digit is 4 higher (mod 9) than the previous digit. One starting digit specifies the starting point (alignment of the pattern), the other starting digit the rotation + mirroring of the pattern. 9 possible alignments times 4 rotations times 2 (mirrored or not) = 9 * 4 * 2 = the 72 different solutions mentioned in the article. But this is caused by the Knight's+King's move constraints (with the "consecutive numbers" constraint prohibiting relabeling of the numbers). There's way more solutions without those extra constraints.
- fsckboy 6y agoyes, the number is greatly reduced, but you're leaving out a source of more variation. A sudoku puzzle not the solution, it's the constrained choice of what is shown vs hidden in the initial state. One solution could be parent to a number of solvable puzzles of varying difficulty.