The New Sudoku Players' Forum

[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

[Guest]

Nice observation! (Silly me, this time! I should have read your earlier post more carefully.) Yes, your upper bound and your method are much better (by a factor of 448/8^2 = 7).

I've spent the last few hours trying to sort out a way to make a brute force count computationally feasible. I'd got my outer loop to about 35000^2, i.e., about 10^9 (!), which was much larger than I wanted - then I thought I saw a way to improve that quite a lot, but after lots of working, it isn't nearly as significant as I'd hoped - my outer loop is still only reduced to about 22000^2. Back to the drawing board (or rather, to bed). But your observation improves the inner loop by a factor of 7. Another order of magnitude, and I'll think about programming it...

Frazer

[Guest]

All good stuff...

My latest thought on my approach is a little baffling to me...

The last version ( 9! x (3! x 2) ^ 6), effectively involves shuffling every box through every possibility, while ensuring the whole grid is consistent. Sounds nice. I don't see how this can miss any possibilities, so I would suggest it is an upper limit. But I actually think it must double count to an alarming degree:

Consider box 1 - we are shuffling the columns to get 3! ^ 3, and saying there are 2 ^ 3 ways to arrange the two boxes below as a result. We then Shuffle the rows and get the same figure. This covers 3!^6 arrangements for box 1. But we are multiplying that by 9!, so we are considering 9! x 3!^6 possibilities for box 1 - silly.

My maths isn't good enough to know what to do with that information - but it feels like you might just take the 3!^3 out leaving 9! x 2^6, or 23,224,320. This is ridiculous! Even if you bring back the flips and spins, it's not a very big number.

[Guest]

A new method... I did this completely independently and almost completely differently, but came to the same number (almost!) as TBB - the only difference comes from the original value for an independent chute. These are the first two answers that are remotely similar, so I'm happy that one of them is right - can anyone see why I get a 36 rather than 56?...

Firstly, Row 1: 9!

now, cells r2c1-c3 can be populated from the values in r1c4-c9. These can be either 3 from box 2, and none from box 3, 2 from box 2 and 1 from box 3, 1 from box 2 and 2 from box 3 or none from box 2 and 3 from box 3.

Each of these have the following possibilities

0 & 3 : 3! x 3!
1 & 2 : 3! x (4 x 3!) - 4 is the number of combinations of 3 from 4
2 & 1 : 3! x (10 x 3!) - 10 = combs of 3 from 5
3 & 0 : 3! x (20 x 3!) - 20 = combs of 3 from 6

This gives a total of 3!^2 x 35 x 3! for second row, and thus the first chute is

9! x 35 x 3!^6.

I'm surprised it wasn't 56 in the middle, but moving on...

The same logic as row 2 works for box 4, so chute 1 & box 4 is

9! x 35 x 3!^6 x 35 x 3!^3

The bottom box is obviously 3!^3.

So the first horizontal chute, and the first vertical chute is

9! x 35^2 x 3!^12

Box 5 will be 448 (or rather 384-448), leaving 8 ways (2^3) to arrange boxes 6 and 8, and 1 for box 9.

So the total is - 9! x 35^2 x 3!^12 x 448 x 8 x 8.

=2.77 x 10^23

[Guest]

Actually, your answer would be 2.77 x 10^22, I think. But I'm completely sure that 56 is right, not 35. I can't quite make out enough of your explanation to put my finger on exactly what is wrong. But I think it must be in the way you are using the combinations; choosing 1 from box 2 and 2 from box 3 can be done in (3 choose 1) x (3 choose 2) ways, which is 3 x 3 =9, and I don't see why you are choosing 3 from 4 at any point. By the way, what is the new point in your method? It does look like earlier methods from what you've said.

With 56, you get exactly TBB's upper bound, 71025136897117189570560, or 7.1 x 10^22. This is only an upper bound, as it simply counts the maximum number of ways of filling in each block.

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

Frazer