The New Sudoku Players' Forum

[kjellfp]

Could you possibly post the grids from 27 up?

I have had this list for one year now. See here. But not with a min-lex grid for each class, as I used a very different ordering of the grids.

[gsf]

the number of automorphisms for any grid is in the range 1..648 inclusive
do we know the impossible ones (number of automorphisms) in that range?

having the catalog in hand is ... handy
here is a table of #autmorphisms and #essentially-different-grids with that number of automorphisms

Code: Select all

   1 5472170387
   2     548449
   3       7336
   4       2826
   6       1257
   8         29
   9         42
  12         92
  18         85
  27          2
  36         15
  54         11
  72          2
 108          3
 162          1
 648          1


You might have seen my post from November 2005 which leads to the same list as yours.

can you show the mapping between your list and the above?
e.g., how does your list show that there is only one grid up to isomorphism with 648 automorphsims?

I see by the way that you have created the grids in compressed form. I think it should be possible with i little bit more than 2 bits/grid (uncomporessed, but I don't think compression will be significant), but I don't know how fast you expect the program that gets the grid to be. And you can't have the grids ordered in whatever way you like - actually they are forced in a very rigid order.

are you describing a way to represent all grids or just the essentially different grids?

[kjellfp]

can you show the mapping between your list and the above?
e.g., how does your list show that there is only one grid up to isomorphism with 648 automorphsims?

The intention of my list was to confirm the number of essentially different grids, both when grids where identified with their transpose (the 5.5e9 S-classes), and when they were not (the 1.1e9 T-classes). That's why I have three, rather than two, columns.

If, in my list, we let X(N) be the number of T-classes with automorphism group size N that are not transpose invariant, and Y(N) those that are, then the number of classes of N automorphisms (the numbers in your list) will be:

Code: Select all

Z(N) = X(N)/2  {non-transpose invariant grids come in pairs, a class and its transpose}
     + Y(N/2)  {transpose-invariant grids have extra automorphisms by transposing}

The Y-term only applies when N is even.
Examples from your list:

Z(648) = X(648)/2 + Y(324) = 0+1 = 1
Z(108) = X(108)/2 + Y(54) = 4/2 + 1 = 3
Z(27) = X(27)/2 = 4/2 = 2 (no Y-term, 27 is odd)
Z(2) = X(2)/2 + Y(1) = 1050496/2 + 23201 = 548449

are you describing a way to represent all grids or just the essentially different grids?

Essentially different.

[kjellfp]

Just another thing to think about.

Some are talking about creating the entire list of essentially different grids in some compressed form, and distributing it for downloading.

But actually, what is the fastest? Downloading the several-Gb-file, or generating it?

Just a thought. I generated my list in 2005 in about 10 hours, my code then was very slow. It can be done much, much faster!

[udosuk]

But actually, what is the fastest? Downloading the several-Gb-file, or generating it?

Yes great idea... Instead of uploading the multi-GB catalogue file, why not write a program which would generate the file in anyone's computer, provided there is available space in the hard drive?

[gsf]

here is a table of #autmorphisms and #essentially-different-grids with that number of automorphisms

Nice! That confirms the number 6670903752021072936960 once again. Could you possibly post the grids from 27 up? Actually, maybe there should be an own thread for "the catalogue". I suspect this is otherwise going to drift very much off topic.

here are the 27 and up grids with #automorphisms, band, and minlex index

123456789456789123789123456231564897564897231897231564312645978645978312978312645 # 648 001 964550
123456789456789123789123456231564897564897231897231564312978645645312978978645312 # 108 001 964558
123456789456789123789123456231564897564897231897231564348672915672915348915348672 # 54 001 964568
123456789456789123789123456231564897564897231897231564348915672672348915915672348 # 54 001 964569
123456789456789123789123456231564897564897231978312645312645978645978312897231564 # 36 001 964589
123456789456789123789123456231564978564897312897231645312978564645312897978645231 # 72 001 965096
123456789456789123789123456231564978564978231978231564312645897645897312897312645 # 108 001 965174
123456789456789123789123456231564978564978231978231564312897645645312897897645312 # 36 001 965182
123456789456789123789123456231564978645897231897312564312645897564978312978231645 # 36 001 966422
123456789456789123789123456231597864597864231864231597312678945678945312945312678 # 36 001 985543
123456789456789123789123456231597864597864231864231597312948675675312948948675312 # 36 001 985544
123456789456789123789123456231678945678945231945231678312597864597864312864312597 # 36 001 989378
123456789456789123789123456231678945678945231945231678312894567567312894894567312 # 36 001 989379
123456789456789123789123456231897564564231897897564231348672915672915348915348672 # 27 001 989400
123456789456789123789123456231897564564231897978645312312978645645312978897564231 # 36 001 989404
123456789456789123789123456231897645564312897978564231312978564645231978897645312 # 36 001 989622
123456789456789123789123456234567891567891234891234567318642975642975318975318642 # 54 001 992761
123456789456789123789123456234567891567891234891234567345678912678912345912345678 # 54 001 992769
123456789456789123789123456234567891567891234891234567372615948615948372948372615 # 54 001 992773
123456789456789123789123456235964817817235964964817235392641578578392641641578392 # 54 001 1006748
123456789456789123789123456267591348591834672834267915375618294618942537942375861 # 54 001 1007164
123456789456789123789123456267591834591834267834267591375618942618942375942375618 # 162 001 1007168
123456789456789123789123456267591834591834267834267591375942618618375942942618375 # 54 001 1007169
123456789456789123789132465231564978564978231978213546312645897645897312897321654 # 36 004 50092115
123456789456789123798132465231564897564897231879213546312645978645978312987321654 # 36 009 224283635
123456789456789123897231564231564978564978231789312645312645897645897312978123456 # 54 016 473714886
123456789456789231789123645231564897564897312897231456375618924618942573942375168 # 36 027 1012364857
123456789456789231789123645231564978564897123897231564375942816618375492942618357 # 36 027 1012366524
123456789456789231789312456231564978564978312978123564312645897645897123897231645 # 27 030 1061944621
123456789456789231789312456231645978645978312978123645312564897564897123897231564 # 54 030 1062073983
123456789457189236968372514291738465374265198685941327546813972732694851819527643 # 36 133 4869572229
123456789457189326869372514214965873635847192978213465381624957546798231792531648 # 36 240 5449015463
123456789457289163689173452235964817816735924974812635392641578568397241741528396 # 54 348 5472677656
123456789457289163689173452245968317316745928978312645564897231731524896892631574 # 108 348 5472677695
123456789457893612986217354274538196531964827698721435342685971715349268869172543 # 72 416 5472730538

[gsf]

Just another thing to think about.

Some are talking about creating the entire list of essentially different grids in some compressed form, and distributing it for downloading.

But actually, what is the fastest? Downloading the several-Gb-file, or generating it?

Just a thought. I generated my list in 2005 in about 10 hours, my code then was very slow. It can be done much, much faster!

until your reminder the thread (or at least I) wasn't aware that an essentially different catalog had been generated

the inner loop of your method uses gangster indices
how does it differentiate between grids that have the same indices?

[JPF]

irrelevant, deleted.

[kjellfp]

the inner loop of your method uses gangster indices
how does it differentiate between grids that have the same indices?

Gangster indices are not used to uniquely determine the grids (not even the 416-index is sufficient). They are used to get early cuts in the search three.

If it will be of any interrest, this is the algorithm more in details:

Every band B has a gangster index g(B) from 1 to 44 and a band index h(B) from 1 to 416. The gangster index can also be lifted to give the index g(C) of a band column configuration C. The band indexing is arranged such that if g(B1)<g(B2) then h(B1)<h(B2).

Loop 1 (the outermost): Run through the 416 unique choices for B1 (the first band), in the h-order (and so also in a never-descending g-order).

Loop 2,3,4 (with the first band chosen): Run through the 56*56*56 choices for the column configuration C2 of band 2, this also gives the configuration C3 of band 3. Cut the branch if not g(B1) <= g(C2) <= g(C3).

Loop 5: Run through the ways to permute the columns of C2 to get a legal Sudoku band B2. Cut the branch if h(B2) < h(B1).

Loop 6: Do the same as for loop 3 on C3 to get a legal Sudoku band B3. Cut the branch if h(B3) < h(B2).

Now we have a candidate for a class. In most cases, the automorphism group is trivial, and easy to know being trivial (for example if the automorphism group of any of the bands is trivial and h(B1) < h(B2) < h(B3)), while in some cases, we need to run through the possible automorphisms of the first band, and/or permutations of the bands, to see if this class has already been represented. This process will also be used to get the actual size of the automorphism group of the entire grid.

We will also have to check if transposing the grid gives an earlier representative.

With all tests above passed, we have a new class.

[gsf]

Now we have a candidate for a class. In most cases, the automorphism group is trivial, and easy to know being trivial (for example if the automorphism group of any of the bands is trivial and h(B1) < h(B2) < h(B3)), while in some cases, we need to run through the possible automorphisms of the first band, and/or permutations of the bands, to see if this class has already been represented. This process will also be used to get the actual size of the automorphism group of the entire grid.

thanks
to see if this class has already been represented
what is the operation here?
just checking against the current class or some number of already generated classes?

[kjellfp]

to see if this class has already been represented

I see this was a very misleading formulation. It's obvious also that when I wrote this, I didn't remeber excatly how I actually implemented it one year ago.

Every T-class has a subset of grids G_1, G_2, ..., G_N with the properties that

* The bands B1, B2, B3 or in h-order, i.e. h(B1)<=h(B2)<=h(B3).
* The first band, B1, is the cannonical representative for it's h-number (the min-lex for some lexiographical order)

In the 6-loop algorithm I have explained above, each of these G_i will be visited once in the innermost loop. Once I have a G_i, I can run through all possible operations (this is easy to keep track of) which sends it to any G_k. This way, I can find both all the other G_k as well as the automorphism group size of the grid itself.

If I transform G_i to a G_k that comes lexiographically (for some convenient ordering I define, how is not important) before G_i, I move on. Only when my G_i is the lexiographically first, I recognize it as a new class.

So saying that the class has already been represented is wrong. It might happen that the lexiographically first G_i is not the cronologically first to be visited. The only important point is that I have a tool for ensuring that every class is visited exactly once.

(In most cases however, there is no non-trivial operation sending my G_i to some G_k. Then N=1, G_i is the class representative, and the gird automorphism group is trivial.)

[udosuk]

here is a table of #autmorphisms and #essentially-different-grids with that number of automorphisms

Code: Select all

   1 5472170387
   2     548449
   3       7336
   4       2826
   6       1257
   8         29
   9         42
  12         92
  18         85
  27          2
  36         15
  54         11
  72          2
 108          3
 162          1
 648          1

Thanks for posting the grids from 27 up!

For completeness sake, I'm sure you can pack the grids of 8,9,12,18 to a file of ~20kB, and the grids of 3,4,6 to a file of ~1MB, which could be compressed considerably... The grids of 2 should occupy about 43MB, and after compression should be much less (a few MBs?)... Of course, all these could be relatively easily uploaded to a free hosting site such as www.badongo.com ...

[coloin]

You might have seen my post from November 2005 which leads to the same list as yours.

Thanks for your work, and i am sure that generating the list will be very much quicker with your programming.

But more thanks to gsf for spelling out the number of automorph grids.

From your post.....

Code: Select all

N   | Classes [G] where #K(G)=N
    +-------------+------------
    | not trans.- | transpose-
    | invariant   | invariant
----+-------------+------------
  1 | 10944340774 | 23201
  2 |     1050496 |   637
  3 |       14672 |    36
  4 |        4378 |    29
  6 |        2442 |     6
  9 |          84 |     1
 12 |         172 |     0
 18 |         168 |     4
 27 |           4 |     1
 36 |          22 |     2
 54 |          20 |     1
108 |           4 |     0
162 |           2 |     0
324 |           0 |     1

This was your table - which quite frankly I couldnt comprehend at the time

So then this "leads to"

Code: Select all

Z(2) = X(2)/2 + Y(1) = 1050496/2 + 23201 = 548449

"therefore" the number of grids with automorphism of 2 is 548449

Code: Select all

If the numbers on row i are denoted (N_i,X_i,Y_i) then

- The number of T-classes = Sum (X_i + Y_i) = 10945437157
- The number of S-classes = Sum (X_i/2 + Y_i) = 5472730538
- The number of S-classes that split into two T-classes = Sum X_i/2 = 5472706619
- The number of S-classes with only one T-class = Sum Y_i = 23919
- The total number of grids = 9! * 6^8 * Sum (X_i+Y_i)/N_i = 6670903752021072936960
- The total number of transpose-invariant grids = 9! * 6^8 * Sum Y_i/N_i = 14347728127918080

with hindsight I can just about see gsf's data here !

[gsf]

For completeness sake, I'm sure you can pack the grids of 8,9,12,18 to a file of ~20kB, and the grids of 3,4,6 to a file of ~1MB, which could be compressed considerably... The grids of 2 should occupy about 43MB, and after compression should be much less (a few MBs?)... Of course, all these could be relatively easily uploaded to a free hosting site such as www.badongo.com ...

all grids with #aut>1 compress to 1899446 bytes (info is <band #aut grid>)
I'll hold off posting data until the space-time tradeoffs precipitate out of this discussion

[gsf]

So saying that the class has already been represented is wrong. It might happen that the lexiographically first G_i is not the cronologically first to be visited. The only important point is that I have a tool for ensuring that every class is visited exactly once.

thanks
we're basically using the same techique: lexicographic ordering to check class membership during generation
we're using different parts of the grid in the inner loop
you: b1b2b3b4b7, me: b1b2b3b4b5b6
[ edit: changed B=>b, b==box not band ]
mine chosen to preserve the minlex canonical form in bands and grids
I'm trying to determine if this is doomed to be slower than your inner loop
to get close to 10H generation time a lot more pruning is in order

the current 5.34GiB catalog grid stream rate is 126K grids/sec/Ghz (<5H @ 2.8Ghz)