Very Hard - from Times Website
by Guest » Sat Apr 02, 2005 6:33 am
Right. I'm sobering up a bit now. Apologies for earlier incoherent ramblings - I daren't go back and read them. However, I'm ready to present Theory B - And this one does hold water. Honest. But you may need to concentrate!
A non-T&E solution to Nishio
c1 & c6 have only two 7s.
Because r7c6 and r8c1 are in the same line of three boxes, these can be proven to be tied.... Refering back to my observation that the set of possibilities for r7c1-r7c3 & r7c7-r7c9 must be the same as that for r6c4-r6c6 & r6c4 - r6c6, we can see that 7 only appears in either pair once.
Therefore, if r8c1 is 7 then r7c6 must also be 7. Likewise if r8c1 is not 7, then neither is r7c6. Perhaps luckily in this case, there is also a pair of (17)s enforcing this, but I doubt this is always true. Now, we can see that if they are not 7, then both r1c1 and r1c6 would have to be 7 as there are no longer any other places in those two columns, but they are both on the same row, so this must be wrong. So, r8c1 & r7c6 must both be 7.
I can hear you thinking this is no different to the T&E method, but it is - I've just used T&E to prove a fundamental property of the pattern, and now the pattern is understood and recognisable, it can be used to resolve possibilities without T&E - just like the simpler rules we all use, and just like the X-wing.
I think the rule can be defined by three criteria that must be met:
Two columns have only two places a digit is possible
Two of those possibilities have one row in common
The other two appear in the same line of three boxes, and are tied.
If these criteria are met then the two tied cells must be the digit in question. As with the X-wing, this can clearly be transposed into a row-based rule.
It's quite a complicated test, and doubtless hard to spot by eye in a puzzle, but this is a solid logical deduction, that does not require the ever-loathed stage of "if this is a 7...", just attention to detail. As I think I said before, I am no longer so sure that this would count as unfair - just very difficult.
Verdicts?....
A non-T&E solution to Nishio
c1 & c6 have only two 7s.
Because r7c6 and r8c1 are in the same line of three boxes, these can be proven to be tied.... Refering back to my observation that the set of possibilities for r7c1-r7c3 & r7c7-r7c9 must be the same as that for r6c4-r6c6 & r6c4 - r6c6, we can see that 7 only appears in either pair once.
Therefore, if r8c1 is 7 then r7c6 must also be 7. Likewise if r8c1 is not 7, then neither is r7c6. Perhaps luckily in this case, there is also a pair of (17)s enforcing this, but I doubt this is always true. Now, we can see that if they are not 7, then both r1c1 and r1c6 would have to be 7 as there are no longer any other places in those two columns, but they are both on the same row, so this must be wrong. So, r8c1 & r7c6 must both be 7.
I can hear you thinking this is no different to the T&E method, but it is - I've just used T&E to prove a fundamental property of the pattern, and now the pattern is understood and recognisable, it can be used to resolve possibilities without T&E - just like the simpler rules we all use, and just like the X-wing.
I think the rule can be defined by three criteria that must be met:
Two columns have only two places a digit is possible
Two of those possibilities have one row in common
The other two appear in the same line of three boxes, and are tied.
If these criteria are met then the two tied cells must be the digit in question. As with the X-wing, this can clearly be transposed into a row-based rule.
It's quite a complicated test, and doubtless hard to spot by eye in a puzzle, but this is a solid logical deduction, that does not require the ever-loathed stage of "if this is a 7...", just attention to detail. As I think I said before, I am no longer so sure that this would count as unfair - just very difficult.
Verdicts?....
- Guest
by SteveF » Sat Apr 02, 2005 9:09 am
Hi IJ,
This is certainly an interesting extention of the solution to the X-Wing to a possible application to the Nishio situation.
One question though. Going way back to the diagram on page one of this post which set everything off, I have three posibilities for a 7 in column 6, ie r8c6 as well as the two you consider, r8c1 and r7c6.
Can you give an insight on why you can eliminate r8c6 as a possibility for a 7?
One final point, at the risk of setting off a further debate. I think I am in favour of the X-Wing being described as a special case, after all a rectangle is a special case of of a four sided polygon (and there have been several references to the rectangular nature of the X-Wing).
However I wonder if your solution for a Nishio is also a special case, given the need for two places in one row and the other two places in the same line of three boxes?
- I wonder if there is a more general definition of Nishio which doesn't have these restrictions?
This is certainly an interesting extention of the solution to the X-Wing to a possible application to the Nishio situation.
One question though. Going way back to the diagram on page one of this post which set everything off, I have three posibilities for a 7 in column 6, ie r8c6 as well as the two you consider, r8c1 and r7c6.
Can you give an insight on why you can eliminate r8c6 as a possibility for a 7?
One final point, at the risk of setting off a further debate. I think I am in favour of the X-Wing being described as a special case, after all a rectangle is a special case of of a four sided polygon (and there have been several references to the rectangular nature of the X-Wing).
However I wonder if your solution for a Nishio is also a special case, given the need for two places in one row and the other two places in the same line of three boxes?
- I wonder if there is a more general definition of Nishio which doesn't have these restrictions?
- SteveF
- Posts: 86
- Joined: 26 March 2005
by Tim » Sat Apr 02, 2005 10:03 am
SteveF wrote:One question though. Going way back to the diagram on page one of this post which set everything off, I have three posibilities for a 7 in column 6, ie r8c6 as well as the two you consider, r8c1 and r7c6.
Can you give an insight on why you can eliminate r8c6 as a possibility for a 7?
Hi - you can eliminate 7 from r8c6 because you have to cells in row 8 that only contain 1 & 7 - r8c1 and r8c4. Therefore you can eliminate all other 1s and 7s from row 8.
- Tim
- Posts: 18
- Joined: 12 March 2005
by shakers » Sat Apr 02, 2005 10:08 am
Someone asked earlier "Who needs sleep?", the answer is I do, so I'm gutted to have missed last night's fantastic breakthrough on this.
I think I need another cup of tea before I get it totally straight in my mind, but it's looking wonderfully promising!
Well done!
I think I need another cup of tea before I get it totally straight in my mind, but it's looking wonderfully promising!
Well done!
Last edited by shakers on Sat Apr 02, 2005 6:19 am, edited 1 time in total.
- shakers
- Posts: 93
- Joined: 10 March 2005
by Sue De Coq » Sat Apr 02, 2005 11:08 am
Tim wrote:Hi - you can eliminate 7 from r8c6 because you have to cells in row 8 that only contain 1 & 7 - r8c1 and r8c4. Therefore you can eliminate all other 1s and 7s from row 8.
I don't think that logic works. The rule ('disjoint subsets') states that when the only candidates for the values 1 and 7 along Row 8 are the same two cells, it's possible to remove all other candidates from these cells. However, the initial condition isn't satisfied in our case because, amongst other things, 1 and 7 are candidates at r8c3.
- Sue De Coq
- Posts: 93
- Joined: 01 April 2005
Summary of thoughts on Nishio
by Sue De Coq » Sat Apr 02, 2005 11:32 am
A Proposed definition: A rule should be described as 'Trial & Error', if, after its application, the grid is no longer guaranteed to be in 'good' state - i.e. if it is no longer guaranteed to be on the path to a (not necessarily unique) correct solution.
On that basis, generic Nishio is not a 'Trial & Error' rule because, although it starts out with a potentially false hypothesis, the grid is guaranteed not to be in a bad state once the application of the rule has been completed. So Nishio uses reductio ad absurdum but not Trial & Error. Furthermore, since each of the logical steps taken during a Nishio is trivial, i.e. it involves the placement of a known value in a row, column or box for which there is just a single candidate position, IMHO, the application of Nishio should fall well within the compass of the Man on the Clapham Omnibus with a pencil in one hand and a copy of The Times in the other. Of course, he might not spot the initial move that, when assumed false, would kick off the Nishio reasoning and result in the elimination of a possibility but, if he did, he ought to be able to follow the necessary logic quite easily.
X-Wings is a special case of Nishio that is able to be expressed in a logically-positive form, which makes it aesthetically more pleasing and much simpler and faster to implement. My hope is that we will be able to examine the Nishio output from other puzzles in order to identify certain geometric patterns, similar to X-Wings, which we are able to express in a logically-positive form.
On that basis, generic Nishio is not a 'Trial & Error' rule because, although it starts out with a potentially false hypothesis, the grid is guaranteed not to be in a bad state once the application of the rule has been completed. So Nishio uses reductio ad absurdum but not Trial & Error. Furthermore, since each of the logical steps taken during a Nishio is trivial, i.e. it involves the placement of a known value in a row, column or box for which there is just a single candidate position, IMHO, the application of Nishio should fall well within the compass of the Man on the Clapham Omnibus with a pencil in one hand and a copy of The Times in the other. Of course, he might not spot the initial move that, when assumed false, would kick off the Nishio reasoning and result in the elimination of a possibility but, if he did, he ought to be able to follow the necessary logic quite easily.
X-Wings is a special case of Nishio that is able to be expressed in a logically-positive form, which makes it aesthetically more pleasing and much simpler and faster to implement. My hope is that we will be able to examine the Nishio output from other puzzles in order to identify certain geometric patterns, similar to X-Wings, which we are able to express in a logically-positive form.
- Sue De Coq
- Posts: 93
- Joined: 01 April 2005
by Tim » Sat Apr 02, 2005 12:08 pm
Sue De Coq wrote:I don't think that logic works. The rule ('disjoint subsets') states that when the only candidates for the values 1 and 7 along Row 8 are the same two cells, it's possible to remove all other candidates from these cells. However, the initial condition isn't satisfied in our case because, amongst other things, 1 and 7 are candidates at r8c3.
Yes 1 and 7 were candidates in r8c3, but they were the only candidates for r8c1 and r8c4. Therefore if you put a 1 or a 7 in any cell other than r8c1 or r8c4 then you cannot complete row 8. Therefore you can remove 1 and 7 as candidates from all the other cells in row 8, as they have to go in r8c1 and r8c4. Thus this leaves only 6 and 9 as candidates in r8c3.
Look at IJ's post on the first page of this topic where I ask how you get the 4 in r8c5 for another view on this.
- Tim
- Posts: 18
- Joined: 12 March 2005
by Guest » Sat Apr 02, 2005 1:26 pm
SDC - Firstly, thanks for your guidance last night - I was going of the rails for a while there!
I think though, that somehow you are still missing the point here. The Nishio method I described is not reducio (ad nauseum or otherwise), it is just a pattern recognition exercise. You never have to try anything, just spot the pattern, and know the inference that can be made.
I feel there is also a problem with your distinction between T&E and other methods - T&E will by definition eventually end up with the correct solution, which is obviously a "Good" state. I think the only definition needed is the term itself - "Trial and Error". If you need to try something (i.e. Trial it), then you are using T&E, whether or not it is possible to proceed without it. All non-T&E methods involve recognising a pattern that is known to have clear, irrefutable inferences. By this definition, the X-wing technique described by Su doku above, and my description of the Nishio pattern are clearly not T&E. They are complicated, but can be resolved without ever testing a value.
The point is that a rule cannot be trial and error - Either you are using a rule (i.e. a recognisable pattern) to make an inference, or you are guessing and seeing what happens. If it's a rule then trial is not needed; conversely, if a value is tested, then you are not using a rule (X-wing, Nishio or any other), you are using T&E.
I think though, that somehow you are still missing the point here. The Nishio method I described is not reducio (ad nauseum or otherwise), it is just a pattern recognition exercise. You never have to try anything, just spot the pattern, and know the inference that can be made.
I feel there is also a problem with your distinction between T&E and other methods - T&E will by definition eventually end up with the correct solution, which is obviously a "Good" state. I think the only definition needed is the term itself - "Trial and Error". If you need to try something (i.e. Trial it), then you are using T&E, whether or not it is possible to proceed without it. All non-T&E methods involve recognising a pattern that is known to have clear, irrefutable inferences. By this definition, the X-wing technique described by Su doku above, and my description of the Nishio pattern are clearly not T&E. They are complicated, but can be resolved without ever testing a value.
A rule should be described as 'Trial & Error', if, after its application, the grid is no longer guaranteed to be in 'good' state
The point is that a rule cannot be trial and error - Either you are using a rule (i.e. a recognisable pattern) to make an inference, or you are guessing and seeing what happens. If it's a rule then trial is not needed; conversely, if a value is tested, then you are not using a rule (X-wing, Nishio or any other), you are using T&E.
- Guest
by Bernard Stay » Sat Apr 02, 2005 2:59 pm
I am grateful (as I'm sure everyone else is) for su_doku's very clear explanation of the 'X-wing' escape from that blocked puzzle. I shall certainly add the technique to my armoury. However I think, as Wayne suggested, that this lies in a slightly grey area between strict logic and T & E. It is logical, but not of the absolute linear logic which I had come to expect. None, for example of the possible placements of the 6 in the puzzle is ruled out by the existing established filled-in numbers. We cannot say this & this has to be a or b so some third cell has to be c. What we are saying is that whether 6 is at a and b or 6 is at c and d some other cell has to be a 9. This smacks to me of "if...then...".
However all that may be, I rather hope that the Times won't be printing such convoluted puzzles, though users might like to consider asking Poppocom to put an occasional stinker on this website for the masochists among us!
However all that may be, I rather hope that the Times won't be printing such convoluted puzzles, though users might like to consider asking Poppocom to put an occasional stinker on this website for the masochists among us!
- Bernard Stay
- Posts: 94
- Joined: 22 March 2005
by Guest » Sat Apr 02, 2005 3:32 pm
Good tip Shakers - I didn't know that. I tried a few and all was well, but then I hit one that my X-wing algorithm wouldn't solve:
* 3 8 7 4 1 * 6 *
7 6 * 3 2 1 * * *
8 4 1 5 6 9 2 7 3
9 3 8 6 * 2 4 * 7
* 7 6 9 4 3 * 2 *
* * 4 7 * 8 3 6 9
3 8 2 1 9 6 7 * *
4 * * 2 3 7 6 * *
6 1 7 4 8 5 9 3 2
I don't see anything obvious, or anything that meets my Nishio criteria. Anyone have any ideas?
PS Bernard - consider the example of two pairs eliminating possibilities for other cells, as we used at the start of this thread to get the 4 in r8c5. This is basically exactly the same logic as the x-wing.
* 3 8 7 4 1 * 6 *
7 6 * 3 2 1 * * *
8 4 1 5 6 9 2 7 3
9 3 8 6 * 2 4 * 7
* 7 6 9 4 3 * 2 *
* * 4 7 * 8 3 6 9
3 8 2 1 9 6 7 * *
4 * * 2 3 7 6 * *
6 1 7 4 8 5 9 3 2
I don't see anything obvious, or anything that meets my Nishio criteria. Anyone have any ideas?
PS Bernard - consider the example of two pairs eliminating possibilities for other cells, as we used at the start of this thread to get the 4 in r8c5. This is basically exactly the same logic as the x-wing.
- Guest
by shakers » Sat Apr 02, 2005 3:37 pm
IJ wrote:Good tip Shakers - I didn't know that. I tried a few and all was well, but then I hit one that my X-wing algorithm wouldn't solve:
* 3 8 7 4 1 * 6 *
7 6 * 3 2 1 * * *
8 4 1 5 6 9 2 7 3
9 3 8 6 * 2 4 * 7
* 7 6 9 4 3 * 2 *
* * 4 7 * 8 3 6 9
3 8 2 1 9 6 7 * *
4 * * 2 3 7 6 * *
6 1 7 4 8 5 9 3 2
I don't see anything obvious, or anything that meets my Nishio criteria. Anyone have any ideas?
PS Bernard - consider the example of two pairs eliminating possibilities for other cells, as we used at the start of this thread to get the 4 in r8c5. This is basically exactly the same logic as the x-wing.
That was how I got the puzzle I quoted earlier. As for this one... have a look at box 1... you seem to have too many 8s...
- shakers
- Posts: 93
- Joined: 10 March 2005
