how many sudoku-grids

dukuso · Posted: Fri Aug 26, 2005 8:51 am Post subject: how many sudoku-grids

there are 6670903752021072936960 sudokugrids from
5472730538 equivalence classes ("S-classes")

where grids are S-equivalent, 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 "T-classes",
23919 S-classes have only 1 T-class, the other S-classes
have 2 T-classes.

there are only 306693 classes ("G-classes"), 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 S-class. They can be generated in about
5 hours but storing them requires too much memory.

Many sudoku-properties are an invariant of the S-class and thus
an invariant of the T-class and some can be checked by checking
these 11555445688 generated sudokus.

10895 ordered 3-tuples of "gangsters" from the "gang of the 44"
occur in sudokugrids.
Between 1 and 985 G-class-representatives
correspond to one such triple. Many triples have just only a few
G-class 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

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

Excellent Post

I have deleted my post - so as not to confuse !

Colin

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

a property like admitting a 16-clue-sudoku
is not an invariant of the G-class, but of the S-class.
So one representative from a G-class may admit a 16-sudoku
and another one not.

Ulisse · Posted: Fri Sep 02, 2005 5:51 pm Post subject: Re: how many sudoku-grids

dukuso · Posted: Sat Sep 03, 2005 6:35 am Post subject: Re: how many sudoku-grids

Ulisse · 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... Embarassed

frazer · 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 T-class 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...

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

OK. I've done the T-class 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 S-classes; namely, to average (over the group) the number of fixed grids up to relabelling. As I mentioned before, the T-group has 484 conjugacy classes, and it's just a question of working out which correspond to S-classes with fixed grids (there are 41 such classes). One then uses Ed's calculation of the number of fixed grids for each S-class. The final result is that there are 10945437157 T-classes. This means that 23919 S-classes have only 1 T-class, and the other 5472706619 have 2 T-classes.

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...

dukuso · 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.

frazer · 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*S-classes and T-classes, 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.)

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

walking throught the 11555445688 sudokus, which by design
should intersect each S-class at least once, I found indeed
23919 T-classes which are T-equivalent to their transpose.
The list is here:
http://magictour.free.fr/t-invar.gz

edited 17.Oct. My earlier calculation of 819 t-invariant classes
was wrong.