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 

9 X 9

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion
View previous topic :: View next topic  
Author Message
dcole
Guest





PostPosted: Sat Nov 26, 2005 5:57 am    Post subject: 9 X 9 Reply with quote

I was done the math and have found the 9 X 9 to have 201 ways the numbers can be arranged.

Is this right? If not, I will register and post a pic of the math
Back to top
Guest






PostPosted: Fri Dec 09, 2005 12:54 pm    Post subject: Reply with quote

there are actually 6561 different ways to arange the numbers. you multiply 81 * 81.
Back to top
dotdot



Joined: 07 Dec 2005
Posts: 29
Location: oberseen

PostPosted: Fri Dec 09, 2005 2:20 pm    Post subject: Reply with quote

Anonymous wrote:
there are actually 6561 different ways to arange the numbers. you multiply 81 * 81.


Some might have learnt the 201 by heart, but 6561 is discouraging.
It is a lot more than that.
Back to top
View user's profile Send private message
Guest






PostPosted: Fri Dec 09, 2005 3:56 pm    Post subject: Reply with quote

If you think about it, we only need to work out the number of ways that 9 numbers can be re-arrange in a row (let say row1) because the rest of the numbers are dictated by the numbers in row 1.

Therefore there are actually, in maths term, 9 factorial ways or
9!= 9x8x7x....x2x1=362880 ways to arrange the numbers in a 9x9 grid.

Cheers
Derek.
Back to top
dotdot



Joined: 07 Dec 2005
Posts: 29
Location: oberseen

PostPosted: Fri Dec 09, 2005 4:56 pm    Post subject: Reply with quote

Any advances on 362880?

You can reach an even bigger number by clicking on 'more' in my previous post.
Back to top
View user's profile Send private message
Guest






PostPosted: Fri Dec 09, 2005 5:51 pm    Post subject: Reply with quote

Dotdot, thanks for pointing out the link but despite reading the article I still think the answer is 9!
Sorry to have sounded a bit stubborn but they did admit in the article that there were duplications!
Simple check is if you try out a 2x2, 3x3 or 4x4... you will get 2!, 3! or 4! respectively. ie. 2 ways for 2x2 grid, 6 ways for a 3x3, 24 ways for 4x4 and so on...9! for a 9x9.

Derek.
Back to top
David Bryant



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

PostPosted: Fri Dec 09, 2005 7:46 pm    Post subject: It's a lot more than 9!, Derek Reply with quote

Derek wrote:
If you think about it, we only need to work out the number of ways that 9 numbers can be re-arrange in a row (let say row1) because the rest of the numbers are dictated by the numbers in row 1.

OK, Derek, since all the rest of the 72 cells are dictated by the values in the first row, what is the unique solution to this sample Sudoku puzzle?
Code:
123 456 789
... ... ...
... ... ...

... ... ...
... ... ...
... ... ...

... ... ...
... ... ...
... ... ...


Please let me know -- I'll bet the answer is not unique. dcb

PS If you're really interested, Gordon Royle's web site has a good explanation of why the symmetry group associated with a single Sudoku solution is of order 9! * 2 * 6^8 = 1,218,998,108,160. In other words, given a single Sudoku solution, I can find 1,218,998,108,159 more and different solutions (different in the sense that, if one were to write each one out as an 81 digit number, all those numbers would be different) by performing the group operations on the starting grid.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Guest






PostPosted: Fri Dec 09, 2005 8:20 pm    Post subject: Reply with quote

David,

Silly me! Thanks for pointing this out. Now I knew that 9! can't be right but what is the right answer?
Is 9! * 2 * 6^8 = 1,218,998,108,160 quoted in your post correct or 6,670,903,752,021,072,936,960 quoted in dotdot's post correct? or neither?

Interesting! I will spend sometimes on these ..........

Derek.
Back to top
David Bryant



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

PostPosted: Fri Dec 09, 2005 9:26 pm    Post subject: I'm not sure myself, but ... Reply with quote

Hi, Derek!

I'm not sure that the big number (6,670,...) is correct. The other number I quoted (9! * 2 * 6^8) is not supposed to be the number of valid Sudoku solutions there are -- it's the number of ways a given Sudoku grid can be transformed by permuting the digits, or the columns within a 9x3 band, or the rows within a 3x9 band, etc. Notice that not every starting grid will give 1,218,998,108,160 distinct solutions when the symmetry operations are applied to it -- the starting grid may have some symmetrical features, so that it is its own mirror image, for instance. In any event, I'm sure the total number of Soduko grids is a very big number -- more like 10^20 or 10^21 than like 10^6, or even 10^12.

Derek wrote:
Simple check is if you try out a 2x2, 3x3 or 4x4... you will get 2!, 3! or 4! respectively. ie. 2 ways for 2x2 grid, 6 ways for a 3x3, 24 ways for 4x4 and so on...9! for a 9x9.

OK, we already know this is wrong, but the 4x4 example is instructive, since it can be subdivided into 4 2x2 boxes, like a baby Sudoku. Here are all (I'm pretty sure it's all) the 4x4 grids that can be constructed with "1" in row 1, column 1.
Code:
12 34   13 24   12 43   13 42   14 23   14 32
34 12   24 13   43 12   42 13   23 14   32 14
23 41   32 41   24 31   34 21   42 31   43 21
41 23   41 32   31 24   21 34   31 42   21 43

12 34   13 24   12 43   13 42   14 23   14 32
43 12   42 13   34 12   24 13   32 14   23 14
21 43   31 42   21 34   31 24   41 32   41 23
34 21   24 31   43 21   42 31   23 41   32 41

12 34   13 24   12 43   13 42   14 23   14 32
34 21   24 31   43 21   42 31   23 41   32 41
21 43   31 42   21 34   31 24   41 32   41 23
43 12   42 13   34 12   24 13   32 14   23 14

12 34   13 24   12 43   13 42   14 23   14 32
43 21   42 31   34 21   24 31   32 41   23 41
21 43   31 42   21 34   31 24   41 32   41 23
34 12   24 13   43 12   42 13   23 14   32 14

12 34   13 24   12 43   13 42   14 23   14 32
34 12   24 13   43 12   42 13   23 14   32 14
41 23   41 32   31 24   21 34   31 42   21 43
23 41   32 41   24 31   34 21   42 31   43 21

12 34   13 24   12 43   13 42   14 23   14 32
43 12   42 13   34 12   24 13   32 14   23 14
34 21   24 31   43 21   42 31   23 41   32 41
21 43   31 42   21 34   31 24   41 32   41 23

12 34   13 24   12 43   13 42   14 23   14 32
34 21   24 31   43 21   42 31   23 41   32 41
43 12   42 13   34 12   24 13   32 14   23 14
21 43   31 42   21 34   31 24   41 32   41 23

12 34   13 24   12 43   13 42   14 23   14 32
43 21   42 31   34 21   24 31   32 41   23 41
34 12   24 13   43 12   42 13   23 14   32 14
21 43   31 42   21 34   31 24   41 32   41 23


Here are the same 48 grids, presented in the form of 16-digit numbers (these are just the grids shown above, read from left to right and from top to bottom, then written out as one line).
Code:
1234341223414123   1324241332414132   1243431224313124
1342421334212134   1423231442313142   1432321443212143
1234431221433421   1324421331422431   1243341221344321
1342241331244231   1423321441322341   1432231441233241
1234342121434312   1324243131424213   1243432121343412
1342423131242413   1423234141323214   1432324141232314
1234432121433412   1324423131422413   1243342121344312
1342243131244213   1423324141322314   1432234141233214
1234341241232341   1324241341323241   1243431231242431
1342421321343421   1423231431424231   1432321421434321
1234431234212143   1324421324313142   1243341243212134
1342241342313124   1423321423414132   1432231432414123
1234342143122143   1324243142133142   1243432134122134
1342423124133124   1423234132144132   1432324123144123
1234432134122143   1324423124133142   1243342143122134
1342243142133124   1423324123144132   1432234132144123

Clearly we can create 144 more of these by simply "rotating" the digits (eg, by writing 2 for 1, 3 for 2, 4 for 3, and 1 for 4) until we've run through 48 more with "2" as the first digit, then 48 more with "3" appearing first, etc. I'm pretty sure that if we make more general permutations on the digits we'll start generating duplicates. So I think there are exactly 192 4x4 mini-sudoku grids -- that' 8 * 4! dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
smith55js



Joined: 29 Nov 2005
Posts: 9
Location: Logan, UT

PostPosted: Sat Dec 10, 2005 10:50 am    Post subject: total possible sudoku grids Reply with quote

I ran across an interesting mathematical proof. It does require a bit of advanced understanding of math to follow along, but the number reached is quite large.

http://www.shef.ac.uk/~pm1afj/sudoku/sudoku.pdf
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Mon Dec 12, 2005 3:50 pm    Post subject: The "proof" of 6,670,903,752,021,072,936,960 Reply with quote

Jake Smith wrote:
I ran across an interesting mathematical proof. It does require a bit of advanced understanding of math to follow along, but the number reached is quite large.

Thanks for the link, Jake. It's an interesting paper. But I wouldn't quite call it a "proof." Maybe "demonstration" is a better word.

I might be a bit too picky, but it seems to me that a real "proof" ought to include a description of all the logical steps in enough detail that the reader can verify, in his own mind, that the conclusion reached is true, given the definitions and assumptions.

The paper is excellent, but the detailed description of how the 71 (subsequently 44) equivalence classes were determined has largely been omitted. I suppose one could work this out for oneself, but it would probably take more time than I care to devote to it. (To be fair to the authors, the details of such a demonstration would increase the size of the paper quite a lot, and make it much less fun to read.)

The other point that one might verify (if one had the time) is the correctness of the computer programs used to make the final counts over blocks 5, 6, 8, & 9. Fortunately the authors used two different approaches themselves, and received independent verification of their results from a third source, so the computer programs are either error-free, or else all three contain the same bug (and that seems highly unlikely). Still, there's the philosophical question -- is a computer program a "proof"?

I'm curious -- what's your opinion of the "proof" of the Four-Color Theorem? 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: Mon Dec 12, 2005 5:18 pm    Post subject: Reply with quote

Hi David,

For me, if the algorithm and the source programs together with the running job are presented, it is part of the demonstration and it we can follow it. So, it is acceptable for me.
Same with the 4 color problem. Parts are done by computer programs which, at the end, are only extensions of our thinking.

see u,
Back to top
View user's profile Send private message
ritz
Guest





PostPosted: Fri Dec 23, 2005 3:19 am    Post subject: a Reply with quote

hey, im not exactly a mathematical whiz. im 17 and i barely made it through my 11th grade math class lol. anyway, the way i thought about it, there should be 3265920. the way i looked at it, one row of cells across, is 9!.

basically, if u look at in horizontal rows, the first box, has 9 possibilies, the second, 8, third 7, so on and so forth, hence the 9!

then, there are 9 rows of this, which would make it 9! (9).

i think that would cover everything, because, even though the verticle rows, are also 9!, i think multiplying across already has each accounted for. but if im wrong there, then i figure it would be, that same 9! (9) for the verticle rows, which would in essense be the original number squared, so 10666233446400.

i have no idea if any of this is even close to being right, seems logical to me. its prolly wrong, but maybe itll give one of you real math whizzes something to think about
Back to top
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion 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