View previous topic :: View next topic 
Author 
Message 
 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

Posted: Fri Aug 26, 2005 8:51 am Post subject: how many sudokugrids 


there are 6670903752021072936960 sudokugrids from
5472730538 equivalence classes ("Sclasses")
where grids are Sequivalent, if they can be transformed into
each other by
permuting symbols
permuting the 3 rows in some stack
permuting the 3 columns in some band
permuting the 3 stacks
permuting the 3 bands
transposing
these 6 groups of transformations do commute and give
9!*6^8*2 transformations in total.
When we omit transposition, we get 10945437157 "Tclasses",
23919 Sclasses have only 1 Tclass, the other Sclasses
have 2 Tclasses.
there are only 306693 classes ("Gclasses"), when we also allow
permuting the 3 entries in any minicolumn but remove transposition.
These 306693 classes generate 11555445688 sudokugrids,
by permuting minicolumns modulo permuting rows in a band,
at least one from each Sclass. They can be generated in about
5 hours but storing them requires too much memory.
Many sudokuproperties are an invariant of the Sclass and thus
an invariant of the Tclass and some can be checked by checking
these 11555445688 generated sudokus.
10895 ordered 3tuples of "gangsters" from the "gang of the 44"
occur in sudokugrids.
Between 1 and 985 Gclassrepresentatives
correspond to one such triple. Many triples have just only a few
Gclass members  half of them less than 10.
Most (985) "belong" to the triple (18,35,37).
Remember, these 18,35,37 were among the most
frequent in random sudokus and in Gordon's 17s.
(planning to fill in the missing numbers and some updates later...)
edited 17.Oct.2005
Last edited by dukuso on Mon Oct 17, 2005 3:40 pm; edited 2 times in total 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Fri Aug 26, 2005 11:40 am Post subject: 


Excellent Post
I have deleted my post  so as not to confuse !
Colin
Last edited by coloin on Fri Aug 26, 2005 10:25 pm; edited 1 time in total 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

Posted: Fri Aug 26, 2005 2:18 pm Post subject: 


a property like admitting a 16cluesudoku
is not an invariant of the Gclass, but of the Sclass.
So one representative from a Gclass may admit a 16sudoku
and another one not.
Last edited by dukuso on Mon Oct 17, 2005 3:44 pm; edited 1 time in total 

Back to top 


 Ulisse
 Joined: 02 Sep 2005  Posts: 2  :  Location: Italy  Items 

Posted: Fri Sep 02, 2005 5:51 pm Post subject: Re: how many sudokugrids 


dukuso wrote:  there are 6670903752021072936960 sudokugrids from
5472730538 equivalence classes ("Sclasses") (...omissis...) 
Hi! i would like to learn more about the math aspects of Sudoku. In particular i would like to know the theoretical aspects of your calculation.
If available could you please link me to papers/articles/webpages that explain the formulas you used to calculate the cardinality of the solutions set?
Thank you very much! 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 


Back to top 


 Ulisse
 Joined: 02 Sep 2005  Posts: 2  :  Location: Italy  Items 

Posted: Sat Sep 03, 2005 10:04 am Post subject: 


Wow!
This is what i was looking for!
Thank you very much indeed!
Obviously i see only now that you already posted some links in an other 3d ... sorry... 

Back to top 


 frazer
 Joined: 06 May 2005  Posts: 8  :   Items 

Posted: Mon Sep 05, 2005 11:52 am Post subject: 


For Ulisse: there will be a new updated version of the article coming very soon, also containing details of the computation of the number of essentially different grids.
For dukuso: I'll think about the Tclass calculation too. The group formed by omitting transposition, although half the size of the full group, has nearly twice as many conjugacy classes (484 rather than 275). For each representative, we have to count the number of fixed points. Since we already know Ed's results for all the elements of the full group, this should be easy, in principle  it's just a matter of working out, for each of the 484 elements, which conjugacy class of the full group it belongs to, and using Ed's result. In practice, this could take a long time, unless I can work out how to automate the calculation... 

Back to top 


 frazer
 Joined: 06 May 2005  Posts: 8  :   Items 

Posted: Wed Sep 07, 2005 2:00 pm Post subject: 


OK. I've done the Tclass calculation, after working out how to write a little program in GAP. I'll add the GAP output to the webpage.
The calculation was done in the same way as for the Sclasses; namely, to average (over the group) the number of fixed grids up to relabelling. As I mentioned before, the Tgroup has 484 conjugacy classes, and it's just a question of working out which correspond to Sclasses with fixed grids (there are 41 such classes). One then uses Ed's calculation of the number of fixed grids for each Sclass. The final result is that there are 10945437157 Tclasses. This means that 23919 Sclasses have only 1 Tclass, and the other 5472706619 have 2 Tclasses.
In the event the calculation was rather easy  sorry to dukuso for not doing it earlier, as it's been some weeks since he first asked it... 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

Posted: Wed Sep 07, 2005 2:52 pm Post subject: 


thanks Frazer.
Now I'll have to check that with my old calculations and files.
But I'm not optimistic. I think I had another number.
My calculation was very vague AFAIR so don't be afraid
too much that yours could be wrong.
Do you have a file with those 23919 ?
Guenter. 

Back to top 


 frazer
 Joined: 06 May 2005  Posts: 8  :   Items 

Posted: Wed Sep 07, 2005 3:23 pm Post subject: 


It's entirely possible that there are errors; the numbers originally due to Ed have been transcribed several times from one place to another before going into the calculation giving that final answer of my last message. I'm sure that the method is fine, so any errors are either in Ed's numbers or subsequent transcriptions. There is no file with the 23919  it's just the difference between 2*Sclasses and Tclasses, both of which were enumerated entirely nonconstructively. (On the other hand, some very mild evidence for the answers is that both worked out to be integers, which would not be likely  but of course possible  if there were errors.) 

Back to top 


 dukuso
 Joined: 14 Jul 2005  Posts: 424  :  Location: germany  Items 

Posted: Thu Sep 08, 2005 6:12 am Post subject: 


walking throught the 11555445688 sudokus, which by design
should intersect each Sclass at least once, I found indeed
23919 Tclasses which are Tequivalent to their transpose.
The list is here:
http://magictour.free.fr/tinvar.gz
edited 17.Oct. My earlier calculation of 819 tinvariant classes
was wrong. 

Back to top 


