by dukuso » Mon Sep 26, 2005 5:21 am
Ed wrote:
>in an effort to understand why you are reporting conflicting
>results to those obtained by Frazer and me, I've been re-reading
>some old postings: (http://forum.enjoysudoku.com/viewtopic.php?t
>=44&start=267) absolutely ages ago dukuso wrote:
>>Let S be the collection of the 84 subsets of {1,..,9} of size 3.
>>Let T be the collection of the 4741632000 9-tupels (S1,..,S9)
>>with members from S such that
>>S1+S2+S3=S4+S5+S6=S7+S8+S9={1,2,3,4,5,6,7,8,9} ,
>>where "+" is set-union.
>>Let 2 members from T be equivalent if one can be obtained
>>from the other by one of the known obvious 6^4*9! operations.
>>Then we get the collection E of the known 44 minimal elements from T,
>>one from each equivalence class, called "the gang of the 44".
>>For M in T let C(M) be its equivalent representative in E.
>>For M in E let Z(M) be the size of its equivalence class.
>>For M in E let N(M) be the number of partial 3*9 sudoku grids
>>compatible with M with respect to the 6^9 operations
>>of permuting inside a column.
>>The 2*44 values of N(M),Z(M) are constant within one class and
>>can be calculated quickly.
>I started coding this up and got stuck trying to calculate the
>equivalence class sizes, Z(.), "quickly". My naive implementation
>looks like it will take hours to do the job. Do you have a quicker
>method and, if so, what is it?
probably - I don't remember. I think I used a slower method first too,
and only later, when I tried to estimate how fast the whole
6.67e21 calculation could be done, I re-estimated these older
tasks too. The resulting numbers however had been confirmed several
times and are likely correct.
I was pretty much convinced at that time (and still am)
that it can all be done in a few minutes.
>Also, I remain unclear about exactly which figures you are disputing.
>The post I quoted from above goes on to say Quote:
>>How can we calculate the total number of sudoku-classes
>>as defined by RedEd but discarding transposition
>>with this method ?
from this introduction you can conclude, that the following part was
a bit more speculative...
>>sum over all M in E,
>>over all (M,A,B) in U(M)
>>of Z(M)*Q(M)*Q(C(A))*Q(C(B))
>>gives 19859770556
>which is nearly double the 10945437157 that Frazer calculated.
I think,I wasn't claiming that this were the number of T-classes.
In fact, I think the factor of almost two can be explained
because I didn't consider permutation of the 2nd and 3rd bands.
Maybe I was hoping this gave a factor of exactly two or
that the difference-numbers could be identified as the counts
of some other class or such.
I wrote, how the number was obtained - but the exact interpretation
and implications for the classes was not so clear to me.
There could be some grids with certain "symmetries" which
disturb the calculation
>I can't believe this is correct, as it would say that, on average,
>a "random" grid is left essentially unchanged by 1.81 elements of
>the group; i.e. the identity element plus probably at least one other.
>Frazer's result, by contrast, says that there's roughly a 1 in 20000
>chance that a random grid will have a non-identity group action that
>leaves it essentially unchanged. To me, this feels far more likely.
Of course. It's pretty clear that the exact number of classes
is close to your 5e9.
See my other post, where I claim that there are exactly 829 grids,
(upto isomorphism) which are isomorphic to their transpose.
This calculation was independent of the one quoted above
and done months later.
>For similar reasons, I would be very suspicious of any figure that's
>very far from 6.67e21 / (3359232*9!) when transpositions are allowed
>(when, I claim, there are 5472730538 essentially-different grids).
>
>So ... which of these figures do you have alternative suggestions
>for now? (and what are they?)
>
>Ed.
we have 3 calculations whicht don't fit together:
(1) yours with the 5472730538 classes
(2) Frazer's with the number of T-classes
(3) mine with the exactly 829 T-invariant classes.
at least the calculations (2) and (3) were reported here
as "not too trustworthy" so to say. They could be wrong with
probability of 30% or such. I don't know in what probability
class you'd put (1) . Well, at least one of the three must be wrong...
I suggested to test my uploaded 829 grids by examining random sudoku-grids.
If there were 20000 invariant classes as suggested by Frazer,
based on his calculation and yours , then we should be able
to find some of them with random trials.
We should be able to find some which are not in my list of the 829.
Maybe we can even construct some T-invariant sudokus.
Maybe starting from a symmetric B1B2B3B4B7.
-Guenter
]