dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

mathematics of Su Doku

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Test
View previous topic :: View next topic  
Author Message
John Ruddock



Joined: 19 Oct 2005
Posts: 4

PostPosted: Wed Oct 19, 2005 7:57 pm    Post subject: mathematics of Su Doku Reply with quote

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
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Wed Oct 19, 2005 9:58 pm    Post subject: Answers to some of your questions Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Thu Oct 20, 2005 7:20 am    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Test All times are GMT
Page 1 of 1

 
Jump to:  
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