The New Sudoku Players' Forum

[Guest]

I am a muppet. Well spotted IJ.

Everywhere I wrote 6!, I really meant 6, ie 3!

So the answer is 9! x 56^6 x (3!)^12 = 24,361,621,955,711,200,000,000,000

Does that look more reasonable?

9! x 56^6 x (3!)^12 = 24 361 621 955 711 196 022 702 080
24,361,621,955,711,200,000,000,000 is obviously incorrect as the above has only one factor of 5 and so cannot be a multiple of 100

But I like this method and this number.

This would mean that any attempt that starts by filling B1, B4 and B9 is doomed to failure as this would imply a multiple of 9!^3 which is a multiple of 1000. - So my previous post about another factor of 25 is wrong

Tim.

[coloin]

All this is really fasinating.

Please could you paste a summary of where we are please.

Is the non-uniqueness factor 9! ?

Rotational and Mirror image allowances arnt clear as far as I can follow.

Thanks in anticipation

[Pappocom]

I haven't been following this thread too closely, but I agree that it must be hard for someone who is interested in the subject to follow where you have got to, so far.

Would one of the regular contributors to this thread care to do a summary (is that possible?), and use the summary to start a new thread perhaps?

- Wayne.

[Guest]

I've now brute forced B1+B2+B4+B5 (took about 1 hour on a 4GHz pentium) and I get:
9!*25609120*48*48 = 21411158320742400

Interesting points to note here: This is a multiple of 5^2 but is not a multiple of 7^2

Brute forcing the entire grid ought to be feasible and would easily distribute.
Very rough ballpark estimate is 65000 CPU hours (allow a factor of 10 if you really want to go this path although I think there would be another factor of about 10 I could easily optimize out)

If anyone is interested in my code as it stands:

http://www.woodall.me.uk/sudoku_count_opt.c

Tim
.

[Guest]

The breakdown of filling B5: given B1,B2,B4

9!*6084 * 48 * 48 have 384 solutions
9!*12204 * 48 * 48 have 392 solutions
9!*36756 * 48 * 48 have 400 solutions
9!*224 * 48 * 48 have 432 solutions
9!*8236 * 48 * 48 have 448 solutions


Not sure if this might help in extending other solutions or not.

Tim.

[Guest]

Tim's computations are very interesting indeed. I've just finished writing a Perl program to do a brute force search through the whole grid. Unfortunately, I'm a terrible programmer, and mine will take more than 65000CPU hours to run! 65000 hours = 2500 days = 7 years, more or less. I think I estimate mine at nearer 70 years (although it will also distribute well)... I really must learn to program better sometime...

(Apologies for my typo in the computation earlier -- I was using a calculator program at home which has no cut-and-paste facility!)

On the other hand, I can run some simulations now, and predict an approximate answer. On the basis of only a few simulations thus far (choosing blocks 2, 3, 4 and 7, then running through all possibilities for block 5, and then all those for blocks 6 and 8, and seeing whether block 9 can be completed), I would so far predict around 6.8 x 10^21 full grids. But I really haven't done enough trials yet to be confident of this. For each configurations of blocks 2, 3, 4 and 7, all this takes about 5 seconds to run. I've reduced the number of configurations to about 500 million... I only finished the program within the last couple of hours, so I'll run some more extended simulations overnight and over the next couple of days, and report back.

Frazer

[Guest]

Think I've made a breakthrough in how to calculate this - thought of it in bed so haven't tried coding it yet.

step 1 - fill B1 - only need to consider one case and then multiply the total solutions by 9!

step 1 - fill B5!

There are only 5 cases we need to consider
111 210 111 300 300
111 102 201 021 030
111 021 021 012 003
(Where each number says how many to select from the same row in B1 to go in the same column in B5)

For each of these we have to multiply the final result by
6^3*6^2, 6^3*3^3, 6^3*3^3*2, 6^3*3^2, 6^2 respectively.
(Exercise for the reader to explain these numbers and show that the sum is 9!)

Then for each of these we find all the cases for B2 and B4. There are at most 252 for each of these we need to consider (think it is a lot lower)

So we now have approx 300000 cases for B1,B2,B4,B5 which we then need to brute force for the rest.

Tim.

[Guest]

There are only 5 cases we need to consider
111 210 111 300 300
111 102 201 021 030
111 021 021 012 003
(Where each number says how many to select from the same row in B1 to go in the same column in B5)

Think I spoke too soon. Think it is max 25 cases to consider and counting the frequency isn't quite as easy. Need to consider the same matrix in B4 for the breakdown.

Tim.

[Guest]

Never post when you are half asleep

For each of these we have to multiply the final result by
6^3*6^2, 6^3*3^3, 6^3*3^3*2, 6^3*3^2, 6^2 respectively.
(Exercise for the reader to explain these numbers and show that the sum is 9!)

Tim.

This was wrong too:

Here's the workings:

Code: Select all

111 21. 111 3.. 3..
111 1.2 2.1 .21 .3.
111 .21 .21 .12 ..3

666 666 666 666 666 Ways of rearranging the numbers in columns
321 311 321 111 111 Ways of selecting the numbers
321 311 311 311 111
321 131 131 311 111



6^3 6^3   6^3   6^3 6^3 Reorder numbers in columns
6^3 3^3   3^3*2 3^2 1   Ways to pick numbers
1   6     6     6   6   Reorder cols (matrix must be unique)
1   2     3     3   1   Reorder rows (matrix must still be unique)

6^2 3^3*2 3^4*2 3^3 1   Divide by 6^4

36  54    162   27  1

36+54+162+27+1=280

280=5*7*8
6^4=2*3*4*6*9


so the factors are
6^6
6^4*3^3*2
6^4*3^4*2
6^4*3^3
6^4

QED.

Expanding out one case above

210 201 120 102 012 021
102 120 012 021 201 210
021 012 201 210 120 102

210 201 120 102 012 021
021 012 201 210 120 102
102 120 012 021 201 210

[Guest]

Good luck to Tim with your calculations! I thought I'd summarise current progress from my end, such as it is.

My program will have finished now calculating all possible Sudoku grids with one specified set of blocks 1-3 (I set it running on my home computer late on Wednesday night, and when I set off for work this morning it had finished 90% of the calculations). Unfortunately, there are quite a lot of possibilities for these blocks, and each will presumably have a different number of grids. The problem is now to work out how many different sets of blocks 1-3 need to be treated. By manipulations (relabelling, permuting columns etc.), I've got the number down to about 22000, each taking about 36 hours to run (that's under 100 years, but not by much...!) I thought of a way which will probably reduce 22000 to something smaller, but I don't know yet how much.

(As I mentioned in previous posts, I'm precomputing all possible blocks 4 and 7. Then I'm computing all possibilities for block 5, working out the possible blocks 6 and 8, and seeing whether block 9 can then be completed.)

Based on the numerical data so far (although other choices for blocks 1-3 will give different answers), I'm getting a prediction of around 6.6 x 10^21 for the total number of blocks, pleasingly close to tinfoil's prediction of 2 or 3 weeks ago. Of course, while this is based on quite a lot of data, it still only represents less than 0.01% of all possible tests...

I'll give more complete numerical data later.

Frazer

[Guest]

If a 9 x 9 grid can be filled a total of "T" ways using nine each of the digits "1" through "9", and a truly random program produces a valid Sudoku combination "N%" of the time after a large number of iterations, then:

How many of the of the solutions so far indicate a number approximating to T x N / 100?

Paul

[Guest]

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

[su bloko]

We've had two different heuristic methods both suggesting 6 x 10^21 as an approximate answer.
Frazer

Wow, what an interesting problem. I thought I would take a fresh stab at it and see where I got. Well, I thought I hit upon a good technique, but ....

I made the assumption that the 1st, 5th and 9th grids could all be filled in independently. There are (9!)^3 possible ways to do this. Then I figured you could brute force how many ways there were to fill in the rest of the grid for for a few of those combinations. I was hoping that any of the (9!)^3 initial start positions would have the same number of ways to complete. Failing that, an average would point to the total number of combinations.

I first tried this start point for my brute force approach:

123 --- ---
456 --- ---
789 --- ---
--- 123 ---
--- 456 ---
--- 789 ---
--- --- 123
--- --- 456
--- --- 789

My algorithm churned out 283 576 different ways of legally filling in the rest of the grid.

Then I changed grids 5 and 6 to:

123
468
579

and

258
713
496

Result: 174937 combinations. Oh well

Then grid 5 to:

468
123
579

Result: 174937 combinations. Interesting that the same number appeared twice.

Anyway, if I take the average of my three tests, I get a figure of 10.1 * 10^22 as an approximation to the total number of possible solutions. A little higher than 6 * 10^21, but in the same ballpark.

[su bloko]

I get a figure of 10.1 * 10^22 as an approximation to the total number of possible solutions. A little higher than 6 * 10^21, but in the same ballpark.

That should read I get a figure of 10.1 * 10^21

[Guest]

Work is in progress. I have set my brute force machine to refine an approximation. I am working on an absolute technique in parallel. Gahh, I have already spent 10 hours on this!