The New Sudoku Players' Forum

[Guest]

Dear forum members,

I'm somebody who has recently developed an interest in the mathematics of sudoku, and a long-time Wikipedia contributor.

Congratulations to Bertram on his discovery of the number of legal sudoku solution grids, and to those whose symmetry discoveries helped him to make the search feasible. I'd just got started looking into the problem and was working along similar lines though I was a long way behind; it's both nice to know I was on the right track and a bit disappointing to find that somebody's already beaten me to it

With respect to the Wikipedia entry, while it's extremely timely to have the solution in the 'pedia before it's been published anywhere else, a forum post is not exactly the first choice of reference (for reasons of permanence and convenience to readers who might wish to learn more).

Additionally, given the burst of interest in sudoku, it seems to me that this discovery might well be of some interest to the British newspapers, at the least.

Could those people responsible for the work that led to the calculation (including the estimates that indicate that the calculation is in the right ballpark) put together a document summarising their work (ideally, in the form of a technical report), and place it somewhere permanent, and then replace (or augment) the Wikipedia link to this forum with a link to that report?

Also, is somebody planning a press release on this topic?

[Animator]

Don't let this thread stop you from doing your own calculations...

The number hasn't been verified... So please continue your calculations and see where you get...

[Guest]

In response to Robert's point, Bertram and I have written the first draft of a short (6pp) article and will be posting it on a website when a more final draft is written.

While I've verified with my own program some cases of Bertram's computations (they all agree!), it takes such a long time for my program to run that this is still a long way from complete. If any others would like to help verify these calculations, please feel free to do so!

Frazer

[Guest]

In response to Robert's point, Bertram and I have written the first draft of a short (6pp) article and will be posting it on a website when a more final draft is written.

While I've verified with my own program some cases of Bertram's computations (they all agree!), it takes such a long time for my program to run that this is still a long way from complete. If any others would like to help verify these calculations, please feel free to do so!

Frazer

I have no objection if anyone wants to use any part of any of my posts to document this effort.

Kevin Kilfoil

[Guest]

It has been an excellent exercise for you very clever people - and I am pleased to have been in on the excitement of trying to generate the number of solutions - admittedly many many years off the pace !

Does the fact there is a large prime number as a factor in the solution preclude a mathematically derived answer rather than a getting a computer to slug it out. ?

And how are we going to prove this number ? [Animator says]

Well......

Varius people have discussed the effects of number substitution,rotation,reflection and shuffling etc so incorporating we have :

Number substitution = 9!
The number of rotational reflective elements = 8
Number shuffling in the rows and columns gives you 6*6
Row shuffling [I think still stays valid] gives you a further 6*6

Please correct me
a if I have got this wrong
b there may be some unforseen double counting

But not unsurprisingly all these factors are in Bertrand's number.

So the actual number of truly unique solutions is reduced but in no way detracts from Bertrand's massive computation.

Also

If we coulld calculate it using a method which considered the boxes in a different order we could arrive at the answer and confirm it.

Which order of boxes did Bertram use ? Did he even use an order of boxes ? Of did he fill out a 123 row of boxes , throw in all the 1s, perhaps a few 2s then ignore symetries which resulted in constraints, reduce the number of calculations by sheer brilliance and then finally remembered that the 9s picked themselves.

It is excellent especially as some were predicting it was going to take years !

I look forward to seeing the full script and the verification when it comes out.

Regards

[Guest]

Generalizing one of the equivalences then reduced this further to 71. I've actually redone the computation with this set of 71 configurations and re-obtained the same result.

[snip]

P.P.S. For those who are interested, the programs that I used and their output for the two calculations mentioned above can be found at http://www.inf.tu-dresden.de/~bf3/sudoku/

I looked at your 'results' files with interest, and I was wondering if you and afj did any sort of 'post-mortum' to see if patterns could be spotted and how many of the 71 configurations actually lead to a unique number of subsequent valid solutions (i.e. an overall histogram), as this may reveal more 'hidden' equivalencies that reduce 71 to some smaller number?

I am still bemused that such a large prime number appears in the solution, as this suggests (as already noted in a prior post) that we were NEVER going to arrive at the exact solution using logic and cleverness, and that brute force was going to have to be employed at some point.

[Guest]

I looked at your 'results' files with interest, and I was wondering if you and afj did any sort of 'post-mortum' to see if patterns could be spotted and how many of the 71 configurations actually lead to a unique number of subsequent valid solutions (i.e. an overall histogram), as this may reveal more 'hidden' equivalencies that reduce 71 to some smaller number?

afj has noted that only 44 configurations lead to unique solutions (based on Bertram's computations)

[Guest]

In response to the previous post, I'll recap briefly on our method:

(1) Fill in blocks 1-3.

Originally Bertram was just filling block 1 and the top row of blocks 2 and 3, but my contribution was to point out that one can exploit many more symmetries by filling in all of blocks 2 and 3. The idea now is to use these symmetries to show that each such configuration of blocks 1-3 is equivalent to one in a very small list of configurations. (By equivalent, I mean that they can both be completed to a full grid in the same number of ways.)

We can reduce the list we have by several methods. Firstly:
(a) Relabel the entries.
(b) Permute the three rows of the configuration.
(c) Permute the three blocks of the configuration.
(d) Permute the three columns within any block.

By relabelling the first block, and then permuting the columns of blocks 2 and 3, and then exchanging blocks 2 and 3, one can get down to 36288 possibilities. But we can do better by looking at more permutations; for example, if we allow ourselves to carry out all permutations as in (c) and (d), and then relabelling to get block 1 as 123/456/789, one gets down to 2051. Allowing also permutations as in (b) gets down to 416 [if you program this sensibly -- I was down to around 1000 here, but Bertram had a better way to store and program the equivalences].

But there are still more equivalences, as I mentioned in my reply to tinfoil much earlier. If the configuration has a 2x2 subrectangle with a..b above b..a, then, as I pointed out there, we can exchange a..b with b..a, and keep the rest of the configuration the same. Bertram programmed this in addition to the other reductions above, and got the answer down to 174 possibilities [in practice, the first version of programming these equivalences got down to 306, which is the point that the program was first run].

In fact, Bertram later improved this by observing that the same holds if there is a 2x3 subrectangle a..b..c above any permutation, e.g., b..c..a -- and for any 2x4 rectangle. Incorporating all these symmetries takes you down to testing just 71 possibilities for blocks 1-3.

I'd observed most of those symmetries and how they worked if one starts with the first three blocks, but Bertram programmed them extremely efficiently (which I hadn't), and wrote a program to do an exhaustive search to complete a given configuration to all possible full grids which worked in less than 2 minutes (compared with my 36 hours!). For the same reason that one can get a factor of 72 by permuting the columns of blocks 2 and 3, and possibly swapping them, Bertram's program then fixes one of the 10 choices for the left column of blocks 4 and 7. Then Bertram's program seems to fill in the remaining numbers in a slightly unexpected (to me) order, but which turns out to be remarkably efficient.

So using my symmetries sped up the algorithm by a factor of around 100 (nearly 500 in the end). [I'm sure that the same methods would quickly have struck Bertram!] And then Bertram's amazing programs gave another factor of 1000 on my programs...

How to prove this number? Well, we hope that other people are going to verify it independently. At least one other person is currently doing so, and will hopefully confirm the answer soon... or not? We shall see... I gather that the method is along the lines of that proposed by Brian, filling in the 1s, then the 2s and so on.

In the previous posting, there is some double counting there; a rotation by 180 degrees can also be achieved by permutations of rows and columns. Also, the existence of a large prime doesn't preclude the existence of a nice combinatorial method; one might be able (simplifying somewhat) to show that there are essentially two methods of constructing grids [in practice, it will be many more!]. Both of the two methods might have easy and nice answers, but when you add them, a large prime appears. For example, if one method has 250 solutions, and the other has 144, say, then the sum 394 has a factor of 197. (On the other hand, I'm pessimistic that there is such a nice method.)

This turned into a rather less brief post than I had originally intended!

Frazer

[coloin]

The main thing that botters and confuses me is this:
...........
............
Then the number of valid solutions drops to 271012...

More and more I'm beginning to believe that the only way to get the answer is to do a brute force on it without making a single assumption...

Animator -
Thank you for your comments and help in this exercise over the past few weeks.

Now please can you tell me what program you use which tells you how many solutions there are for a given uncompleted grid - and how does it work ?

You were correct in surmizing that there was a problem with box 9 in my box159 method.

This has been confirmed by there being only one 9! in Bertran's number.

This means that there must even be some ways of completing box1- box5 which end up there being no valid solution - never mind trying to work out what the numbers of the box1-box5-box9 combination were.
And we [sorry I] all thought they were exclusive of each other.

Have you got an example where you can fill in two boxes say b1 and b5 and your program - instead of coming out withan answer of more than 270,000 it says there are none?

This is also confirmed when you add up all the numbers in Tims 384-392-400-432-448 solutions answer - they are less than 9!^2 . And that is before you loose with other constraints from subsequent boxes.

I am sorry I took to guessing - but I was never going to be able to do a computor solution - the idea that the constraints would balance each other is ludicrous. Looking back I think I was going over ground months back and the smart boys, you included, had realized that we were always going to have to number crunch it.

Regards
Coloin

[coloin]

The result of the computation is

6,670,903,752,021,072,936,960 = 2^15 * 3^8 * 5*7 * 27,704,267,971 = 9! * 72^2 * 2^7 * 27,704,267,971

I wonder some of the factors of 2 can be explained by symmetries.

Thankyou afj for your explanation of the symetries reducing the number of calculations - it seems obvious now - that just interchanging a pair of numbers can give you the same number of solutions - thereby reducing the total number of calculations. Indeed you say now that this has amazingly been reduced to 44 configurations.

Very very good.

Interesting point regarding the rotational and swap symetries - these were included initially to reduce your number of calculations - of course. This means that all the rotational symetries and row swaps are naturally included in the final answer as we always thought.

My estimate was
symetries /rotation was 8 =2^3
row swaps 36 = 2^2*3^2
box swops 36 = 2^2*3^2

8*36*36 = 10368 = 2^7* 3^4

yes the double counting is there I think - a 180 degree rotation is equivilent to a column box swop plus 3 column swaps plus a reflection.
I cant quite compute the implications of this off the top of my head - but there almost certainly will be others.

Therefore this 10368 is an overestimate.

There may be more symetries that we havnt thought of - maybe ones "similar" to what you used in reducing the number of computations.
[potentially 64 plus the unknown [yet] double counters above]

It doent prove anything though the answer was always going to be a number [n] which represents the number of absolutely unique solutions
times 9!
times the number of ways you can represent any one effectivly similar grid.

Regards again.

[Guest]

How to prove this number? Well, we hope that other people are going to verify it independently. At least one other person is currently doing so, and will hopefully confirm the answer soon... or not? We shall see... I gather that the method is along the lines of that proposed by Brian, filling in the 1s, then the 2s and so on.

Frazer

Have you considered cross-checking your own answer via filling in different blocks first? For example, if you left B1 as given, and then found the assorted permutations for Blocks 2 and 4, you'd have a dramatically different goup of combinations to brute force. There's more ways to fill B1,2,4 compared to B,1,2,3, but I suspect there are many more opportunities for symmetries to reduce the number of trials. There should be fewer valid solutions per trial, however, so the computational load increase may not be too bad.

For that matter, if we are not in a hurry, given Bertram's incredibly efficient code, you could just fill in the unique combos for Block 2 only (Block 1 still fixed), and run the somewhat larger brute force trials. Each combination trial could take somewhere between 6^3 * 2 minutes to 9! * 2 minutes to run (worst case), but there wouldn't be very many of them.

Unless someone else adapts something along the lines of Bertrams's coding techniques, it's going to take 000's of hours to confirm anyways.

[Guest]

The prime number does not mean there are no further symmetries (as a friend pointed out here : http://www.sudoku.org.uk/discus/messages/29/34.html?1117032714

it means there are no other general symmetries (ie those that apply to all Sudoku). I may be able to find some computing time if a decent sieve can be written to find sudoku from all possible first 3 rows arrising from a single tope-left cell:

123
456
789

[Guest]

designate the boxes as follows

ABC
DEF
GHI

Box A can be filled in 9! (362880) ways.
Consistent with that boxes B and D can each be filled in 12096 = 9!/30 ways. =56 * 216 for box B the distrubution of the 9 numbers between the three rows can be done in 56 ways, each of the three rows can be order in 6 ways.
Now boxes C and G can be filled in 216 ways each. the rows areof C are fixed each can be ordered in 6 ways.

now box E. we have 3 numbers prohibited for each row and 3 for each column. It is relatively easy to show that over all possibilities the average is 403.2 But as B and D depend on A all possibilities are not equally likel, that's why this is only an estimate. I have found the true average but I've lost it since, it was marginally hiigher.

For box F we know the numbers in each row and have three numbers prohibited for each column. This leads to either 8 or 0 solutions in the ratio of 9 to 1. so on average 7.2.

exchange rows for columns and box H gives an average of 7.2

Box I we know all the rows and all the columns. these are consistent 9 times out of 70. so 0.1285714...

Multiplying we get 6.657084617 * 10^21 which is just below Bertrams number.

for a 4 x 4 grid this estimation method gives 256 instead of 288 but I would expect it to be more accurate (in percentage terms) for the full sized grid.

A brief comment on sysmetries.
The following operations on a solution will always give another solution
1) permuting the numbers 1 to 9
2) reordering a set of three columns which pass through the same boxes.
3) reordering rows similarly
4) reodering rows of boxes.
5) reodering columns of boxes
6) reflecting in a diagonal

these generate a group of 1,218,998,108,160 elements.
each gives a solution but they are not necessarily all different.
we can show however that we get at least 1,881,169,920 different solutions. 9! * 6^4 * 2^2 as permuting the numbers in gives 9! different sforms for the top left box. and for any of those shuffling columns 456 coulums 789 and swtching 456 with 789 give different top rows. similar shuffling of rows gives different first columns.

further one solution gives only 1,881,169,920 variants under the oerations. i.e

123 978 564
456 312 897
689 645 231

564 123 978
897 456 312
231 689 645

978 564 123
456 312 456
689 645 789

this factor of 2^13 3^8 5 7 gives only factors of 4 and a very large prime to account for.

[coloin]

Guest
nice calculation
I have been working on the exact same method just half an hour ago !

I had just formed an L shape like yours - although I had a nagging feeling that a combination of these first 5 boxes might just result in a constraint giving an impossible grid.

I was stuck on the central box 5 as you are but there is a calculation and i knew you need to use an average figure - not sure why though .

"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 ..."

Can you use show me why this doesnt help ? It certainly looks useful.

The last box - where do you get the 9 out of 70 ? I thought 1/30

The symetries are complicated - I cant see how one grid gets a different number from another - but nothing surprises me now.

[su bloko]

I have noted that it is much quicker to compute the number of solutions remaining given blocks 1.5 and 9 as opposed to blocks 1,2 and 3 (taking my crap programming as a given).

With this in mind I decided to see if I could derive the final result arrived at by Bertram/afj by using an analagous approach to theirs, but using blocks 1,5 and 9 as the start point.

I have just completed a trial of 1000 different random sets of blocks 5 and 9. 988 of these produced unique solutions. This compares poorly to the 44 unique sets for the 1,2 and 3 approach. It suggests that symmetry techniques will not allow me to make my approach managable.

Ho hum. Anyway, based on my 1000 trials, I can give another approximation to the number: 6.71 E 21. This is within about 0.5% of the Bertram/afj result.

I look forward to reading the finished document.