The New Sudoku Players' Forum

[Guest]

tinfoil's most recent two posts are indeed along the lines of those I had been thinking. But I'm not sure whether the asserted example works or not. (One has to be more careful here than I had been in previous attempts, as I discovered to my cost!) But there are similar things which do work. Consider

123 457 689
456 189 237
789 236 145

and exchange all the 1s and 4s:

423 157 689
156 489 237
789 236 415

Any way to fill in blocks 4-9 to make a complete grid will also be a way to fill in

123 457 689
456 189 237
789 236 415

in which the 14/41 configurations in blocks 1 and 2 are exchanged. We conclude that the number of ways of completing the first and third of these grids (which differ only in that the 1 and 4 in block 3 are interchanged) are the same. (In the example, you can do something similar with the 6 and 9.)

It looks like my catalogue for blocks 4 and 7 will also be shortened a little with the aid of this trick.

I've failed to program this correctly so far. (My program recognises where this sort of thing may occur, but then doesn't do what I want it to! Maybe I'll have time tomorrow or Saturday to fix it...)

Frazer

[Animator]

As said earlier, before I did some calcuations on the rows but they didn't turn out quite as I expect... I'll post the results, maybe someone in here can make some sense out of it...

(I used rows since that was a lot easier from a program's point of view then using the boxes, but I guess there should be no difference in the result...)

What I did was fixing one row and then calculating the possible combinations for the next row. The grid with 8 rows fixed looks like:

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

And here are the results:

Row-1: 3.628800e+05 : 362880.000000 = 9! ==> this means, that if there are no rows fixed there are 9! numbers of possible combinations to f ill Row-1

Row-2: 1.209600e+04 : 12096.000000 ==> if row1 is fixed then there are 12096 possible combinations for row 2

Row-3: 2.160000e+02 : 216.000000 ==> Row 1 and Row 2 fixed

Row-4: 1.209600e+04 : 12096.000000
Row-5: 4.000000e+02 : 400.000000
Row-6: 8.000000e+01 : 8.000000

Row-7: 2.160000e+02 : 216.000000
Row-8: 8.000000e+01 : 8.000000
Row-9: 1.000000e+01 : 1.000000

My first guess was that the total would be 1 * 8 ^ 2 * 216 ^ 2 * 400 * 12096 ^ 2 * 9!.

Since I have no idea wheter this is correct I decided to try it out on the rows, as in, what are the total number of combinations when several rows are empty:

If everything after row 6 is empty (row 1, 2, 3, 4, 5, 6 are fixed), then there are 1728 (valid) possibilities to fill in row 7, 8 and 9. This number equals 1 * 8 * 216.

But, this does not work out when the rows after row 5 are empty... As in, the total number of valid possibilites is 4068... which does not equal 1 * 8 * 216 * 8...

Empyting the rows until row 4 gives a total number of possibilites of 633312, which is not the same as 1 * 8 * 216 * 8 * 400 (= 5529600), nor 4068 * 400 (= 1627200).

At the moment I'm calculating on what it would give if it is fixed until row 4... But I really have no idea what to expect...

Can anyone make sense of it? :/

[Animator]

After posting the previous message and after waiting a bit I decided to try another thing too: fill row 4, row 5 and row 6, and see how many combinations it can have...

That test resulted in 35057664 (3.505766e+07) combinations... which is also not the same as 12096 * 400 * 8 (= 38707200)...

My best guess now is that the filling in row 4 till 9 (as in, having the first 3 rows/blocks fixed) will result in 35057664 * 1728 combinations... (60579643392).

If this number is correct then the other thing I'm running will finish in 7 or 8 days... (assuming an average of finding 100000 solutions per second).

(Small side note, in an attempt to increase the average solutions/seconds I stopped the main program I was running after finding 1.072692e+11 (107269200000) in 1117082 seconds (about 12 days))

[Guest]

"That test resulted in 35057664 (3.505766e+07) combinations... which is also not the same as 12096 * 400 * 8 (= 38707200)... "

I suspect that the difference is because the number of possibilities for, say, row 6 when rows 1-5 (incomplete blocks) are fixed depends on the particular values chosen. Whereas when whole blocks are fixed, eg rows 1-3, or 1-6, the answer is valid.

[Guest]

I've finally got around to reuniting the runs I did on my home computer and the runs I left going on my work computer overnight. Here are the results so far. In all cases, the first two blocks were

123 478
456 139
789 256

Various blocks 3 : possible ways to complete to a grid:

569/278/134 : 97961464
569/287/134 : 97539392
568/297/134 : 98369440
586/279/134 : 97910032
596/278/134 : 97961464
596/287/134 : 97539392

(Note that the coincidence between the number for the first and fifth, and the second and sixth, choices, is due to the phenomenon I mentioned earlier.)

The average number of the first four is 97920082. If this were really the average (but there are many more cases not yet done!), then the total number of Sudoku grids would be 6684406103696835870720, or about 6.68x10^21. Before running more tests, I'll try to reduce the list of things I count, so that I don't get these duplicate answers (which have already wasted about 72 computer hours...).

Frazer

[Guest]

I've finally got around to reuniting the runs...
... snip...

1) I'm sure your results are right, and this completely invalidates my recent posts. I am surprised that exchanging two values in block 3 actually makes a difference in the number of valid solutions, as I assumed that there would simply be a 'symmetrical' (not really the right word) re-distribution of valid solutions.

2) How exactly are you computing your integer values to so many significant digits of accuracy? There's a few checks I would like to employ where Excel 'roundoff' is making my answers seem identical when your results show that they obviously are not.

[Animator]

My best guess now is that the filling in row 4 till 9 (as in, having the first 3 rows/blocks fixed) will result in 35057664 * 1728
combinations... (60579643392).

Again, this is incorrect...

If blocks 1, 2, 3 are:

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

Then there are 7802998272 (7.802998272 * 10 ^ 9) possibilities to fill in blocks 4-9.

This one however can be diveded by 1728 (the number of possiblities to fill in blocks 7, 8, 9), and results in 4515624...

Can anoyone make some sense of that number?

[Guest]

Still can't get my reduction to work properly, even after a couple of hours' work. Maybe over the weekend...

In response to tinfoil's question (2), you can just use the Windows calculator (on XP, it's on Start > All programs > Accessories; choosing Scientific under View gives more functions). There are other free programs around too, but I think the calculator should be enough.

(I think I mis-hit a key when I worked out the average earlier - it should be 97945082, giving a prediction of 6686112701048259870720.)

Frazer

[Guest]

My guess: 2.8 x 10^25.

Given any digit, there are (3!)^6 = 46656 ways of filling the grid satisfying the rules. Given a filling with one digit and a filling with another, the probability that the two fillings are compatible is roughly (8/9)^9 = 34.6% (in each of the nine boxes we check that the two digits aren't in the same square).

Now, we choose a filling for all nine digits, (46656)^9 possible ways. The probability that these fillings are compatible is (.346)^36 (since there are (9 choose 2) = 36 choices of pairs of digits to check compatibility). Multiplying these two numbers yields the answer of 2.8 x 10^25.

This, of course, is a rough estimate, as I have assumed a lot of independence that is not true. But I think it is a reasonable guess.

Has anyone tried this method using a computer? That is, filling in all the 1's first, then filling in the 2's, and so on, rather than filling the upper left box with 1-9, then the upper middle box, and so on?

We may assume (by multiplying by 9! afterwards) that the upper left box is 123, 456, 789, which cuts down the possible fillings to 46656/9 = 5184 for each digit. Furthermore, we may choose exactly where the 1's go (by later multiplying by 5184). Then we eliminate the fillings for the digits 2,3,... that aren't compatible with the filling of 1's, leaving about (8/9)^8 * 5184 = 2000 possible fillings for each digit. With an explicit list of the 46656 possible fillings, it is simple to check whether two fillings are compatible (just list the squares the digits occupy and see whether any are the same).

Is this a practical method?

[coloin]

Su bloko has directed us to boards.straightdope.com [an interesting message board !]

Can I congratulate Su bloko aka InvidiousCourgette for his excellent posting.

I think the difficulty in solving the number of unique solutions available in sudoku is apparent and we are waiting for the next 8 ? years for the computors to number crunch it. The maths is interesting and complicated.

However the posting below whilst not exact gives us an idea of where were are now. We may well be onto other things when the real answer comes out.

Can I repeat his posting on this board for all to see.

He writes
"By filling in the mini grids 1, 5 and 9 randomly you can set a program to brute force the number of valid ways to fill in the remaining mini grids. The number you get turns out to vary depending on how you filled in those first three grids. I tried it 25 times with 25 set of randomly filled in grids (1, 5 and 9). I got a figure of 133700 as the average number of valid ways left to fill in the remaining grids.

It is then possible to say that the total number of valid sudokus, based on the average calculated by my 25 trials, is = 133700*9!^3, or 6.4 * 10^21

Note that when I say "randomly" filling in the first three grids, I mean random in the sense that each grid has all the numbers 1 to 9 put in them, but in a random order."

Brilliant I say.

It approximates well to the other methods currently postulated.


Other facts gleaned from sudoku.com noticeboard are

Total number of 9x9 squares = 9^81 [9 to the power of 81] = 1.966x e^77 [a very big number]

an example of this square would be
999999999
999999999
888888888
555555555
333333333
333333333
777777777
999999999
111111111 [any number anywhere]

Total nuber of 9 [3x3] boxes with 1-9 in them
9!^9 = [9 factorial to the power of 9] = [9x8x7x6x5x4x3x2x1] to the power of 9 [ about 1.0911 x 10^50]

an example of this square would be

123123123
456456456
789789789
123123123
456456456
789789789
123123123
456456456
789789789


Total number of 9x9 Latin squares = [Bammel and Rothstein in 1975 ] about 5.525 x 10^27

an example of this square would be
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

None of the above squares are "valid" sudokus !


Total number of valid sudukus is estimated to be less than 6x10^21 by various methods

Total number of absolutly unique sudokos may well be reduced by :

Of the total [6x10^21] - 9! [362880] are essentially identical by number substitution
[there are 362880 ways to fill in box 1]

Of the total [6x10^21] - potentially 8 x 6^4 [10368] are essentially identical
- by rotation and or reflection - 8
- number shuffling in rows and columns - 6x6
- box shuffling horizontally and vertically - 6x6

I say potentially as this is controversial at present and may be an overestimate.

If the above is correct then the exact answer is a multiple of 362880 x 10368 [!]

That is where I think we are - I hope this is useful to others and correct as we stand.

Credit goes to the respective contributors on the forum.

[coloin]

Del

[Guest]

I have a program that should be able to solve the problem (how many valid filled Sudoku configurations are there?) within a bit more than a month on a single PC (estimated), or even faster given more CPU power:

http://www.inf.tu-dresden.de/~bf3/sudoku.cc

The program first fills the first 3x3 box (with a fixed numbering reducing the number of solutions by a factor of 9!), the first row (with one out of 10 possible labelings out of a total of 720, reducing the number by a factor of 72) and the first column (another reduction by a factor of 72) and then proceeds with an exhaustive enumeration of all remaining possibilities.

Enjoy,

Bertram

[coloin]

tannedblondbloke previously worked out that x = 56

This may well suffer from the "fundemental" problem of counting possible
combinations which result in "invalid" sudokus.

However it is an upper limit.

I am prepared for a bubble burst here.

Please enlighten me.

[coloin]

del

[coloin]

del