| View previous topic :: View next topic |
| Author |
Message |
dcole
Guest
|
 Posted: Sat Nov 26, 2005 5:57 am Post subject: 9 X 9 |
 |
|
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
|
| Posted: Fri Dec 09, 2005 12:54 pm Post subject: |
|
|
| 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
|
| Posted: Fri Dec 09, 2005 2:20 pm Post subject: |
|
|
| 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 |
|
|
Guest
|
| Posted: Fri Dec 09, 2005 3:56 pm Post subject: |
|
|
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
|
| Posted: Fri Dec 09, 2005 4:56 pm Post subject: |
|
|
Any advances on 362880?
You can reach an even bigger number by clicking on 'more' in my previous post. |
|
| Back to top |
|
|
Guest
|
| Posted: Fri Dec 09, 2005 5:51 pm Post subject: |
|
|
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
|
| Posted: Fri Dec 09, 2005 7:46 pm Post subject: It's a lot more than 9!, Derek |
|
|
| 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 |
|
|
Guest
|
| Posted: Fri Dec 09, 2005 8:20 pm Post subject: |
|
|
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
|
| Posted: Fri Dec 09, 2005 9:26 pm Post subject: I'm not sure myself, but ... |
|
|
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 |
|
|
smith55js
Joined: 29 Nov 2005
Posts: 9
Location: Logan, UT
|
| Posted: Sat Dec 10, 2005 10:50 am Post subject: total possible sudoku grids |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Mon Dec 12, 2005 3:50 pm Post subject: The "proof" of 6,670,903,752,021,072,936,960 |
|
|
| 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 |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Mon Dec 12, 2005 5:18 pm Post subject: |
|
|
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 |
|
|
ritz
Guest
|
| Posted: Fri Dec 23, 2005 3:19 am Post subject: a |
|
|
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 |
|
|
|
|
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
