The New Sudoku Players' Forum

[Mathimagics]

In "There are 5,472,730,538 essentially different Sudoku grids", the authors arrive at the magic number by:

• determining the conjugacy classes for the permutation group of Sudoku grid transformations

• for a representative of each conjugacy class counting the number of invariant grids

• using Burnside's lemma, ie dividing Sigma(class size * number of invariant grids) by the order of the permutation group (3359232)

I am trying to replicate this process. I have used GAP to replicate their conjugacy classes, and produce a representative for each class, and so have replicated the first 3 columns of their table.

But now find that the article says nothing about how to determine the key values, i.e. column 4 (number of invariant grids).

It just says "column 4 gives Ed Russell's computation of the number of grids fixed up to relabelling.". But gives no information on how that is done.

Given that Russell is our (erstwhile) very own Red Ed, I thought the details would be here in this forum somewhere, but I can't find it.


Can anybody help?

[David P Bird]

A forum search of Red Ed's posts that contain the word 'conjugacy' gives 17 hits, all in the general section - perhaps one of those will give you a lead. (Apologies if you have already followed that route.)

[Mathimagics]

Thanks David!

That helped me to find some useful-looking clues in Page 17/43 of this thread.

[StrmCkr]

http://forum.enjoysudoku.com/post262717.html#p262717 i also posted some hints in this thread on a way to accomplish it, with notes
i'm about 90% of the way completed my code to generate all of them {bug testing it atm} and ill update the next sections in a few days.

they generated 2 different lists

one of the auto-morphs
and a 2nd with all the unique grids.

then counted the number of auto-morphs per solution grid

then you have
sum (auto morph # x grid count ) * 9! = total grids.

[Mathimagics]

they generated 2 different lists
. one of the auto-morphs

. and a 2nd with all the unique grids.

then counted the number of auto-morphs per solution grid

then you have
sum (auto morph # x grid count ) * 9! = total grids.

That's not quite right, I think. Their approach is really a counting method rather than an enumeration method, although the counting necessarily entails some enumeration.

The key point is that the 3,359,232 geometric grid permutations can be reduced to just 275 sets (the conjugacy classes). Each member of a set has the same number of automorphic (invariant) grids. Thus to count all automorphic grids we only need to find the automorphic grid count for any one member of a set.

Obtaining the automorphic grid count for a given permutation necessarily involves enumeration (I had initially thought Ed Russell had some secret counting algorithm). It turns out that Red Ed Russell did describe the enumeration method here. The method is based on transversals and digit templates.

It may well be possible to generate ALL automorphic grids for a permutation set (conjugacy class) from the single permutation enumerations, I would have to look into that (perhaps someone can provide an answer to that).

The essential point is that we reduce the problem from 3,359,232 permutations to be tested to just 275 (*). And this same methodology can be used for arbitrary grid size, and for most Sudoku variants, to count the number of "unique" solution grids.

None of this is intended in any way to critique your methodology, by the way. I must confess to not really understanding it, but then again, it's pretty easy to achieve that!

When you've finished, I'd like to see a "layman's guide" to the method.


=================================================================================================
* in fact for 9x9 Sudoku only 26 of these 275 classes actually produce automorphic grids, but in general (eg different size grids, different Sudoku variants) we may not know that.

[eleven]

Have you seen the wikipedia links from https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#cite_note-ed44-81 (which also has a description how to enumerate them) http://www.afjarvis.staff.shef.ac.uk/sudoku/ed44.html and http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf ?
Also look at this post http://forum.enjoysudoku.com/post4381.html#p4381.

With gsf's program you can list all essentially different grids, pack them with i think 3 bytes per grid and make some calculations like listing all automorph grids - but don't ask me for the command line parameters ...

[Mathimagics]

Thank you eleven, but all these links refer to the "all different" enumeration problem (ie: "There are 6,670,903,752,021,072,936,960 Sudoku grids").

Although I do note that the last one (dukuso's ultra-fast enumeration method) is new to me.

Have I missed the connection to the "all unique" question? Are you saying that gsf sudoku tool can be used to identify automorphisms for just 44 grid candidates, and thus arrive at the 5,472,730,538 figure?

[eleven]

Hi Mathimagics,

you are right, the links don't show how the numbers for the essentially different (unique) puzzle count were calculated (only "brute force" is mentioned). So the post by Red Ed you found, seems to be the only description. I was also surprised, that i could not find anything about alternative ways to get this number or any confirmations by others (maybe there were some, but got lost with the programmer forum).

However, gsf has calculated all of them. See e.g. the thread catalog of all essentially different grids.

[Mathimagics]

So the post by Red Ed you found, seems to be the only description.

And a pretty loose description at that! I like the way he concludes with:

And that's all there is to it. I'd rather not tell you just how long it took to debug this stuff though ...

... probably as long it took me to recreate this method from scratch!

But I have a working version, confirmed for one of the classes (class #23 has 162 invariant grids) ...

Unlike gsf's catalog, this methodology just enumerates automorphic grids directly. Given we know the total number of different grids, we can arrive at the unique grid count via the back-door, ie: #different minus #automorphic.

Getting all this going will allow me to arrive at the corresponding counts for SudokuP, aka "restricted sudoku", for which the "number of unique grids" (as far as I can tell) is either unknown unreported.

[dobrichev]

In this topic Kjell Fredrik Pettersen is reporting execution time

Code: Select all

Lookup table generation: average   1.87 ms
Gangster generation    : average   0.31 ms
Main counting first    : average   2.03 ms
Lower right count      : average   1.72 ms
Main counting second   : average   2.50 ms
=====
Overall                : average   8.43 ms


[Mathimagics]

Thanks, dobrichev, I hadn't seen that.

It too, however, seems to be an optimised method of counting different grids, and I will take a closer look ...

But it doesn't answer the unique grids question.

Speaking of which, I have made some progress with optimising the Red Ed algorithm ... which I will describe once I'm satisfied with it.

[Serg]

Hi Mathimagics!

So the post by Red Ed you found, seems to be the only description.

And a pretty loose description at that!

It's very likely that nobody at this forum can describe Red Ed's method in details at the moment. Years ago I studied Red Ed's famous computation of essentially different sudoku solution grids (we discuss exactly this work now) and I was surprised that the method of finding "fixed" grid for given class was not described.

Red Ed is bright figure, maybe the main contributor to sudoku mathematics. But his posts were always brief. You should force your brain to work for understanding his ideas. His post were "brain food" for me. Maybe it's time to understand his method of counting "fixed" grids ...

But I have a working version, confirmed for one of the classes (class #23 has 162 invariant grids) ...

Congratulations! Would you describe your method?

Getting all this going will allow me to arrive at the corresponding counts for SudokuP, aka "restricted sudoku", for which the "number of unique grids" (as far as I can tell) is either unknown unreported.

It would be nice if you could use common terminology - I think you are talking about "essentially different" SudokuP grids, right? It's very likely nobody solved this problem, but you should understand, that possible isomorphic transformations for SudokuP grids don't form group. I mean that there are "universal" isomorphic transformations which transform any SudokuP grid to other SudokuP grid, and there are "non-universal" isomorphic transformations which transform some SudokuP grids to other SudokuP grids, but they transform the rest SudokuP grids to non-SudokuP grids. I.e some isomorphic transformations are not universal. This means that Burnside's Lemma used for essentially different sudoku grids enumeration by Red Ed is not applicable here.

Serg

[Mathimagics]

Hi there Serg!

Would you describe your method?

I will do so in detail once I have sorted out some wrinkles!

I'm sorry about "unique", it's used in the SudoPedia page "The Importance of Automorphic Solutions" and I assumed it was in common use. I will stick to "essentially different" from now on!

It's very likely nobody solved this problem, but you should understand, that possible isomorphic transformations for SudokuP grids don't form group.

Yes, I had indeed noticed this, and actually made mention of this fact myself somewhere (?).

My thinking was that those particular cases of non-standard isomorphism might be addressed as a separate problem. But surely the valid universal transformations surely still constitute a permutation group, don't they?

[Mathimagics]

Actually, on reflection, it occurs to me that this might not be a problem after all!

The problematic transformations are those that involve row/col permutations within individual bands (as against ALL bands).

It's true that these may or may not yield another SudokuP.

But they can't result in automorphisms - this is true for all Sudoku's, not just these restricted forms, which is why the Russell & Jarvis tables show 0 for the number of invariant grids for all of these transformations.

I think that resolves that question!

[and I learned below that I thought wrong!]

[Serg]

Hi, Mathimagics!

The problematic transformations are those that involve row/col permutations within individual bands (as against ALL bands).
It's true that these may or may not yield another SudokuP.
But they can't result in automorphisms - this is true for all Sudoku's, not just these restricted forms, which is why the Russell & Jarvis tables show 0 for the number of invariant grids for all of these transformations.
I think that resolves that question!

Yes, such "non-universal" transformations cannot result to automorphisms. But automorphisms themselves are not the only obstacles, preventing us from counting essentially different grids.

Suppose, we have a set G of transformations, acting on set E of elements. Assume, that set E is closed under set G of transformations, i.e. result of any transformation of any element belongs to E. Let's consider orbits of E elements - results of all transformations applied to single element e. If all orbits are disjoint sets and each orbit contains |G| elements, the task of enumeration essentially different elements is simple. We need to divide |E| by |G| to get number of essentially different elements. But unfortunately in real life some elements can have automorphisms, decreasing size of orbits. Ignorance of automorphisms leads us to underestimation of true number of essentially different elements.

Suppose, we have another set H of transformations, acting on the same set E of elements, such that set H doesn't provide closure of E. I.e. result of applying transformation h, belonging to H, to element e can belong or not to set E. Such "wrong" transformations can connect orbits of set E elements under transformations from set G. So, ignorance of "non-universal" transformations leads us to overestimation of true number of essentially different elements. The "non-universal" transformations accounting problem is not related to automorphisms accounting problem.

Serg