The New Sudoku Players' Forum

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

[Hammerite]

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.

Well, if there are 5,472,730,538 grids and we identify each one by one of the positive integers, then we can identify each one with just 10 digits instead of 81 Whether that's useful is another thing entirely!

EDIT: In order to make it even smaller, if you use letters as well as numbers - i.e. base 36, the letters being not case sensitive - we can do it in 7 digits!!! (Since 36^6=2176782336 but 36^7=78364164096)

[angusj]

Well, if there are 5,472,730,538 grids and we identify each one by one of the positive integers, then we can identify each one with just 10 digits instead of 81 Whether that's useful is another thing entirely!

Unfortunately, that is based on the false premise that for any one grid there is only one puzzle. The truth is for any one grid there can be many different puzzles.

[Hammerite]

Oh, I thought we were talking about grids...

I was already aware that some grids contain multiple, mathematically distinct puzzles. It came up in the topic I started on the minimum number of clues, which is around here somewhere.

If there was a systematic way of working out how many puzzles a grid has and of ordering them, then in principle the idea would still work. Assuming that no grid contains more than 10^k (or 36^k !) puzzles (for some positive integer k), you could form a puzzle identifier number by giving the 10 (or 7) digit reference number and adding k extra digits on the end. Of course you could only hope to do that if there was a systematic method of doing... what I said in the first sentence. :)

[angusj]

Oh, I thought we were talking about grids...

So you were, my mistake.
It seems to me a rather useless exercise to work out a reference number just for a grid (except for the mathematical challenge).

[Peter Morris]

Unless I am mistaken, you guys have now enumerated the 9x9 grid. Top job! However, have you been able to map the possible grids (i.e. given a unique ID, calculate the grid)? Or is this going to have to be a large look-up table, which I suspect to be the case, save for a pretty complex algorithm.

For either method, and given that the standard 9x9 puzzle is reflectively symmetrical, one only needs a further 25 bits of information to uniquely identify any given puzzle, indicating whether the cell displays its number or not. Using alphanumerics (upper case only), one could do that in a further 5 characters, leading to a 12 character string, identifying any puzzle. This is better than any hashing technique I've been able to create thus far and seems a useful shortcut.

So, the challenge is to determine the mapping algorithm or, given the grunt and the storage, creating a PHP page which returns an XML version of a 9x9 grid, given its 7-character ID. Deriving the puzzle using the 5 character suffix is trivial.

So, does puzzle 3KR WPA M9Y BBU require an x-wing? :o)

Pete

[dukuso]

The number of essentially different sudoku grids is

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

how many classes, when we consider transposed grids different ?

[Red Ed]

Unless I am mistaken, you guys have now enumerated the 9x9 grid. Top job! However, have you been able to map the possible grids (i.e. given a unique ID, calculate the grid)?

There seems to be some confusion about this, so let me attempt to clarify:

1. The number of ways of filling in an empty grid consistent with the rules of sudoku is 6670903752021072936960. This is now old news; see Bertram's post of May 23 at http://forum.enjoysudoku.com/viewtopic.php?t=44&start=138 .

2. The question just answered by me and Frazer (who also helped with the big number above) is: how many "essentially different" patterns are there within these 6.67x10^21 grids? We regard as essentially the same any two grids that differ only by relabelling the digits and/or applying some sequence of validity-preserving transformations such as rotation, transposition, row-band swapping and rows-within-band swapping. It's easy to show that the answer is something a bit bigger than Bertram's number divided by 3359232 x 362880, but somewhat harder to show that its exact value is 5472730538.

The way you go about getting the exact answer is to count grids for which one of the validity-preserving transformations merely has the effect of relabelling the digits. Here's a nice example, where rotation by 90 degrees just has the effect of mapping 1->3->9->7->1 and 2->6->8->4->2:

Code: Select all

124|567|893
378|294|516
659|831|742
---+---+---
987|123|465
231|456|978
546|789|321
---+---+---
863|972|154
495|618|237
712|345|689

I think all this stuff about reference numbers is a red herring and in any case is not something that anyone has provided the means to achieve. We can't even write down the 5472730538 essentially-unique grids, as the counting argument above doesn't work like that. And no, I am not volunteering to do anything about it!

how many classes, when we consider transposed grids different ?

Nor am I going to bother with this one. Sorry!

[datprogrammer]

A quick play with Ruby shows that a mere 8.2038817249341 e -10 %
of the total number of valid grids are distinct! That's a TINY number!!!

[coloin]

Yes great work Red Ed - a great sigh of relief when the two numbers divided without remainder ! - you can now have a couple of weeks off - but when you come back we will still need your help !!!!!!

So the classes with no invarients had the maximum number of transpositions and substitutions - but the classes which had invarients had a reduced number because they could be transposed into an equivilent grid - which when relabelled was identical. [Is this right ?]

I dont know if we have any further to go on this topic.

Regards

[angusj]

I dont know if we have any further to go on this topic.

Indeed we do! How many unique puzzles are there for each grid?

Yes, I know it's almost certainly an insoluble problem, not least because of the multiple opinions as to what constitutes a valid puzzle.

[dukuso]

I'm convinced now, that the whole enumeration can be done
in a few seconds. I got the correct number after 12 sec.
but included some data for the 44 chute-classes obtained
with another program.
Anyway, the trick is that we can coarsen the classes
by allowing to permute the minicolumns in a filled band.
This doesn't change the count of the possible completions
and gives only 3863552 different classes.

-Guenter.