The New Sudoku Players' Forum

[frazer]

I'm impressed with the elimination of class 275, and no doubt the others work in the same way (thanks for the full output of your program eliminating all the other classes -- I'll work through some of these by hand myself), and I'll update the web page...

As for your second post, element 86 is not rotation by 90 degrees, but a conjugate, so I don't think that it will necessarily generate an interesting group. For example, (1 2 3) and (3 4) generate S_4, whereas (1 2 3) and the conjugate (1 2) of (3 4) generate S_3. I guess that I'm trying to say that the choice of representative from within conjugacy class makes a big difference to the group generated, and so influences whether the group you get is interesting or not. Certainly rotation by 90 and rotation by 180 should generate an interesting group, but conjugates may generate a larger group which may contain non-interesting elements.

To get the number of essentially different grids, we just need to take the average of the number of fixed points of each group element (where our group is acting on the set of grids-up-to-relabelling). This is essentially Burnside's Theorem.

Frazer

[Red Ed]

Thanks for the explanation of subgroups and conjugates ... makes sense now.

To get the number of essentially different grids, we just need to take the average of the number of fixed points of each group element (where our group is acting on the set of grids-up-to-relabelling). This is essentially Burnside's Theorem.

... and this is really good news (I'd forgotten this theorem). So much so that I'll celebrate by calculating the number of grids essentially invariant under 180 degree rotation: 9! x 155492352 = 56425064693760. It's about 5 times easier to be 180 degree invariant than it is to be transpo invariant.

[Red Ed]

Here are another two.

This transformation that cycles the three row bands ...

Code: Select all

ABC       DEF
DEF  -->  GHI
GHI       ABC

... appears to have 9! x 144 x 103040 = 5384326348800 essentially invariant grids.

And any transformation that cycles the three rows within each band (not necessarily in the same "direction", e.g. row perm (123)(456)(798) is allowed) looks to have 9! x 72 x 18 x 82944 = 39007939461120 invariant grid patterns.

[coloin]

Stunning work - but I will have to take your word for it.

Does it mean that when we sum up the total number of invarients for each group we get Bertram's number [I hope so] ?

Also - prior to your present stream of postings I had been thinking about transformations and relabeling. :

1.
If you have box 1 :
123
456
789 as 9! options and then you start shuffling rows and columns in the other boxes you have to be careful not to shuffle the numbers in box 1 - other wise you change box 1 - thus you only have one factor of 6*6*2 [72] - this explains the 72 in the calculation using the 44 method

2.
I started with box 1 as
123
456
789 and the rest a random grid
- then did a 90 degree rotation - then I relabeled the grid so that the new box 1 was as before
- not surprisingly [but a pity] no amount of row and column shuffling got me back to the original grid - even though it was supposedly equivilent - from what you have posted - there are some grids which do this - "13056 x 9! = 4737761280"
- but then I started thinking if you carry on shuffling and row swapping - always by definition keeping with an eqivilent grid - are we going to seriously overestimate the number of equivilent grids? [Maybe we are not ? - maybe it is only 6^4*6^4*2]

Keep going with the 275 - [Where did this number come from ?]
Also I also dont follow the numbers [0-81] in the representitive labeling box.

Regards

[frazer]

180 degree rotation is class 79. The cycles of the three row bands is class 25, and the cycles of three rows within each band is class 8. I've updated the web page (finally). I think all transformations cycling rows within bands (or columns) are conjugate, but if not, then other classes will have the same number of invariants too.

In response to coloin, it's slightly tricky to explain what we are doing now! But I do remember as a child seeing questions like: colour the edges of a square red and blue -- how many essentially different ways are there to do this (where two colourings count the same if they can be rotated into each other). It turns out that there is a mathematical theorem ("Burnside's Theorem") which allows you to work this sort of thing out. You write down all the possible symmetries (there are four symmetries, rotation by 90, 180 and 270 degrees, as well as the trivial symmetry which doesn't move the square at all). For each symmetry, you count the number of colourings which are fixed by the symmetry. Then the answer to the question is the average of these numbers.

For this problem, there are 4 edges, each can be coloured in 2 ways, so there are 2x2x2x2=16 possible colourings of the square's edges. The identity fixes all these 16 colourings. Rotation by 90 degrees fixes the colouring only if all four sides have the same colouring. So the fixed colourings are those which have all 4 edges red or all 4 blue, making 2 possibilities. Rotation by 180 degrees fixes a colouring if the opposite pairs have the same colour -- we have 2 choices for the top/bottom, and 2 for the left/right, making 2x2=4 in total. Rotation by 270 degrees clearly also has 2 fixed colourings, just like the 90 degree case. The average is therefore (16+2+4+2)/4=24/4=6.

And there are indeed 6 colourings: all 4 edges red, 3 red edges and 1 blue, 2 opposite red and 2 opposite blue, 2 adjacent red and 2 adjacent blue, 1 red and 3 blue, and 4 blue.


We are trying to do the same to count the number of essentially different sudoku grids. It turns out that there are 3359232 symmetries. To count the number of fixed points for all these would take an immense time, even with Red Ed's amazing programming. But just as the rotations by 90 and by 270 gave the same answer above, it turns out that there are 275 "conjugacy classes" (any 2 elements in the same class will have the same number of fixed grids), so we only have to see what happens for these 275 symmetries -- any symmetry will have the same number of fixed grids as one of these 275. (It's a bit like the reduction to 44 in the problem of counting all different grids.) And Ed has pointed out that all but 28 of these classes have no fixed grids. Of the 28, he's computed how many fixed grids there are for 6 of the classes.

That explains the idea. I should explain the notation on the web page... The table has one row for each of the 275 classes. I've labelled these arbitrarily 1-275 (just in the order that the program spat them out). The third column gives you one of the symmetries in each class. For example, for class 2, the bracket (7 8 9) means that square 7 is moved to square 8, square 8 to square 9 and square 9 back to square 7. (In other words, this bracket permutes the top row of the third block.) Class 2 contains the symmetry which sends 7->8, 8->9, 9->7, 16->17, 17->18, 18->16, 25->26, 26->27, 27->25, and so on. If you think about it, this is the symmetry which cycles the three final columns, and also cycles the three final rows. The second column gives the number of symmetries in the same class (which therefore have the same number of essentially invariant grids), and the final column says what this number is.

So the sum of the numbers in the second column should be the total number of symmetries, 3359232. What we need is to average, for each of these 3359232 symmetries, the numbers in the 4th column. This means that to get the final answer, we multiply the numbers in the second column by those in the fourth, add them all up, and divide by 3359232. (Of course, if we don't get a whole number, something will have gone wrong...)

Frazer

[coloin]

So much so that I'll celebrate by...

Thanks for the explanation - I can sense a celebration too. Maybe a triumph.

[Red Ed]

A few more:

class 7: nr invariants = 9! x 21233664
class 9: nr invariants = 9! x 4204224
class 10: nr invariants = 9! x 2508084

I'm fairly confident about these, since the same code also confirms the answer previously obtained (in a more efficient manner) for class 8.

Also, using almost the same program:

class 28: nr invariants = 9! x 2085120
class 30: nr invariants = 9! x 294912

Of the remainder, I think classes 27, 29, 40, 134, 135, 143 and 145 should be easy to work out. But I don't like the look of 22, 23, 31, 32, 43, 44, 142 and 144 at all ...

Update: class 22 appears to have no invariants.

[coloin]

Great work Ed
.................When you say that a class of grids have no invarients / fixed grids - what does this mean ?
.................When you say that a class of grids has x invarients - what does this mean ?

[I sort of know what you mean but just clarify please] [Frazer has explained above I know !]

Also - how are you doing all this ? [rude question - but Im interested !]

Regards
.

[Hammerite]

And are you going to tackle the general, n^2 by n^2 (n-squared by n-squared) case? :)

[Red Ed]

Here are some new results:

class 23: 9! x 162
class 24: 9! x 288
class 26: 9! x 2592
class 27: 9! x 5184
class 29: 9! x 1296
class 31: 9! x 648
class 32: 9! x ??? (method doesn't apply here)
class 40: 9! x 1854
class 43: 9! x 288
class 44: no invariants
class 134: 9! x ??? (method is too slow here)
class 135: 9! x 27648
class 142: 9! x 6480
class 143: 9! x 1728
class 144: 9! x 3456
class 145: 9! x 13824

The code that generated these also confirms previously-recovered results for classes 30 and 86, so there's a good chance these results are correct.

I think that just leaves two classes: 32 and 134.

[frazer]

Fantastic work. I'm away for the next week and a half, so I'm going to miss your final calculations (and I won't be able to update the web page either)... Good luck!

Frazer

[Red Ed]

The number of essentially different sudoku grids is

18,384,171,550,626,816 / 3,359,232 = 5,472,730,538

I'm annoyed at just how easy this was to calculate in the end: I found, after coding endless class-specific solvers, that a single method sufficed for all cases -- actually just an extension of the very first thing I tried (for transpositions). Oh well. It works as follows.

1. Let's say that we're trying to count the number of essentially-invariant grids for some grid transformation, g.

2. Without loss of generality, we can assume that digits 1-9 are laid out in order on the top row of an essentially-invariant grid. Since digit labels are irrelevant, we won't multiply by 9! at the end.

3. We make 9 lists, one per digit, showing the positions that the digit could occupy on the grid, given its known position in the top row. That's 5184 "templates" per digit.

4. For each template, work out what happens to it when successive powers of g are applied. If the template is called x, then you want the set of each possible (g^i)x to consist of non-overlapping templates: if not, delete the template from the list; but if so, replace the template by the union of all (g^i)x. You could call these replacements "extended templates".

5. Now run a 9-deep loop (or maybe 8-deep is good enough) looking for 9 non-overlapping extended templates, one from each of the per-digit lists. Or, nearly do that: when at level d in the loop, if you find that one of the extended templates from a higher level has occupied digit d's cell in the top row, then you contribute the empty template instead of one from your list.

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

btw, I was wrong about class 22: it has 9! x 323928 invariants. The two classes needed to finish off the calculation were class 32 (9! x 6342480) and class 134 (9! x 449445888).

[scrose]

Well done! Does this mean that it would now be feasible -- with a number as small as 5.47 billion -- to give each "essentially different" grid a unique reference number?

[angusj]

Well done! Does this mean that it would now be feasible -- with a number as small as 5.47 billion -- to give each "essentially different" grid a unique reference number?

Well done indeed.

The answer to your 'reference number' question would have to be yes, but one wonders if it can it be short enough to be a significant improvement over printing the whole 81 digits.

[johnw]

Well done! Does this mean that it would now be feasible -- with a number as small as 5.47 billion -- to give each "essentially different" grid a unique reference number?

The implication of this question is that any grid can simply be reduced to its "canonical form" which has the given reference number. So I could input a random valid completed grid and the program would say "Ah yes, that's equivalent to grid number 1046784232 if you permute rows (15)(34) etc etc and renumber the top row"

Are we sure that's a trivial task?

What's needed next is more work on the starting grids not the completed grids.