How many sudokus are there REALLY?

Everything about Sudoku that doesn't fit in one of the other sections

How many sudokus are there REALLY?

Postby BlueSpark » Tue Oct 04, 2005 1:26 pm

I have seen the issue of the number of possible sudokus arise here and there, and so what I have to say has probably been said. I am fairly new to sudoku and have been thinking about this issue recently.

Apparently, the number of sudokus has been calculated, and it is a very large number. It seems to me, however, that if this very large number was determined merely through calculating the numer of possible arrangements of the numbers 1 through 9 that violate none of the rules of a properly constructed sudoku (each number appearing exactly once in each row, column and 3 x 3 box) then this very large number is not equivalent to the number of possible sudokus. I would submit that the actual number might be lower by many orders of magnitude. Consider:

As we know, a sudoku need not use numbers to fill the cells. One could use a group of 9 of anything--letters, shapes, colors, faces, words, objects, or technically even sounds, textures, smells, etc. Now if we were to take a completed sudoku and replace all the numbers with, say, colors, we would not say that we have created "another" sudoku--what we have done is merely to present the same sudoku in a different way. What makes a sudoku, then, is not the particular symbols or items we employ to express the sudoku but rather the set of logical relationships expressed by the chosen symbols or items.

The same reasoning holds, it seems, even when we don't switch the numbers of a given sudoku with non-numerical items but merely switch the numbers for each other--for instance, switching all the 7's for all the 3's in a sudoku. In such a case, the original sudoku and the modified sudoku exhibit the same exact set of logical relationships between the placeholders, it's just that the particular numbers that we use have been altered. In the accepted grand total of the number of possible sudokus, however, these "two" sudokus would be considered different sudokus. Thus the grand total involves some double-counting. The grand total counts every sudoku that looks different as different, but if I am right then sudokus can look different without being so. The grand total is in a sense an aesthetic total, not a logical total.

I have not sat down to figure out the number of possible ways in which the numbers in a sudoku could be switched about without altering the basic logical structure of the sudoku. My slapdash look hinted that there are 36 possible ways of swapping out one number for another, but of course one need not stop there--you could swap the 3's for the 8's, the 2's for the 4's, and the 5's for the 9's. You could do all sorts of swapping--36 is probably just the molecule on the tip of the iceberg.

Also, we should consider more than number-swapping. Take any given completed sudoku and place it on the table and give it a quarter-turn. Have we created a "new" sudoku? No, it seems not. We are merely looking at the same old sudoku from a slightly different angle. It is not the sudoku's fault that we changed the position of our chair relative to the sudoku. The grand total of sudokus, however, does count these as different sudokus. The same would apply when giving the sudoku a half-turn or a three-quarter-turn. Four persons sitting north, south, east, and west of a sudoku could all work on it simultaneously--but they are not working on 4 sudokus. Imagine that the table is made of glass. You could have 4 additional puzzledoers situated beneath the table--but this does not create 4 additional sudokus for a total of eight, but the grand total of possible sudokus does consider these to be 8 sudokus.

So for any sudoku you come across, there exists a large set of logically equivalent ways (using numbers--there exists an infinite set when we open the door to things other than numbers) of expressing that sudoku that are counted as different sudokus in the generally accepted grand total of possible sudokus. The question "How many sudokus are there?" is not merely a mathematical question but a logical one, and one best rephrased, "How many such sets of sudokus are there?" This number will itself be very large, but it will be smaller than the total arrived at mathematically.

One last thing: it would seem that for a casual puzzledoer the fact that one presentation of a sudoku differs from another would be sufficient for saying that they are "two different sudokus." Certainly they could be done in different ways (depending on how altered they are) without the puzzledoer noticing that they are equivalent. In fact, one could probably create an entire book of sudokus simply by turning, flipping and swapping out the numbers of one given sudoku, and most puzzledoers would not feel cheated by the book (although there might be a general sense of "this book is not as interesting as others I have done" or something like that) or notice its "laziness." For someone who is interested in the fundamental structural properties of these strange little logical beasties we call sudokus, however, any consideration that helps sweep away the superficial elements of sudokus is important.

I will end with a superficial element of sudokus: has anyone out there noticed that if you assign the position values 1 to 81 to the cells of a sudoku, the values of any given number in a completed sudoku add up to 369? Does this mean anything?
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby Shinhan » Tue Oct 04, 2005 2:35 pm

As answer to your first question, there exists a 9! or 362880 ways a 9 numbers can be ordered, so thats simple to calculate.

As for the other thing, you could also try fliping by the diagonal. Or using mirror. But how many combinations does that produce? Are there any other transformations can be done that change the display, but not the content of sudoku?
Shinhan
 
Posts: 5
Joined: 03 October 2005

Postby coloin » Tue Oct 04, 2005 2:36 pm

All your points are pretty well correct.........
And they have all been painfully considered ... in the past.....and it took a lot longer to get it all together than your concise post.

But despite all this there really are a lot of 9x9 valid suduku grids. There are even more puzzles per grid - at least 10^30 per grid depending on the number of clues used. [It is not worth going any furthur on this one]

Cleverer mathematitions / programmers have counted the absolute number [Bertram] 6*10^21
http://www.shef.ac.uk/~pm1afj/sudoku/index.html

This is reduced by 9! to include number substitution.
Box swapping and shuffling in row/colums get rid of another 72^2
Rotating and reflecting gets complicated because most of the time you get a "different " grid but rarely you get the same grid.

Re Ed has worked them all out - not independantly checked....but seems right.
http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html

The rotations and reflections are complicated and my friends are still coming to an agreement of different numbers of classes of grids - ones which transpose into other grids - which I just cant comprehend.
http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=360

If you are anyone else can follow this you may be interested in the quest to find a 16 clue puzzle - see my previous post.
http://forum.enjoysudoku.com/viewtopic.php?t=605&start=225
Regards
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby Shinhan » Tue Oct 04, 2005 2:50 pm

Thought so. 9! number of permutations of numbers seemed like pretty easy thing to guess, and not likely to be forgotten by people who would want to calculate total number of valid Sudoku.
Shinhan
 
Posts: 5
Joined: 03 October 2005

Postby Pi » Tue Oct 04, 2005 3:10 pm

There are 6670903752021072936960
Pi
 
Posts: 389
Joined: 27 May 2005

Postby BlueSpark » Tue Oct 04, 2005 3:13 pm

Thanks for the responses.

Coloin, thank you for the links. I will check them out. You read my mind: I was wondering about the possibility of certain combinations of number-swapping and flipping/rotating resulting in a sudoku that was not visually any different than the original (and thus would not be counted in what I was referring to as "the grand total"). In removing double-counting we need to be careful not to double count!

Cheers
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby dukuso » Wed Oct 05, 2005 8:35 am

Coloin, let me clarify for others here, that I withdrew my
remark that I got different numbers.
Red Ed's 5472730538 looks good to me.
An estimate shows that the real number must be
close to this.
My estimate for T-invariant grids is close to Frazer's now.
Frazer once said, that he were not very certain about
this, but probably was just careful here.
I'd like to see a probability estimate from RedEd, that the
number is correct !
I guess, it's about 90%.
dukuso
 
Posts: 479
Joined: 25 June 2005


Return to General

cron