The New Sudoku Players' Forum

[ramnath]

Whilst I love solving tough Su-Dokus I have a couple of niggling questions in the back of my head about the puzzle.

1. How many ways are there of populating an empty 9*9 grid such that it satisfies the Su-Doku rules?

2. What is the minimum number of clues (cells) required to give a unique solution?

If anyone has the answers (and reasons/calculations) - please let me know!

Thanks
Steveb

I BET IT IS NOT MORE THAN 81 TO THE POWER 9 THAT IS 150094635296999121 NUMBER OF SOLUTIONS . I AM WORKING ON THIS

[coloin]

The Gang of 44 is published in http://www.shef.ac.uk/~pm1afj/sudoku/

I think we need to have a definitive opinion on how many transformations there are.

Double counting is the issue here I think.

[frazer]

Some comments on recent posts:

nilton's e-mail gives an answer which is not so far away. But to say that column 5 can then be filled in in 5! ways and column 6 in 4! ways is too simple. One needs to be more careful here.

There is a request for a clearer listing of the "gang of 44". I'll do this and add it to the web page sometime later this week. (I'm working from home today.)

In reply to condor, you are right that rotations, reflections and relabelling will give the same number of similarities for all grids. But in our efforts to reduce the sizes of the brute force computations, we introduced other similarities, and these can sometimes coincide. This makes the sizes of the similarity classes not constant. For example, given the top three rows

123 456 789
456 789 123
789 123 456

a permutation of the three rows which moves the top row to the bottom:

456 789 123
789 123 456
123 456 789

could also be viewed as a permutation moving the leftmost 3x3 block to the right. For an arbitrary Sudoku grid, these transformations don't coincide -- it's just that in some cases, they do.

To answer coloin's most recent remark is difficult without a really clear definition of the question. Is the question now: exactly how many essentially different 9x9 Sudoku grids are there? This seems a good question to ask, as long as we have a precise definition of what "different" should mean. If we define our equivalences in the same way as Bertram and I and Red Ed do, then there are 44 choices for the top three rows. Since relabelling has restricted the first block to be 123/456/789, there are at most 36288 possible blocks 4 and 7, depending again on the definition of "different". Given block 4, there are then at most 36288 choices for blocks 5 and 6, and similarly given block 7, there are at most 36288 choices for blocks 8 and 9. So an upper bound is 36288^3*44. But this is surely a wild overestimate (the huge majority of these are not going to be Sudoku grids, and there are going to be additional similarities between many of those which are), although it would provide a good starting point for the calculation. But the question needs clarification: we need a precise definition of what will be meant by "different". I'm sure that rotations, reflections and relabelling should count as giving "the same" grid. Do you allow permutations of rows 1-3, 4-6, 7-9? And columns in the same way? Do you allow grids whose top rows start
1** 4** ***
4** 1** ***
*** *** ***
and
4** 1** ***
1** 4** ***
*** *** ***
to be counted as the same grid? There are going to be at least three different answers to this question, depending what transformations you allow.

Frazer

[frazer]

The bound in my recent post is true, but the justification is flawed (there are a couple of factors of 72 I've removed in writing 36288 which I shouldn't have removed). In any case, a better bound is got by looking just at the 44 top three rows, and adding the number of completions to full grids. This is certainly bounded by 44*108374976, the second factor being the largest number which crops up. But I'm sure that the answer will be much smaller (depending on the definition of "different")...

Frazer

[Red Ed]

Double counting is the issue here I think.

For an arbitrary Sudoku grid, these transformations don't coincide -- it's just that in some cases, they do.

[Red Ed]

Damn it. Wretched computer sent before I wanted it to.

What I was going to say was ...

Let G be the group of all transformations that preserve "essential similarity" -- so, transposition, rotation, chute swapping, row/col swapping -- *excluding* digit relabelling. Say that a sudoku S is "essentially invariant" under some transformation g, written g(S) ~ S, if g merely has the effect of relabelling the digits in S. The g for which g(S) ~ S is a subgroup of G. For each subgroup H of G, let n(H) be the number of the 6.67e21 sudokus that are essentially invariant under H but not under any larger group containing H. So N = sum of all n(H) = 6.67e21 and the number of essentially different sudokus is sum_H n(H)/|H| .

Now I expect enumerating n(H) will be hard for most H. So instead let's go for m(H), the number of sudokus essentially invariant under H (and possibly larger subgroups, but we don't care -- unlike the n(H) case). This might be quite easy to evaluate for many H, e.g. how hard can it really be to find the number of sudokus for which transposition merely has the effect of relabelling the digits? Tricky, yes, but I'm sure it's tractable.

So, you grind through the m(H) calculations for all different "types" (e.g. no point doing vertical inversion once you've done horizontal) of subgroup H and then combine the results using some sort of horrible inclusion/exclusion formula.

I've no idea whether or not this is a feasible approach. I'm worried that there might be far too many subgroups to evaluate (just think of all those row/col perms) but am too lazy to work out the group structure to confirm this ...

[frazer]

If my calculations are right, the group G mentioned in Red Ed's post has size 3359232 = 2^9.3^8. This group is smaller than I was expecting. But the factors perhaps suggest that there will be a lot of subgroups. It may be just as easy to list the group elements and work out for each element how many sudoku grids are essentially invariant under this element. I have no idea if this is feasible either, although it doesn't look impossible; it's just that there are quite a lot of group elements. I'll see if I can get the program I'm using (for the first time!) to output the list of group elements to a file...

Frazer

[Red Ed]

The number of grids essentially invariant under transposition appears to be 30258432 x 9! = 10980179804160.

Next!

[frazer]

The group G has 275 conjugacy classes, so rather than list all the elements, it should be enough to list representatives of each class, together with the size of the class. For each of the 275, one needs to do some calculation like Red Ed's.

More facts about G, according to this program (!): it is solvable, but not nilpotent, has trivial centre, derived length 5, and exponent 72.

Frazer

[gfroyle]

If my calculations are right, the group G mentioned in Red Ed's post has size 3359232 = 2^9.3^8.

The row permutations give Sym(3) wreath Sym(3), the column permutations give an independent Sym(3) wreath Sym(3) and transposing the matrix gives 2. So total order is 6^4 . 6^4 . 2 which agrees with your calculations..

Cheers

gordon

[Aeron]

To get the total number of posiblilities you must first relize that some sudokus have the same pattern.

Take

123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678

and

637159428
159428637
428637159
371594286
594286371
286371594
715942863
942863715
863715942

for example.

If you take the 1st box and you call the
up-left A
up B
up-right C
left D
center E
right F
bottom-left G
bottom H
bottom-right I

You'll get out of both sudoku's:

ABCDEFGHI
DEFGHIABC
GHIABCDEF
BCDEFGHIA
EFGHIABCD
HIABCDEFG
CDEFGHIAB
FGHIABCDE
IABCDEFGH

Cause you can connect 123456789 to ABCDEFGHI on 362880 (9*8*7*6*5*4*3*2*1 = 9!) ways.

So the formule we can now conlude is:
possiblilities = patterns * 362880.

The number of patterns is based on how many we ways we can place ABCDEFGHI in the sudoku

Now lets see on how many ways we can place the A in the sudoku:



Diffrent colors indicates the boxes (except for the 1st)
White means unusable place.
A black dot indicates the position of A.
A light color indicates where the black dot of that box also could have been placed.
A dark color indicates where the black dot could be placed if the other black dots where diffrently placed.

You might think "What if i place the 'A' in the first block on position 2?" Well if we do that we get on how many ways we can set the 'B'

And now a image for the rest:



The number of posibliities we can place 'A' in a box per box is:

1 6 3
6 4 2
3 2 1

Thats 5184 (1*6*3*6*4*2*3*2*1).

The same as for BCDEFGHI

But, if we do
5184^8 * 362880
It's wrong cause some pattrens overlap eachother.

And i'm currently working on how many pattrens overlap.
What I do know is that the forumla is something like:
5184 * ? * ? * ? * ? * ? * ? * ? * 1 * 362880

And the overlapping calulating has something to do with 2^?.

Thats how far i got.

Update/edit:
I made a table of in how many times the 'A' is set in a place in the box in all of it's patterns:

[Red Ed]

For each of the 275, one needs to do some calculation like Red Ed's.

The number of grids essentially invariant under quarter-turn rotation looks like it might be 13056 x 9! = 4737761280. Gosh, that seems quite small, hope I've coded it correctly.

Three classes down (id, transpo, rotn), 272 to go ...

Perhaps we need a web page or something listing the canonical elements of those 275 classes, plus the class size, and the number of essentially-invariant grids for each case. It would really help to identify the classes that have no essentially-invariant grids, e.g. the class that swaps the top two rows. The remainder are the "interesting" classes: if there aren't too many of those, perhaps we'll find the energy to calculate the corresponding grid counts.

[frazer]

I've made a page as Red Ed suggested, with representatives of each class, the size of the class, and initial data that Ed has found. The page is at: http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html - I hope it is correct!

I'm not too surprised that there should be comparatively few essentially-invariant grids for the quarter turn symmetry. If I get a chance (not that likely, in the next few weeks), I'll try to analyse those classes which will have no essentially-invariant grids -- I suspect that it will be the vast majority of the classes.

Frazer

[Red Ed]

I'll try to analyse those classes which will have no essentially-invariant grids -- I suspect that it will be the vast majority of the classes.

I make it just 28 classes that possibly have some invariant grids, namely nrs: 1 7 8 9 10 22 23 24 25 26 27 28 29 30 31 32 37 40 43 44 79 86 134 135 142 143 144 145. Thankfully, nrs 1, 37 and 86 are in there 8-) ... so just 25 left to enumerate. This is definitely doable!

Here's an example, showing why class 275 has no invariants.

Code: Select all

class 275 : exp 6 : NO INVARIANTS (power=3)
 . . > . > . . . >
 . . > . > . . . >
 . . > . > . . . >
 . . > . > . . . >
 . . > . > . . . >
 . . > . > . . . >
 > > > > > > > > >
 > > > > > > > > >
 > > # > # > > > #

This means that the canonical element has exponent (is that the terminology?) 6, i.e. elt^6 = id and its third power has the effect shown. The characters are:

Code: Select all

# = definitely stays put
> = definitely changes to a different value
. = neither of the above

We can work out the #'s easily: these are just the cells not touched by the transformation. The >'s are found by looking for cells that are moved to another position in the same row, column or 3x3 box. The .'s are just the remainder.

Consider the value in the bottom right cell. This is fixed by the action of the canonical element. However, the sudoku rules mean there must be a cell of the same value somewhere in row 8 column (1, 2, 3, 4, 5 or 6), all of which change. This is a contradiction, hence there cannot be any essentially-invariant sudoku grids for this conjugacy class.

[Red Ed]

... so just 25 left to enumerate.

Uh, oh. I'm not super-confident about this. Say a transformation is interesting if it's one of my 28; and say a subgroup is interesting if it consists only of interesting transformations. I looked at subgroups with pairs of interesting non-identity generators <g,h> and found only a few interesting results:

<10,x> for x = 25, 28, 30, 32, 37, 40
<22,37> and <22,43>
<25,79>
<28,79>
<30,135>
<37,43>

The problem here is that element 86 (rotation by 90 degrees) isn't paired with anything, when it should be paired with rotation by 180, whatever conjugacy class that's in. I think I must've messed up somewhere