The New Sudoku Players' Forum

[kjellfp]

0.359 sec - I'm just amazed. Congratulations. I'd like to see and share the code.

I'm down to 1.4 sec myself, but that's on a 3 GHz, so I admit your code is far faster than mine!

And by the way: The number of S-classes and T-classes as well as (once again) the number of grids for 3x3-sudoku is now confirmed.

Let A be the group of automorphisms acting on 3x3-sudoku grids, given by symbol permutations, band permutations, stack permutations, permutations of rows within a given band and of columns within a given stack. For any grid G, let K(G) be the automorphisms in A leaving G fixed. Then #[G] = #A/#K(G) = 9!*6^8/#K(G) where [G] is the equivalence class of G modulo A.

I have written a program that runs through all T-classes, and for each class [G] (where G is a grid) finds the size of K(G), and wether G is transpose-invariant (i.e. [G]=[transpose(G)]). The result of the counting:

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


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

[kjellfp]

Yep, it's all-inclusive. Down to 0.359 seconds now (0.093 on generating the gangsters, 0.266 on counting all the grids) and can probably be made to go a little bit quicker.

I'm down to 0.203 seconds now, but as my CPU on the paper should be faster, I don't know which of us had the quickest implementation.

I use 0.118 on gangster generation and band completion, and 0.085 on the final counting.

EDIT:
0.156 total. Red Ed is still better when comparing CPU, but I can see further improvement. I'll guess we are converging towards more or less the same code.

[Red Ed]

I'm down to 0.203 seconds now, but as my CPU on the paper should be faster, I don't know which of us had the quickest implementation.

I use 0.118 on gangster generation and band completion, and 0.085 on the final counting.

My current figures are 0.046 on gangsters plus 0.113 on final counting. I don't think I can make it go much faster.

btw, great work on the all-in-one enumeration quoted above -- nice to see the nr essentially different grids finally confirmed (along with so much more besides; what a great method!)

[kjellfp]

OK, so I'm really loosing faith on the 4x3-counting.

I just had the ideas on how to attac it, but I didn't do enough on the estimates. I now see that the task is too big.

There are 12!/(4!*4!*4!*3!)=5775 ways to group 12 symbols into an unordered tripple of disjoint 4-element sets. That means that the number of band configurations where the columns within a box is ordered by their smallest element, and where the configuration of the first box is C0={{1,2,3,4},{5,6,7,8},{9,10,11,12}}, is 5775^3.

Given a band configuration on this form, there are 24^4*6 operations that will lead to all the other elements in the same equivalence class: 4! ways to permute the boxes and 3! ways to permute the columns in the first box before the symbols are repermuted to put the first box on the base form C0, then another 4!^3 ways to permute the symbols within each column in the first box.

So each equivalence class ha a maximum size of 24^4*6, hence there are at least 5775^3/(24^4*6) = 96752 gangsters in 4x3-sudoku. As there are 346 ways to choose the column configuration of each box on the second row, the innermost loop when doing the counting must be run at least 96752 * 346^4 / 6 = 2.3e14 times. And that is not the only problem, it can be hard for a band configuration to find the way back to its gangster, or in another way find out its total number of sudoku bands - without wasting to much time.

Unless someone comes up with a clever shortcut here, I regard the exact number of 4x3-sudokus as inaccessible for us mortals.

Frustrating when the estimate I have given earlier probably is pretty close...

[dukuso]

but 2.3e14 doesn't sound soo bad.
Just 1 day with 3GHz and 1 operation per cycle.
Let's say you have 64 cycles in your inner loop , then
let us mortals just wait that you'll get one of these 64-processor
computers for cheap in a few years...
I think some of us will see that number being computed in their lifetime.

By that time RedEd will probably compute the 3*3s in a microsecond...

[kjellfp]

My best now is 0.013 on gangsters and 0.070 on counting. I have some improvement ideas in my head, but I doubt if they will contribute.

I'm running cygwin on XP, I don't know how that compares to running under Linux on the same hardware?

dukuso: I don't think I'm planning to do 4x3, despite your encourage. I'm not interrested only in running the loop 2.3e14 times, I have to do something inside as well. Also 2.3e14 is an optimistic lower bound. You should probably multiply by 3, and upgrade from the lower bound estimate to the actual number of gangsters. (For 3x3, the lower bound is 11, the actual number 4 times as big). So say 7e14 is the number of loops. When doing T-class numbering, I visit 1.1e10 classes in 10 hours, 7e14 classes would take 72 years. 4x3 might be faster on the innermost code, so maybe "only" 10 years? I don't know, but I think the one who sits down and waits for the newest hardware will be faster than the one who starts the counting now...

[kjellfp]

I have now checked Ed's code, and I see that together, we can improve it even more.

My best was 13 ms on gangsters and 70 ms on counting.
Ed's (run on my PC) was 33ms and 41ms. We had one best part each, but Ed was best in total.

I now see how Ed was better on the second part, and when adopting his ideas, I got the last part for me in 42 ms. Using some of my ideas on Ed's code brought him down to 40 ms, so he still does something better than me, but I'm not going to chase it.

Ed, I sent you a PM, but hasn't left my outbox. I'll send you my code with comments later.

Btw, one original reason for improving the code, was to see what we could expect for the 4x3-counting. Now, if my lower bound 96752 on the number of gangsters is correct (probably wrong) and each innerloop could go just as fast as for Ed's counting (also wrong), then the entire counting should take 83 days on my PC. Broken up in parts on several computers makes the number not as inaccessible as I first thought, though hard enough. There are also other problems to overcome as well, like memory: Integer arrays of size 280x280 is not the same as 5775x5775x5775...

[Moschopulus]

Does anyone have a program (that they are willing to share) that computes the symmetry group/automorphism group of a given grid?

Way back in an earlier post I (probably others too) mused that grids with large auto group are less likely to have a puzzle with a small number of clues. I'd like to compute some data on that.

This thread is too long...

[dukuso]

@kjell:
I also got Ed's code, but didn't quite understand. I'll wait for
the final version - it's getting ever faster
@kjell:
we needn't do the 4*3 computation now. Just let's keep in mind that
it's not completely out of reach. Someone might do it earlier
or later.
@Moschopulos:
I use "Nauty" for this. I have several programs to convert a
sudoku(-grid) into graphs with same automorphismgroups
as a S-class,T-class,G-class
Then I use a program,calling Nauty, to compute the size,
canonical form or generators.
Send email, what you need.




@all:

has anyone stored this thread into one big file ?

edit: ahh, I just found out, that you _can_ search this
thread: there is an option : display results as posts.
So, what's about all the people (including me) complaining
this long thread couldn't be searched ?
Did they all miss this possibility ?

[kjellfp]

Does anyone have a program (that they are willing to share) that computes the symmetry group/automorphism group of a given grid?

I used this when counting the T-classes. This is basically how:

Before the counting, all 416-band groups were generated, and their symmetry group stored. I also store enough information making it possible to permute any band back to its class representative.

On a complete grid, I transform it such that the first band is on its representative form, let the symmetry group act on the entire grid, and count grid symmetry transformations. If some of the other bands belong to same class, I permute bands as needed and do the same.

I never store the symmetry group of a grid though, only remember its size. But I could if I would.

[Moschopulus]

Does almost every grid have automorphism group of order 1?

Apart from the canonical grid, I have searched over 20,000 grids and found three grids with group of order > 1. These have order 2. (Thanks dukuso for the program)

Which grids have group of order > 1? If there are so few of them, it should be possible to work them out.

[gfroyle]

Does almost every grid have automorphism group of order 1?

Yes... the vast majority of them do, and this is to be expected. This will be true in the mathematically precise sense of the phrase "almost every" in that the proportion of grids with k^2 rows and columns with trivial automorphism group will tend to 1 as k tends to infinity. [I am just restricting to the square case to avoid ambiguity about what the "boxes" are, but it will be true for any sensible version]

The exact numbers for the regular Sudoku with 9 rows/columns were computed as part of the enumeration of equivalence classes of grids:


http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html


Cheers

Gordon

[Moschopulus]

Oh yeah, I forgot those numbers were there. Thanks!

[kjellfp]

Does almost every grid have automorphism group of order 1?

Yes. If you look at http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=454 you see that almost every isotropy group is trivial. This was also expected before I computed the table, as #grids/#T-classes is almost the same as 9!*6^8.

Which grids have group of order > 1? If there are so few of them, it should be possible to work them out.

I have already done this. Guenter asked for it, so I produced the entire list of class representing grids grouped into files depending on isotropy class size and wether the classes were transpose invariant. I have already sent him the files, except those that are non-transpose invariant with group order 2 (that file alone was 11 MB compressed, the others 300 KB all together).

Give me your mail address, and I'll send the same files to to you.

[dukuso]

Does almost every grid have automorphism group of order 1?

Yes... the vast majority of them do, and this is to be expected. This will be true in the mathematically precise sense of the phrase "almost every" in that the proportion of grids with k^2 rows and columns with trivial automorphism group will tend to 1 as k tends to infinity. [I am just restricting to the square case to avoid ambiguity about what the "boxes" are, but it will be true for any sensible version]

is it true for pandiagonal latin squares ?