The New Sudoku Players' Forum

[Guest]

Lets try this from a whole different direction:

Step A:
Pretend that the only 'rule' was the 'block' rule, and that the row and column rules did not exist. Then each block could be arranged 9! ways, or 9!^9 ways to populate the puzzle (1.0911*10^50 'solutions').

Step B1:
If we then say 'let us add a rule about unique values in a row', then the top three blocks can be filled as follows:
Block 1: 9! ways
Block 2: 56 ways to select which values go in each 3-cell row, and 3! ways to arrange them (remember that we haven't invented a column rule yet).
Block 3: with 1 and 2 filled, the values that go in each row is now defined, but each row can be arranged 3! ways.
Therefore, we have 9! * 56 * 3!^6 ways to fill the top three blocks, and this value cubed to fill all nine blocks. (or 8.5227*10^35 solutions). Note that this represents a 'reduction ratio' (denoted as R) of 1.2802*10^14, by adding this one new rule.

Step B2: But we could have just as easily added a 'unique in columns' rule, and achieved the same results downward instead of across, with the same value of R.

Step C: (and here is where my solution is not rigorous) What if we assume that each of these rules would constrain the number of valid solutions by exactly the same ratio? Then there would be a combined reduction ratio of R^2. So the intitial value of 1.0911*10^50 solutions would reduce by a factor of R^2, or 1.639*10^28, leaving 6.6571*10^21 valid solutions.

[Guest]

That was me as 'guest again'.

[Guest]

Well, I think Tinfoil's approach requires a pretty big leap of faith - and why not? Nothing else seems to be much better! I'll have a ponder on that.

On the point made by a previous guest about my method (was this Tinfoil too?) I think the second shuffling idea was indeed a red herring - the case I used to convince myself was actually a digit translation (i.e. part of the 9!), not a position change. So that leaves it back at 9! x 8 x (3!^8), or 4.8 * 10 ^ 12. Could you give an example of how two manipulations could be the same? I can't quite see it, but I'm willing to believe it may be true.

My biggest worry is that this approach might not lead to all possibilities, even if you consider all possible transformations. I can't think why it wouldn't, but can't quite convince myself that it does either...

[Guest]

Could you give an example of how two manipulations could be the same? I can't quite see it, but I'm willing to believe it may be true.

It is not that the manipulations are the same. What I was saying is that the final and initial grids may 'look' the same, for some grids.

Consider:
123 456 789
456 789 123
789 123 456

231 564 897
564 897 231
897 231 564

312 645 978
645 978 312
978 312 645

There's a host of row / column / block by row or column 'swaps' that result in the starting point.

For example, swap blocks 147 with blocks 258, and then roll the rows so that rows 123,456,789 become 312,645,978. Since each of 9 occurances of each digit are the same, you are back where you started.

[Guest]

I keep forgetting that this forum does not retain the username!

That was me again.

[Guest]

Ok, so we start with this
123 456 789
456 789 123
789 123 456

231 564 897
564 897 231
897 231 564

312 645 978
645 978 312
978 312 645

Swap the first two vertical chutes:
456 123 789
789 456 123
123 789 456

564 231 897
897 564 231
231 897 564

645 312 978
978 645 312
312 978 645

And then roll the rows 123, 456, 789 to 312, 645 978 you get
123 789 456
456 123 789
789 456 123

231 897 564
564 231 897
897 564 231

312 978 645
645 312 978
978 645 312

This isn't where we started, because cols 4,5,6,7,8 & 9 are different...

[Guest]

Oops, I didn't state that quite right (and apparently you cannot read my mind)

Could you give an example of how two manipulations could be the same? I can't quite see it, but I'm willing to believe it may be true.

It is not that the manipulations are the same. What I was saying is that the final and initial grids may 'look' the same, for some grids.

Consider:
123 456 789
456 789 123
789 123 456

231 564 897
564 897 231
897 231 564

312 645 978
645 978 312
978 312 645

There's a host of row / column / block by row or column 'swaps' that result in the starting point.

For example, ROLL blocks 147 to blocks 258, and ROLL blocks 258 to 369. Now roll the rows so that rows 123,456,789 become 312,645,978. Since each of 9 occurances of each digit are the same, you are back where you started.

[Guest]

I've just realised that when I realised that my original realisation was wrong, I was wrong. It was right. Well, nearly. Are you keeping up?

The idea of Shuffling one box, and then the one below (or the third one), is in fact sound, but I got the maths a little wrong...

To illustrate, consider this chute:

123
456
789

234
567
891

345
678
912

The top box can be shuffled 3!^3 times, and for each of these there are then two valid combinations for the 2nd and 3rd box. So for the top box as it is, the 2nd and 3rd box could be as shown, or they could be:

342
675
918

534
867
291

So the number of combinations for the column is 3!^3 x 2, not (3!x2)^3

Thus, all chutes give us (3!^3 x 2)^3, and then we need to square it to allow for horizontal chutes: (3!^3 x 2)^6

Leading to

9! x 8 x (3! ^ 2) x (3! ^ 3 x 2) ^ 6

or 6.8 x 10^23

But this is bigger than the 5x10^23 which was set as an upper limit before.

I'm thinking that maybe there is something in what Tinfoil said. Perhaps these shuffles will cover all rotations and flips too, so you can probably disallow the 8, which brings it back to 8.5 x 10^22, which is at least below the previously lowest upper limit.

[Guest]

Tinfoil again I assume? I see what you mean. That's a bugger. Any idea how to work out how many duplicates there are? I think that may be much the same problem as we hit with the TBB approach...

Or... maybe the shuffling of chutes is a red herring too. Perhaps, thinking about TBB's method, all you need to do is allow for the in-box shuffling of the starting grid, so you just have

9! x (3!^3 x 2) ^ 6

Which is 2.35 x 10^21 - a nice big number, but healthily below the old upper limits.

[Animator]

A bit off-topic (sorry for those reading the thread):

I keep forgetting that this forum does not retain the username!

That was me again.

It does... but before you can enable it you need to register yourself... look at the top of the page next to 'Usergroups' (http://forum.enjoysudoku.com/profile.php?mode=register)

[Guest]

What an active thread this has been in the last 24 hours! For what it's worth, IJ's new approach seems to be the same as the one I vaguely outlined in my post of April 1st - but he explains it better than I did! However, after thinking briefly about it, I couldn't find any other good transformations either, and also came to an answer that seemed many orders of magnitude too low. So I gave up. (But I still think that this would be nicest approach, if it could be made to work!)

I think I mentioned something in that post too about looking up the method for counting the number of "Latin squares" (n x n squares with every number 1,...,n appearing in each row and each column); I assumed that it would use some similar method. But in fact it uses a brute force counting method, to my surprise, with calculations taking lots of CPU time on a powerful computer. I do wonder now whether this might be the only method...

tinfoil's nice heuristic idea giving an answer of around 6 x 10^21 coincides with what Josh reported Mante Carlo simulations as giving. It all makes me want to know the exact value even more!

Frazer

[tannedblondbloke]

Yes - I started with 8, but then I managed to convince myself that other combinations were possible too. It was late!

Any comments on the rest?

I'm sure I will have. You've made some thought provoking posts that I would like to think about. I might not reply immediately as I am going on holiday in less than a week, but I do plan to reply!

[tannedblondbloke]

We seem to be agreed that the number of ways of populating a chute (when neither of the other chutes in the same direction has any cells filled) is:

9! x 56 x (3!)^6

[AFJ, IJ and myself all claim this].

Just to recap, we got this by (a) noting there is no restriction the first box we fill (9! cases), (b) there are 54 ways of assigning digits to rows in the second box so that they don't clash with the first box -- see my earlier post -- and digits WITHIN each row are unrestricted (3! for each row ie 3!^3) (c) the allocation to rows in the 3rd box are now all fixed, but there is freedom on the allocation within rows (3! for each row ie 3!^3).

I had then proceeded to construct a chute perpendicular to the first (actually creating a + shape but the same arguments would apply if constructing an L or a T) - analagous to (b) and (c) there would be 56x(3!)^3 ways of filling the fourth box and (3!)^3 ways of completing the fifth box.

At this point I had used analagous arguments to (b) to enumerate the possibilities for the remaining boxes and it looks like the choices we have already made have differing effects on completing the rest of the puzzle (ie we have to identify subcases). This must be the case, else Tinfoil and I would have come up with the same number, as we basically applied the same philosophy but in a different order! And Tinfoil's flaw must also be present in mine.

I must write another program! I started using my current program and whatiffing constraints, and concluded that (a) such an approach would take too long but (b) my previous estimate was several oders of magnitude too high, as I could see the light at the end of the tunnel if I had enough time.

I'm concerned about IJ's "generator" approach - I too wonder if a mix of reordering, relabeling, shuffling, rotations and reflections can bring us back to our starting point! Also, does it generate every possibility? I'd like to think about this some more.

Tinfoil's "leap of faith" in his step C may be a leap too far. Just like the whittling of mu 54^2 possibilities for box one down to 448 (or 432 or 400 or 392 or 384!), the fact that our row and constraints interfere with one another leads me to guess you will end up several orders of magnitude too high.

I'd like to propose a new approach. Before it was a top down approach: fill in one block; what does this imply about other blocks in the same stack?; what does this imply about other blocks in the same band?; what does this imply about other blocks elsewhere?

Suppose we are filling in a block; how many ways of filling it in are there, if we have already filled in a blocks in the same band and b in the same stack? (By symmetry, only need to consider a>=b)

a=0 b=0 ie block 5 in my first stab 9!
a=1 b=0 ie block 4 in my first stab 54x(3!)^3
a=2 b=0 ie block 6 in my first stab (3!)^3
a=1 b=1 ie block 1 say Originally I said 54x54; now 384-448 depending choices already made
a=2 b=1 ie block 3 and 7 Originally 54 but clearly 0 or 8 depending on choices already made*
a=2 b=2 ie block 9 say Originally 1 but actually 0 or 1 depending on choices already made

So a new upper bound would seem to be

9! x 54 x 3!^6 x 448 x 8 x 8 = 26,213,335,317,872,600

What I want to do now is do a bottom up approach - start with a=2, b=2 and work towards a=0, b=0, asking questions like "what constraints on the grid make the a=2, b=2 case 0 rather than 1? Or the a=2, b=1 case 0 rather than 8? etc

[Guest]

I agree that we are agreed on 9! x 56 x 3!^6 for any "chute". This leads to 9! x (56 x 3!^6)^2 for any cross shape (L, T, +, etc., where we have one vertical chute and one horizontal chute). [Did you miss out blocks 2 and 8 in your new upper bound, by the way?] So, this gives the possible ways of filling in blocks 1, 2, 3, 4 and 7. We can fill in block 5 and block 9 in at most 448 ways each. Then blocks 6 and 8 can be filled in at most uniquely. This gives the upper bound: 9! x (56 x 3!^6)^2 x 448^2, as IJ already gave, I think.

I'd suggest a brute force approach along these lines - fill in block 1 with 123/456/789, as usual, and look at all the (56 x 3!^6)^2 ways of filling these in to blocks 2, 3, 4 and 7. Although this is a big number (!), there should be rather fewer which are "essentially distinct", in that they give different numbers of ways of filling blocks 5, 6, 8 and 9. (It would be computationally very desirable to cut this number down as much as possible!) Then, for each, count the number of ways of filling in blocks 5 and 9 which give valid Sudokus. It all looks a rather frightening calculation to do!

As for tinfoil's "leap of faith" in step C, it certainly doesn't give the right answer exactly - in fact, it isn't even an integer (it would give an answer with a denominator of 125, I think). Nevertheless, my gut feeling is that it is a very good guide to what the answer should be, and I think I'd be surprised if that actual answer differed by more than a few percent from it (and if it were within 1%, I don't think I'd be surprised).

As for the "generator" approach, it will certainly be true that a mix of reordering, etc., brings us back to the starting point. But I don't think that that's so important at this point - the key thing is to be sure that we can generate every grid with a series of the given transformations; the equivalences can be dealt with later.

Frazer

[tannedblondbloke]

I agree that we are agreed on 9! x 56 x 3!^6 for any "chute". This leads to 9! x (56 x 3!^6)^2 for any cross shape (L, T, +, etc., where we have one vertical chute and one horizontal chute). [Did you miss out blocks 2 and 8 in your new upper bound, by the way?] So, this gives the possible ways of filling in blocks 1, 2, 3, 4 and 7. We can fill in block 5 and block 9 in at most 448 ways each. Then blocks 6 and 8 can be filled in at most uniquely. This gives the upper bound: 9! x (56 x 3!^6)^2 x 448^2, as IJ already gave, I think.

Silly me. Yes I did miss out boxes 2 and 8. Also in the last post I typed 54 a few times where I meant 56.

My upper bound is different from yours though - I think 448 appears once:

9! for box 5 (a=0, b=0)
56x(3!)^3 for box 4 (a=1, b=0)
(3!)^3 for box 6 (a=2, b=0)
56x(3!)^3 for box 2 (a=1, b=0)
(3!)^3 for box 8 (a=1, b=0)
448 for box 1 (a=1, b=1)
8 for box 3 (a=2, b=1)
8 for box 7 (a=2, b=1)
1 for box 9 (a=2, b=2)

All which multiplies up to 9!x56^2x(3!)^12x448x8^2=
71,025,136,897,117,200,000,000