Tinfoil - I had read TBB's very carefully before (you might have noticed my input then). And his reasons for 56 make sense, but only work because at each stage he is considering the contraints made by one box, not two (e.g. He states that with Box 5 populated, there are 56 ways to populate both box 4 and 6).
So, in your model this works for box 2 when considering box 1 alone (it is also true for box 3). But this is obviously the upper limit for possibilities. The flaw in your model is that by considering the columns, the options suddenly leap to 56^2 - this obviously can't be true because the options for a box based on two constraints (i.e. box 1 & 5) must be less than or equal to the options based on one constraint (e.g. box 1)
Su-Doku's maths
by Guest » Fri Apr 15, 2005 2:51 pm
IJ wrote:Tinfoil - I had read TBB's very carefully before (you might have noticed my input then). And his reasons for 56 make sense, but only work because at each stage he is considering the contraints made by one box, not two (e.g. He states that with Box 5 populated, there are 56 ways to populate both box 4 and 6).
So, in your model this works for box 2 when considering box 1 alone (it is also true for box 3). But this is obviously the upper limit for possibilities. The flaw in your model is that by considering the columns, the options suddenly leap to 56^2 - this obviously can't be true because the options for a box based on two constraints (i.e. box 1 & 5) must be less than or equal to the options based on one constraint (e.g. box 1)
Please note that I am 'stealing' his logic from his STEP 5, where he is filling block 1, given that blocks 2 and 4 are filled.
In my case, I am filling blocks 2 or 4, given that blocks 1 and 5 are filled. I contend that the constraints are identical, so the number of permutations must be as well.
- Guest
by Guest » Fri Apr 15, 2005 5:36 pm
Well, not quite - TBB said that the possibilities for box 1, 3, 7 & 9 are 56 each - not 56^2 each.
But, I've been thinking about that, and suspect TBB may be wrong there too. As I say, when there are more constraints, there must be fewer possibilities (or at least no more). So, the possibilities in his step 5 cannot be the same as in step 2.
More to the point though, I think the starting point for the corners in step 5 should be 56x(3!^3), not just 56 (There is no reason to assume that the possibilities from shifting the rows are invalid)
So, for box 1 (based on box 2) you start with 56x(3!^3), but then you need to remove the possibilities that are disallowed by box 4. I have no idea how to do that! 56x(3!^3) is definitely the upper limit, but the logic falls down because there is no direct link between the combinations in box 2 & box 4, so the number of invalid combinations in box 1 depends on which of the 56x(3!^3) possibilities are in box 4.
My Head hurts :o)
But, I've been thinking about that, and suspect TBB may be wrong there too. As I say, when there are more constraints, there must be fewer possibilities (or at least no more). So, the possibilities in his step 5 cannot be the same as in step 2.
More to the point though, I think the starting point for the corners in step 5 should be 56x(3!^3), not just 56 (There is no reason to assume that the possibilities from shifting the rows are invalid)
So, for box 1 (based on box 2) you start with 56x(3!^3), but then you need to remove the possibilities that are disallowed by box 4. I have no idea how to do that! 56x(3!^3) is definitely the upper limit, but the logic falls down because there is no direct link between the combinations in box 2 & box 4, so the number of invalid combinations in box 1 depends on which of the 56x(3!^3) possibilities are in box 4.
My Head hurts :o)
- Guest
by Guest » Fri Apr 15, 2005 10:42 pm
Well, I have an answer for the corners. I couldn't work out how to define the problem, so I used brute force.
In the corner boxes, each digit could be placed in 4 cells. This is because, for example, each digit appears in both box 2 and box 4 once, on either a row or a column that intersects with box 1. These two intersections always exclude 5 cells, thus leaving 4 cells for a placement.
Not knowing how to get a number from this information, I wrote a short program to explore all the combinations that produce a valid box. The answer is 448 - I'd love to know why. It's 8 x 56 if that helps.
So boxes 1 and 9 can be 448, but boxes 2 and 4 are actually defined now - that is, they have only one valid solution. This is because row 1 now has 6 digits, so the 3 digits for c7-c9 are known, but not the order, however, this is also true for col 9. So the digit they have in common must go in r1c9, and so on for all the intersections between rows 1,2 & 3 and cols 7, 8 & 9
Going back to TBBs answer, but replacing these values we get
9! x (56 ^2) x (3!^12) x 448^2
or about 5x10^23
In the corner boxes, each digit could be placed in 4 cells. This is because, for example, each digit appears in both box 2 and box 4 once, on either a row or a column that intersects with box 1. These two intersections always exclude 5 cells, thus leaving 4 cells for a placement.
Not knowing how to get a number from this information, I wrote a short program to explore all the combinations that produce a valid box. The answer is 448 - I'd love to know why. It's 8 x 56 if that helps.
So boxes 1 and 9 can be 448, but boxes 2 and 4 are actually defined now - that is, they have only one valid solution. This is because row 1 now has 6 digits, so the 3 digits for c7-c9 are known, but not the order, however, this is also true for col 9. So the digit they have in common must go in r1c9, and so on for all the intersections between rows 1,2 & 3 and cols 7, 8 & 9
Going back to TBBs answer, but replacing these values we get
9! x (56 ^2) x (3!^12) x 448^2
or about 5x10^23
- Guest
by Guest » Thu Apr 21, 2005 6:41 pm
I fear that IJ's calculations aren't quite right; the first reason is that 448 is not always right (it is usually just a bit too much), but the more serious reason is that tinfoil's "fundamental problem" isn't accounted for. The first problem makes only a small difference, but I suspect that the second could make a difference of a couple of orders of magnitude, making Josh's reported estimate earlier much more accurate. But IJ's value is an upper bound - the best yet!
To deal with the first problem first, 448 would be the correct answer for filling in blocks with constraints like
*** 123
*** 456
*** 789
123 ???
456 ???
789 ???
(where the * are irrelevant, and we are trying to fill in the ?) in which not only are there four possible squares for any number, but, conversely, every square has four possible numbers going into it. But consider the configuration
*** 147
*** 258
*** 369
123 ???
456 ???
789 ???
It is still true that every number can go into one of four possible squares; however, some squares can be filled by three numbers and others by six. In fact, it's quite easy to show that there are 432 possible ways to fill this in. I think that there are always between 384 and 448 possible ways to fill in these constraints. (I may have this wrong, but I think that there are five basic patterns, which my computer tells me have 448, 432, 400, 392 and 384 possibilities.)
But the second problem is much more serious. As tinfoil originally said, "with only blocks 6 and 8 to fill, there can be only one unique way to fill them", but later noted that in fact, there can easily be no ways at all to fill them. My guess is that this will be the typical case. The sort of thing that can happen when trying to fill in block 1, say, if we already have blocks 2 and 3, and blocks 4 and 7, is that there might be a picture like the following:
??? *** ***
??? 1** 2**
??? 2** 1**
*12
***
***
*21
***
***
The constraints from blocks 2 and 3 force the 1 and the 2 both the occur in the top row of block 1, and blocks 4 and 7 force them both to occur in the left column - so they have to occupy the same square, which is not possible!
Frazer
To deal with the first problem first, 448 would be the correct answer for filling in blocks with constraints like
*** 123
*** 456
*** 789
123 ???
456 ???
789 ???
(where the * are irrelevant, and we are trying to fill in the ?) in which not only are there four possible squares for any number, but, conversely, every square has four possible numbers going into it. But consider the configuration
*** 147
*** 258
*** 369
123 ???
456 ???
789 ???
It is still true that every number can go into one of four possible squares; however, some squares can be filled by three numbers and others by six. In fact, it's quite easy to show that there are 432 possible ways to fill this in. I think that there are always between 384 and 448 possible ways to fill in these constraints. (I may have this wrong, but I think that there are five basic patterns, which my computer tells me have 448, 432, 400, 392 and 384 possibilities.)
But the second problem is much more serious. As tinfoil originally said, "with only blocks 6 and 8 to fill, there can be only one unique way to fill them", but later noted that in fact, there can easily be no ways at all to fill them. My guess is that this will be the typical case. The sort of thing that can happen when trying to fill in block 1, say, if we already have blocks 2 and 3, and blocks 4 and 7, is that there might be a picture like the following:
??? *** ***
??? 1** 2**
??? 2** 1**
*12
***
***
*21
***
***
The constraints from blocks 2 and 3 force the 1 and the 2 both the occur in the top row of block 1, and blocks 4 and 7 force them both to occur in the left column - so they have to occupy the same square, which is not possible!
Frazer
- Guest
by Guest » Thu Apr 21, 2005 8:49 pm
I agree with the second point - I actually think this is a fundamental problem with this general approach - I don't think there is any way to avoid it. I'm starting to lean back towards the possibilities grid proposed as the best method.
On the first point, I thought I had tested enough combinations to be sure about the 448, but obviously not! I can confirm afj's numbers, though I don't understand them any more than my original 448...
On the first point, I thought I had tested enough combinations to be sure about the 448, but obviously not! I can confirm afj's numbers, though I don't understand them any more than my original 448...
- Guest
by Guest » Thu Apr 21, 2005 11:36 pm
OK, a slightly new approach - don't think this is quite right, but maybe others will chip in...
Take the basic starting grid:
123 456 789
456 789 123
789 123 456
234 567 891
567 891 234
891 234 567
345 678 912
678 912 345
912 345 678
Working on the discussions elsewhere about "generator" puzzles , you can do a lot to this grid without affecting it's validity (sorry, I can't find the original discussion, so I can't credit the author).
That initial discussion covered the fact that you can flip vertically, horizontally, or diagonally and rotate through 90, 180, or 270 degrees. I think you can get 24 distinct transformations from these.
So allowing for the 9! combinations of the starting grid, we have 9!x24 possibilities.
But taking the idea a bit further, you can also reorder the rows within each horizontal chute (i.e. rows 1 - 3, 4 - 6 and 7-9) and remain valid, giving:
9!x24x(3!^3)
Likewise for cols 1-3, 4-6 & 7-9:
9!x24x(3!^6)
Finally, you can also reorder the horizontal and vertical chutes themselves.
9!x24x(3!^8)
This is a pretty small number compared to the other upper limits (around 1.46 x 10^13).
Can anyone think of other operations that don't invalidate the grid, or any reason why this general approach is invalid?
Take the basic starting grid:
123 456 789
456 789 123
789 123 456
234 567 891
567 891 234
891 234 567
345 678 912
678 912 345
912 345 678
Working on the discussions elsewhere about "generator" puzzles , you can do a lot to this grid without affecting it's validity (sorry, I can't find the original discussion, so I can't credit the author).
That initial discussion covered the fact that you can flip vertically, horizontally, or diagonally and rotate through 90, 180, or 270 degrees. I think you can get 24 distinct transformations from these.
So allowing for the 9! combinations of the starting grid, we have 9!x24 possibilities.
But taking the idea a bit further, you can also reorder the rows within each horizontal chute (i.e. rows 1 - 3, 4 - 6 and 7-9) and remain valid, giving:
9!x24x(3!^3)
Likewise for cols 1-3, 4-6 & 7-9:
9!x24x(3!^6)
Finally, you can also reorder the horizontal and vertical chutes themselves.
9!x24x(3!^8)
This is a pretty small number compared to the other upper limits (around 1.46 x 10^13).
Can anyone think of other operations that don't invalidate the grid, or any reason why this general approach is invalid?
- Guest
by Guest » Fri Apr 22, 2005 1:08 am
Got some more!
You can also shuffle a box, keeping each digit on the same row (as discussed by TBB). This gives you 3!^3. Each row in the box below can then be arranged in one of 2 ways - 3!^3 x (2^3). The last box will have only one posible combination.
So, by shuffling the first box, we get (3!^3 x (2^3))
Now, I think that this covers all the possibilities. I explored the option of shuffling the second box, and then the third, but I don't think it's necessary.
Coming at it another way, of the 6! ways to arrange the digits 1,2 & 3 there are only two exclusive sets (123, 231, 312 and 132, 213, 321). Each of these can be arranged 3! ways, so that's 2 x 3! resolutions for the digits 1,2 & 3 down a vertical chute of three boxes. That's also true for 4,5 & 6 and 7, 8 & 9. Giving us (3! x 2) ^ 3, or (3!^3 x 2^3) as above. Good - I've convinced myself!
So, we then need to do the same for the columns in boxes along a horizontal chute:
(3! x 2) ^ 6
This is actually a general case of the shuffling of rows and columns I was talking about, so we can discount the (3! ^ 6) for them, and multiply by the number above instead:
9! x 24 x (3!^2) x (3! x 2) ^ 6
This is aprroximately 9.36 x 10^14
You can also shuffle a box, keeping each digit on the same row (as discussed by TBB). This gives you 3!^3. Each row in the box below can then be arranged in one of 2 ways - 3!^3 x (2^3). The last box will have only one posible combination.
So, by shuffling the first box, we get (3!^3 x (2^3))
Now, I think that this covers all the possibilities. I explored the option of shuffling the second box, and then the third, but I don't think it's necessary.
Coming at it another way, of the 6! ways to arrange the digits 1,2 & 3 there are only two exclusive sets (123, 231, 312 and 132, 213, 321). Each of these can be arranged 3! ways, so that's 2 x 3! resolutions for the digits 1,2 & 3 down a vertical chute of three boxes. That's also true for 4,5 & 6 and 7, 8 & 9. Giving us (3! x 2) ^ 3, or (3!^3 x 2^3) as above. Good - I've convinced myself!
So, we then need to do the same for the columns in boxes along a horizontal chute:
(3! x 2) ^ 6
This is actually a general case of the shuffling of rows and columns I was talking about, so we can discount the (3! ^ 6) for them, and multiply by the number above instead:
9! x 24 x (3!^2) x (3! x 2) ^ 6
This is aprroximately 9.36 x 10^14
- Guest
by tannedblondbloke » Fri Apr 22, 2005 6:17 am
IJ wrote:That initial discussion covered the fact that you can flip vertically, horizontally, or diagonally and rotate through 90, 180, or 270 degrees. I think you can get 24 distinct transformations from these.
So allowing for the 9! combinations of the starting grid, we have 9!x24 possibilities.
Rotations and reflections alone only give 8 arrangements, not 24:
no change (1)
rotate about 90, 180 or 270 deg (3)
reflection about x axis or y axis or either diagonal (4)
Any combination ofthese 8 results in another of these 8. Combine 2 rotations and you get a rotation; combine two reflections and you get a rotation; combine a reflection and rotation and you get a reflection.
- tannedblondbloke
- Posts: 16
- Joined: 09 April 2005
by Guest » Fri Apr 22, 2005 12:50 pm
IJ wrote:Got some more!
You can also shuffle a box, keeping each digit on the same row (as discussed by TBB). This gives you 3!^3. Each row in the box below can then be arranged in one of 2 ways - 3!^3 x (2^3). The last box will have only one posible combination.
So, by shuffling the first box, we get (3!^3 x (2^3))
Now, I think that this covers all the possibilities. I explored the option of shuffling the second box, and then the third, but I don't think it's necessary.
Coming at it another way, of the 6! ways to arrange the digits 1,2 & 3 there are only two exclusive sets (123, 231, 312 and 132, 213, 321). Each of these can be arranged 3! ways, so that's 2 x 3! resolutions for the digits 1,2 & 3 down a vertical chute of three boxes. That's also true for 4,5 & 6 and 7, 8 & 9. Giving us (3! x 2) ^ 3, or (3!^3 x 2^3) as above. Good - I've convinced myself!
So, we then need to do the same for the columns in boxes along a horizontal chute:
(3! x 2) ^ 6
This is actually a general case of the shuffling of rows and columns I was talking about, so we can discount the (3! ^ 6) for them, and multiply by the number above instead:
9! x 24 x (3!^2) x (3! x 2) ^ 6
This is aprroximately 9.36 x 10^14
I think that you have to be careful about 'shuffling' a row in one box, and then expecting that the same digits are going to be available in the same row below.
In addition, there are going to be some cases where your manipulations are going to result in an identical solution. For example, a reflection/rotation combined with a box exchange can result in the starting point, if your solution started out with a high degree of symmetry.
But this is a promising approach.
- Guest
- Posts: 312
- Joined: 25 November 2005
by Guest » Fri Apr 22, 2005 1:27 pm
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.
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
- Posts: 312
- Joined: 25 November 2005
by Guest » Fri Apr 22, 2005 2:38 pm
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...
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
by Guest » Fri Apr 22, 2005 2:59 pm
IJ wrote: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
- Posts: 312
- Joined: 25 November 2005
