| View previous topic :: View next topic |
| Author |
Message |
John Ruddock
Joined: 19 Oct 2005
Posts: 4
|
 Posted: Wed Oct 19, 2005 7:57 pm Post subject: mathematics of Su Doku |
 |
|
I have read recently that there are 6 x 10 to the power 21 permutations of the Su Doku grid. Is this really right? I don't regard number transpositions as yielding a different puzzle i.e swapping a 1 for a 9 (and vice versa) throughout the solution and the starting grid essentially yields the same problem. This can be extended to row boxes and column boxes - essentially the same problem. Moving on transposing rows inside eack set of row boxes yields the same problem - likewise for columns.
So question - how many different grids are there really?
The whole thing fascinates me. What is the smallest number of filled grid entries that yields a soluble puzzle? Conversely, what is the largest number of grid entries that yields a completely insoluble puzzle?
Are all puzzles set by computer programmes or do people compile some of them - if so, how do they ensure there is an unambiguous solution?
Using the Times as an example - the Easy and Mild puzzles generally have many paths to the solution. The Difficult and Fiendish tend to have multiple paths until a single path stage. Has anyone compiled a puzzle that has a single path for as many entries as possible - what is the maximum length single entry path until multiplicity is inevitable?
John |
|
| Back to top |
|
 |
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Wed Oct 19, 2005 9:58 pm Post subject: Answers to some of your questions |
|
|
| John Ruddock wrote: | I have read recently that there are 6 x 10 to the power 21 permutations of the Su Doku grid. Is this really right? I don't regard number transpositions as yielding a different puzzle i.e swapping a 1 for a 9 (and vice versa) throughout the solution and the starting grid essentially yields the same problem. This can be extended to row boxes and column boxes - essentially the same problem. Moving on transposing rows inside eack set of row boxes yields the same problem - likewise for columns.
So question - how many different grids are there really? |
A good question, John. The Wikipedia article gives the total number of elemental grids as 6,670,903,752,021,072,936,960 = 9! × 2^13 × 3^4 × 27,704,267,971. Gordon Royle at the University of Western Australia gives the order of the symmetry group for Sudoku grids as 9! x 2^9 x 3^8. One would like to answer your question by dividing the first number by the second one. Unfortunately, the result is not an integer, leading me to suspect that one of the numbers (probably the first one) is wrong.
| John Ruddock wrote: | | The whole thing fascinates me. What is the smallest number of filled grid entries that yields a soluble puzzle? Conversely, what is the largest number of grid entries that yields a completely insoluble puzzle? |
Gordon Royle offers 24,620 examples of 17-clue Sudoku puzzles -- he claims that these are all distinct in the sense you are after, although how he made this determination is beyond me. If I understand the computations involved, he would have to compare the 24,620 examples pairwise (roughly 300 million pairs) and he would have to run through all 9! x 2^9 x 3^8 (roughly a trillion) permutations for one of the items in every pair. That works out to something like 3 x 10^20 comparisons, which strikes me as an awful lot. Maybe he had a better way to do it.
So far as I'm aware, nobody has yet constructed a 16-clue Sudoku puzzle, but there is no proof that such a thing is impossible. The idea that at least 17 clues are required to give a unique solution is plausible -- imagine a 9x9 grid with the 17 clues aligned along the top row, and in the first column. The idea that the values in the remaining 64 cells can be fixed by these "boundary values," but that a lesser number of "boundary values" won't work, is intuitively appealing.
I'm not sure I understand your second question. I can construct an "insoluble" puzzle with just two numbers in it -- say two "1"s in the first two cells. If you mean what's the largest number of cells that can be filled in without actually displaying an explicit violation of the rules, I think that number is 79 -- I've seen erroneous "solutions" that have just one column and one row left incomplete, with no way to fill in either of the last two numbers without making the contradiction apparent.
| John Ruddock wrote: | | Are all puzzles set by computer programmes or do people compile some of them - if so, how do they ensure there is an unambiguous solution? |
According to the Wikipedia article, a few puzzles are still set by hand. I imagine the author ensures a unique solution by starting from the answer grid and working backwards to the published version of the puzzle.
| John Ruddock wrote: | | Using the Times as an example - the Easy and Mild puzzles generally have many paths to the solution. The Difficult and Fiendish tend to have multiple paths until a single path stage. Has anyone compiled a puzzle that has a single path for as many entries as possible - what is the maximum length single entry path until multiplicity is inevitable? |
I don't have any idea. I have seen a couple of puzzles where the first three or four moves seem to be forced, but they don't necessarily have to be done in a particular order. As for critical spots near the middle of the puzzle (with say 30 to 40 cells still unresolved), most of those seem to boil down to a single critical move, and once that's been found a lot of different numbers pop out all at once, creating multiple solution pathways. dcb |
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Thu Oct 20, 2005 7:20 am Post subject: |
|
|
You put it very well in words, David.
That is also (approximate) my understanding.
P.S. I "downloaded" the 17 cells Sudokus. They are a real source of inspiration, except that they are not symetric.
ONE MORE POINT: Be aware that there are a couple of internat pages with Sudoku problems that DO NOT HAVE UNIQUE solutions!
The authors are using "quick and durty" programs to generate them and smashing them on to the public.
They do NOT even warn you that their puzzels does NOT have a unique solution.
The WHOLE fun is in the UNIQUE SOLUTION, but if the author NOTIFIES us that he is not GARANTING one, than it is OK with me, I will not even start to look at his one.
see u, |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
