by tannedblondbloke » Sat Apr 09, 2005 10:03 am
How many possible grids are there?
Here's my attempt.
First we consider block 5; then blocks 4 and 6; then blocks 2 and 8; then blocks 1, 3, 5 and 7.
1 - Block 5
In filling in block 5, there are no constraints, and clearly we can fill it in any of 9! ways. For the rest of this post, I will assume this block is filled out as below, as we can go from any grid to one looking like this by relabelling:
123
456
789
How many ways are there of filling blocks 4 and 6? Well, let's consider the rows and columns of blocks 4 and 6 separately - rows first.
2 - Rows of Blocks 4 and 6
In block 4, all numbers must be shifted up a row or down a row (ordering the rows cyclicly, up from row 4 is row 6, and down from row 6 is row 4) as numbers can't occupy a row in block 4 if they occupy that row in block 5. And whatever shift applies in block 4, the opposite shift applies in block 6 (if number 5 is shifted up to row 4 in block 4, it must be shifted down to 6 row in block 6) by applying the same constraint to blocks 4 and 6.
Let's consider then what happens to numbers 4, 5, and 6. We only need count what happens in block 4 as we know the opposite happens in block 6. For each, there are two choices - shift up or shift down - so 2x2x2=8 choices in total. In 2 of these choices, 4, 5 and 6 are all shifted in the same direction (up or down); in the other 6, one is shifted one way and two the other.
Suppose 4, 5 and 6 are all shifted to row 4; where can 7, 8 and 9 go? Well, they can't remain in row 6, and because row 4 is occupied, they can't go there. So they are forced up into row 5, and 1, 2 and 3 are shifted up into row 6. So all the row choices are forced. By symmetry a similar argument applies if 4, 5 and 6 are shifted down.
Now suppose 4 and 6 are all shifted up and 5 is shifted down. Where can 7, 8 and 9 go? Well, they can't remain in row 6, and 2 cells in row 4 are occupied. One could go to row 4, but the other two have to go to row 5. What about 1, 2 and 3? They can't remain in row 4, and two cells in row 5 are occupied, so two of them must go to row 6, which along with number 5 is now fully occupied. So of 7, 8 and 9, exactly two shift up and one down, and of 1, 2 and 3, exactly two shift up and one down. So we need to choose one of 1, 2 and 3, and one of 7, 8 and 9 to move down, and the rest of those numbers move up.
To recap - with block 5 fixed, there are 2+(6x9)=56 ways of assigning numbers to rows in block 4 - just work out what happens to numbers 4, 5 and 6 (up or down, for 8 choices) - in 2 of those 8, they are all shifted the same way and indeed all 9 numbers are shifted that way. In the other 6 choices, one of 4, 5 and 6 move opposite to the others, and we must also pick an opposite mover out of each of {1,2,3} and {7,8,9}. And having made these choices, the assignment of numbers to rows in block 6 are forced.
3 - Columns of Blocks 4 and 6
In block 4, we have assigned 3 numbers to row 4, 3 to row 5, and 3 to row 6. Within each row, there is no constraint - we can assign those numbers to columns arbitrarily. So for each row there are 6! choices to be made, ie (6!)^3 in total. The same applies to block 6.
Taking steps 1, 2 and 3 together, there are 9! x 56 x (6!)^6 ways of populating blocks 4, 5 and 6.
4 - Blocks 2 and 8
By the same argument, all numbers in block 2 are shifted left or right in block 2, relative to their position in block 5, and the opposite applies to block 8 - we simply consider what happens to numbers 2, 5 and 8, and what that forces on each of {1,4,7} and {3,6,9} and come up with 56 ways of assigning numbers to columns in block 2 (which forces assignments to columns in block 8). Numbers can be assigned to rows freely.
So we have 9! x 56^2 x (6!)^12 ways of assigning numbers to blocks 2, 4, 5, 6 and 8.
5 - Blocks 1, 3, 7 and 9
In block 1, all numbers are shifted up or down relative to their position in block 2, and the opposite shift applies to block 3. We have 56 choices as before.
In block 7, all numbers are shifted up or down relative to block 8, and the opposite shift applies to 9 - 56 choices again.
In block 1, all numbers are shifted left or right relative to their position in block 4, and the opposite now applies to 7 - 56 choices.
Finally, in block 3, all numbers are shifted left or right relative to block 6, and opposite applies to 9 - 56 choices
So the final number of choices is 9! x 56^6 x (6!)^12 = 217,210,668,439,560,000,000,000,000,000,000,000,000,000,000,000,000