One for the combinatorics gurus

[groza528]

I came up with this question yesterday. I don't know the answer. Frankly, the answer doesn't interest me terribly, but the solution does... I want to know if there is an elegant way to arrive at a numerical answer. Just to satisfy my own curiosity.

How many legal solutions are there to a blank sudoku grid?

[Sentran]

My immediate response would be 9! (with the ! meaning factorial, not just a vehement 9), which is 362,880 possible combinations.

To think through logically...
If it was a grid of 1 number, there is only 1 possible outcome.
If it was a grid of 2, there are 2 possible outcomes. (2*1)
If it was a grid of 3, there are 6 possible outcomes. (3*2*1)
And so on to 9.
_________________
Sentran
"Speaking of double negatives, I haven't read greylab yet today." - Lifeinmomland

[groza528]

I'm referring to a full 9x9 grid, not just one section of the grid. If I were only trying to fill in a 3x3 grid, of course it's 9!, but to fill in the full 9x9 you have to start with the 9! and then fill in the other rows/columns/sections in a constricted manner.

[Zag]

Hmmm. Interesting problem. This would be my approach:

Consider the word "square" always means one block of 9 numbers, so a sudoku has three rows of three squares.

Take the top left square. You can place the numbers 1-9 in those positions any way you like, so that gives you 9! combinations.

Now consider the square to its right. This has the same 9! combinations, but many of them are now illegal because of conflicts with the first square. I was hoping something would hit me on how to enumerate the illegal positions, but nothing is. The big problem is the large number of overlaps. Ok. Here's the best I have

The number of illegal positions due to exactly 1 number in the top row being illegal (and possibly more in other rows, but only 1 in the top) is 3 * 3 * (6C2) * 6! I think. That's 3 numbers that can make it illegal * 3 positions * the number of combinations for 2 numbers that wouldn't be illegal * the number of possible combinations for the remaining six numbers. You could do a similar calculation for the combinations that are illegal due to exactly 2 numbers in the top row, and the number for all three in the top row being illegal (3! * 6!).

Then you have to count the number of ways that the second square can be illegal because there are 0 illegal values in the top row and exactly 1, exactly 2, and all 3 illegal in the second row. Note that once the first and second rows (of this second square) are legal, the last row must be, as well.

Phew! On to the third square, which will be easy. There are (3!) ^3 legal combinations of this block, given the first two blocks.

The first square of the middle row of squares will have the same number of combinations as the second square of the top row.

The middle square is tricky, I haven't worked that one out, yet.

Once you have that, the rest are pretty easy, and are left as an exercise for the grad student.

[groza528]

I disagree with the last line; I'm not convinced that the end is as easy as you say.

Consider the smaller example, two rows of two 2x2 squares.

4! = 24 ways to fill in the upper left, which is pretty arbitrary. Let's assume we fill in

[Sentran]

[L'lanmal]

One approach would be to calculate the odds that a randomly chosen Latin Squares meets the blocks of 9 requirement, and multiply by the number of 9x9 Latin Squares. (Of which, it is "well-known" that there are 5,524,751,496,156,892,842,531,225,600. Link http://en.wikipedia.org/wiki/Latin_square )
But with no known closed-form formulae for number of arbitrary sized Latin Squares, a systematic formula for number of valid Sudoku grids from that method seems unlikely.

The number for 9x9 case in particular is known (published 2005), but that paper (Bertram Felgenhauer and Frazer Jarvis) is probably not the elegant solution you are hoping for.

[LordKinbote]

[lostdummy]

I think solution is 9!*6!*6!*3!*3!*3! [/b], or around 10^13

Way I got to this number is to see in how many ways we can chose numbers starting from one corner, for example top left corner:

9 8 7 6 5 4 3 2 1
6 5 4 3 2 1
3 2 1
6 3 - 3 2 1
5 2
4 1
3
2
1


For top row in top left box, 987 means we can chose all 9 numbers for first position, but only 8 for second (since 1st number is chosen in same row), and one less for 3rd (so 7). Second row in same box is already limited by those 3 selected numbers ans start from 6 (so 654), and same for third row (321).
For top middle box, upper row continue as 654 (limited by 3 numbers in same row in first box), but second row is now constrained both by those 3 numbers in this box and also by 3 numbers in left box, so it starts from 3 (321), and rest is forced (1). Top right box start from 3 in upper row , since there are already 6 numbers in upper row, so 321, and rest is forced. BTW, all empty spaces are also forced (so "1").

Same logic is applied to left middle box (only vertically), then left bottom box.

Interesting is middle box, where we still can make combinations - first number is constrained by 3 numbers above it and 3 to left, so it starts at 3 (321). Rest is forced.

That result in picture as above, and number 9!*6!*3! (horizontal top boxes) * 6!*3! (vertical left boxes) * 3!(middle box)= 9!*6!*6!*3!*3!*3!

BTW, I did not consider symmetries here to get "number of unique sudokus" - this is solution for total number of valid sudokus.

*EDIT* After some thought, there could be problem with this solution. For example, in second row of top middle box (321), it is not clear that first position have only 3 possible values, since numbers in upper row of that box can duplicate with some or all of 3 numbers in row to left and that would leave 6 possible choices in such case ... or still only 3 choices if numbers do not duplicate.

[lostdummy]

Heh, my last sentence from previous post started me thinking on this "symmetry" problem:

What is exactly symmetry, and why would we consider it at all here?

Common sense response would be that if we can create new valid sudoku from existing one by just applying mirroring or rotating, we could consider those to be "same" and not count in number of "unique" sudoku puzzles.

Now, in that "common sense" definition key word is "unique", and that would mean here : "can not be derived from other unique sudoku with some transformation"

And again, key word there is "transformation" - clearly mirroring and rotating are such transformations, but are they all ?
As I mentioned, just doing permutation of vertical 3x3 boxes will also result in valid sudoku. Is such transformation also as valid as mirroring here?
And where do we stop?Computer program who is searching all possible sudokus starting from one "unique" sudoku position is also transformation.

Probably some common sense approach would be to say that only "easy or straightforward" transformation are valid to determine uniqueness, but that is too subjective definition. One definition that could be more precise would be:
Any transformation that can be defined just by changing position of any of 9x9 cells

That means if we label every cell in 9x9 grid with number 1 to 81 (1 top left, 9 top right, 81 bottom right), then we can say that for example mirroring across vertical line will put number from original cell 1 at new cell 9, 2 at 8 ... 73 at 81 etc.

Therefore vertical mirroring can be described by list of 81 numbers, each defining where "original" number from that cell will end up ( in above example: 9,8,7,6,5,4,3,2,1,18,17...81,80,79,78,77,76,75,74,73)

Clearly computer program searching all sudokus can not be described in such way, so it does not count as valid "transformation". But bonus question here is:

What are all valid transformation for sudoku, and how much they would reduce number of unique solutions?

Some of transformations that I saw so far:
2x vertical mirroring
2x horizontal mirroring
4x rotations
3!x permutations of whole vertical box groups
3!x permutations of whole horizontal box groups
3!*3!*3!x permutation of 3 vertical columns within each of 3 vertical box groups
3!*3!*3!x permutation of 3 horizontal rows within each of 3 horizontal box groups

Now, most of those transformations are multiplicative, meaning we can apply both vertical mirroring and one rotation, or permutation and rotation etc... so total number of "derived" sudokus from one "unique" sudoku would be close to multiply of all of above.

So just going by those numbers listed, it would mean that one unique sudoku can generate 2*2*4*6*6*6*6*6*6*6*6 derived sudokus.

BUT some permutations when combined can get same end result. For example, multiplied 2x horizontal mirroring and 2x vertical and 4x rotations suggest total of 16 derived (including one unique) sudokus, but rotate twice get same result as mirror vertical and horizontal, or rotate three times and mirror vertical gets same result as rotate once and mirror horizontal etc .. so total number of different derived sudokus using both mirrorings and rotates is actually 8 .

I dont know if other listed transformations above also have similar duplication effects, or if in fact those are all valid transformations. IF they were, number of derived sudokus from one unique would be around 8*6^8, and number of "unique" sudokus would be 9!*6!*6!*3!*3!*3! / (8*3!*3!*3!*3!*3!*3!*3!*3!*) = 9!*6!*6!/(8*6^5) = 3024000

BUT I suspect that number is not correct, ie I suspect that both some of other transformations mentioned above when applied in combination get duplicated results similar to mirror/rotate (which when corrected would reduce number of derivations from one unique sudoku and increase total number of unique sudokus) , and also its possible that some other transformation that I did not think about exists (which then would inclrease number of derivations and reduce number of unique sudokus)

[lostdummy]

I did some counting on how many there are different transformations from those listed above, and it turns out there are 2*3!^8 (=3,359,232) of those.

In fact, I found that following transformations from my above list duplicate with each other:
- vertical mirroring is subset of combination of vertical box and column transformations
- horizontal mirroring is subset of combination of horizontal box and row transformations
- rotation by 2 or 3 is combination of rotate by 1 and above horiz/vert box/row transformations

So reduced list of valid non duplicated transformations is:
- (2) rotate to right by 90 degrees
- (3!) permutations of whole vertical box groups
- (3!) permutations of whole horizontal box groups
- (3!*3!*3!) permutation of 3 vertical columns within each of 3 vertical box groups
- (3!*3!*3!) permutation of 3 horizontal rows within each of 3 horizontal box groups

That means if we apply all those transformation on unique sudoku position, it will result in 2*3!^8 (=3,359,232) sudokus.

Of course, that presume only those transformations that I listed before - maybe someone can think of some other transformation that would result in non-duplicated valid sudokus ;p

[L'lanmal]

The most natural transformation I can think of on a sudoku is conjugation. (e.g. Replace all 1s with 9s and all 9s with 1s.) This does not change the structure what-so-ever (or influence the reasoning needed to solve one), just the labeling conventions.

I imagine this will overlap greatly with rearranging rows and columns.

[Thok]

6670903752021072936960

Gotten by using Sloane's integer series page

The general problem is fairly wild: once you factor the obvious factors, there isn't much structure. Wikipedia claims the number of 16x16 sudokus (with 16 4x4 squares) is still an open problem.

[lostdummy]

[Zag]

That little bit of difference sounds more like a rounding error to me.

[Thok*]

[lostdummy]

[Thok*]