The New Sudoku Players' Forum

[Max Beran]

Perhaps someone can help sort out the logic of this puzzle. There is a NiceLoop which allows the 6 to be removed from r2c3 and from r8c3 and the 2 and the 6 from r2c8. At this point there is an xy-chain that allows the 7 in r2c8 to be eliminated. Proceeding from this point, the puzzle is then solved (and checks with the solution provided on www.sudokusite.eu/pdf/5s-k10.pdf).

But this is where my own puzzlement begins because if you study the xy-chain closely you reach an apparent internal conflict.

Going thorugh the xy-chain in the normal fashion, assume r2c8=7. Then
(r2c3=2) => (r8c3=9) => (r7c3=6) => (r7c8=4) and you can continue to show (r1c8=7) hence establishing the contradiction.

But if you go back to the statement (r7c8=4) then this also carries consequences:
(r7c8<>6) => (r6c8=6) => (r6c8<>2) => (r1c8=2); or more directly (r7c8=4)=> (r2c8=7) which is not in conflict with the initial premise.

The source of the contradiction is the odd number of links from r7c8 round to r6c8 that reverses the logic. I know that an xy-chain cannot use the target cell which in a sense I am doing if the aim is to get from r2c3 to r1c8 but surely the knock-on consequences of the real chain shouldn’t throw up inconsistencies en route.

Any assistance to get my thought processes back on track gratefully received.

[daj95376]

I may know why you're having a problem. You're following the XY-Chain in reverse!

The XY-Chain starts in [r1c8] and has two parts:

Code: Select all

[r1c8]=7                    => [r2c8]<>7
[r1c8]=2 => ... => [r2c3]=7 => [r2c8]<>7


See if you encounter any contradictions now.

[Carcul]

Hi Max Beran.

Sorry for going off topic, but, before your nice loop why don't you use the XY-Wing that solves the puzzle directly?

Carcul

[Max Beran]

Thanks Carcul for reminding me about xy-wings. It certainly makes this puzzle a lot easier to solve. I'd got into the habit of looking for xyz-wings then Swordfish then xy-chain then loops.

[Max Beran]

Thanks for your thoughts daj95376, but I'm not sure you've solved anything. If you inspect the chain of consequences of [r1c8]=2, you reach the points [r6c8]=6 then three steps later [r7c8]=6; a contradiction.

On reflection, what this shows is that the puzzle is unsolveable with [r1c8]=2. Normally the impossibility of a position only reveals itself further down the line and this puzzle is perhaps slightly unusual in bringing you face to face with its impossibility early on.

To the best of my knowledge xy-chains are not directional - you get the same answer whichever end you start at.

[daj95376]

Thanks for your thoughts daj95376, but I'm not sure you've solved anything. If you inspect the chain of consequences of [r1c8]=2, you reach the points [r6c8]=6 then three steps later [r7c8]=6; a contradiction.

On reflection, what this shows is that the puzzle is unsolveable with [r1c8]=2. Normally the impossibility of a position only reveals itself further down the line and this puzzle is perhaps slightly unusual in bringing you face to face with its impossibility early on.

To the best of my knowledge xy-chains are not directional - you get the same answer whichever end you start at.

What you've done is encountered the 'gotcha' in how XY-Chains work. Bivalue/bilocation links are followed but not performed or evaluated for contradictions. I originally wrote my solver to actually perform and evaluate XY-Chains while searching for them. I don't do that anymore.

Wait until you encounter a branching condition and discover that one direction leads to a valid XY-Chain and the other direction leads to a contradiction for the XY-Chain. From what I gather, contradictory branching chains are ignored. Now you know why solutions involving XY-Chains always have the chain spelled out in detail.

[ronk]

Going thorugh the xy-chain in the normal fashion, assume r2c8=7. Then
(r2c3=2) => (r8c3=9) => (r7c3=6) => (r7c8=4) and you can continue to show (r1c8=7) hence establishing the contradiction.

I see the implication of r7c8=4 as r2c8=7 ... not r1c8=7. IOW we've again described the same continuous loop (now an xy-ring) used for the prior exclusions. How did you get from r7c8=4 to r1c8=7?

.....68.3....9....8.4.7..95.......3829.568.1754.......38..5.7.2....8....7.16.....

Code: Select all

 9    127  5    | 124  124  6    | 8    27   3
 16   3   *27   | 8    9    5    | 126 *47   146
 8    126  4    | 123  7    123  | 126  9    5
----------------+----------------+---------------
 16   167  67   | 249  24   249  | 5    3    8
 2    9    3    | 5    6    8    | 4    1    7
 5    4    8    | 137  13   137  | 269  26   69
----------------+----------------+---------------
 3    8   *69   | 149  5    149  | 7   *46   2
 4    26  *29   | 379  8    379  | 1369 5    169
 7    5    1    | 6    234  2349 | 39   8    49

xy-ring:

r2c8-7-r2c3-2-r8c3-9-r7c3-6-r7c8-4-r2c8-

... which is a continuous loop, i.e., no contradiction

[RW]

How did you get from r7c8=4 to r1c8=7?

Code: Select all

 9    127  5    | 124  124  6    | 8   *27   3
 16   3   *27   | 8    9    5    | 126 *47   146
 8    126  4    | 123  7    123  | 126  9    5
----------------+----------------+---------------
 16   167  67   | 249  24   249  | 5    3    8
 2    9    3    | 5    6    8    | 4    1    7
 5    4    8    | 137  13   137  | 269 *26  *69
----------------+----------------+---------------
 3    8   *69   | 149  5    149  | 7   *46   2
 4    26  *29   | 379  8    379  | 1369 5    169
 7    5    1    | 6    234  2349 | 39   8   *49

... => r7c8=4 => r9c9=9 => r6c9=6 => r6c8=2 => r1c8=7

RW

[ronk]

Max Beran, xy-rings such as ...

r2c8-7-r2c3-2-r8c3-9-r7c3-6-r7c8-4-r2c8-

r7c8-4-r2c8-7-r1c8-2-r6c8-6-r7c8-

... neither prove nor disprove the existence of a candidate in the cells of the xy-ring. Therefore, your paradox doesn't exist IMO.

[Max Beran]

daj writes:

... neither prove nor disprove the existence of a candidate in the cells of the xy-ring. Therefore, your paradox doesn't exist IMO.

I think daj you still neglect the parallel existence of the side loop via r9c9 as was pointed out in my first posting and again by RW.

HOWEVER - following my Eureka moment (and fully accepting the blame for setting this particular hare running, I think all this stuff about xy-chains and rings has become a bit of a non-issue when the real reason why r2c8 cannot be 7 is that if it were then it makes r1c8=2 and that leads very rapidly to a contradiction. I never really got to grips with Nishio but isn't this what Nishio is about - choose a candidate and see if it leads to an impossible situation with that or another candidate.

Another way of looking at it is, if the puzzle had been posted as

Code: Select all

9.5|..6|823
.3.|895|...
8.4|.7.|.95
---+---+---
...|...|538
293|568|417
548|...|...
---+---+---
38.|.5.|7.2
4..|.8.|.5.
751|6..|.8.


then it would have quickly been spotted that this was an illegal Sudoku.

[RW]

Max, finally think I understand your initial question.

Going thorugh the xy-chain in the normal fashion, assume r2c8=7. Then
(r2c3=2) => (r8c3=9) => (r7c3=6) => (r7c8=4) and you can continue to show (r1c8=7) hence establishing the contradiction.

But if you go back to the statement (r7c8=4) then this also carries consequences:
(r7c8<>6) => (r6c8=6) => (r6c8<>2) => (r1c8=2); or more directly (r7c8=4)=> (r2c8=7) which is not in conflict with the initial premise.

The source of the contradiction is the odd number of links from r7c8 round to r6c8 that reverses the logic. I know that an xy-chain cannot use the target cell which in a sense I am doing if the aim is to get from r2c3 to r1c8 but surely the knock-on consequences of the real chain shouldn’t throw up inconsistencies en route.

In fact, when examined close enough, all XY-chains should show up inconsistences on the way. The basic idea of the XY-chain is that you have two possibilities, one of which must be true and the other false, but both lead to the same elimination. In this case you had either r2c3=7 or r1c8=7, therefore r2c8<>7. However, as the puzzle has an unique solution, one of the possibilities must be false and if you follow both chains long enough, one will lead to a contradiction sooner or later. What you found was simply this contradidiction (if r7c8=4 => r2c8=7 and r1c8=7). Actually this is a subchain of your XY-chain that makes the elimination:

r9c9<>4 => r9c9=9 => r6c9=6 => r6c8=2 => r1c8=7 => r2c8=4

So basically you missed this shorter XY-chain and went for the long one. But that doesn't really matter, both work. When working with chains the hardest thing is often to se the contradiction when it is in front of you.

RW

[daj95376]

This thread has taken several tangents since my last message. Maybe we should look at the original puzzle and the original problem presented by MB. (As I understand it.)

Code: Select all

# original puzzle from MB's graphic file
 *-----------*
 |...|..6|8.3|
 |...|.9.|...|
 |8.4|.7.|.95|
 |---+---+---|
 |...|...|.38|
 |29.|568|.17|
 |54.|...|...|
 |---+---+---|
 |38.|.5.|7.2|
 |...|.8.|...|
 |7.1|6..|...|
 *-----------*


Code: Select all

# reduced to just before MB's Nice Loop
# puzzle would be solved if XY-Wing at [r9c9] had been caught
 *-----------------------------------------------------------*
 | 9     127   5     | 124   124   6     | 8     27    3     |
 | 16    3     267   | 8     9     5     | 126   2467  146   |
 | 8     126   4     | 123   7     123   | 126   9     5     |
 |-------------------+-------------------+-------------------|
 | 16    167   67    | 249   24    249   | 5     3     8     |
 | 2     9     3     | 5     6     8     | 4     1     7     |
 | 5     4     8     | 137   13    137   | 269   26-   69*   |
 |-------------------+-------------------+-------------------|
 | 3     8     69    | 149   5     149   | 7     46*   2     |
 | 4     26    269   | 379   8     379   | 1369  5     169-  |
 | 7     5     1     | 6     234   2349  | 39    8     49*   |
 *-----------------------------------------------------------*


Code: Select all

# puzzle after MB's Nice Loop
# XY-Chain (a..h) for <2> candidate in MB's graphic link
 *-----------------------------------------------------------*
 | 9     127   5     | 124   124   6     | 8     27a   3     |
 | 16    3     27h   | 8     9     5     | 126   47-   146   |
 | 8     126   4     | 123   7     123   | 126   9     5     |
 |-------------------+-------------------+-------------------|
 | 16    167   67    | 249   24    249   | 5     3     8     |
 | 2     9     3     | 5     6     8     | 4     1     7     |
 | 5     4     8     | 137   13    137   | 269   26b   69c   |
 |-------------------+-------------------+-------------------|
 | 3     8     69f   | 149   5     149   | 7     46e   2     |
 | 4     26    29g   | 379   8     379   | 1369  5     169   |
 | 7     5     1     | 6     234   2349  | 39    8     49d   |
 *-----------------------------------------------------------*


Now, the problem arises because MB can't accept that [r6c8]=6 and [r7c8]=6 in the XY-Chain. To tell the truth, I have a hard time swallowing it as well. My earlier explanation still holds about how links are the basis for XY-Chains and no actual cell assignments occur to create contradictions. Am I correct?

[daj95376]

daj writes:

... neither prove nor disprove the existence of a candidate in the cells of the xy-ring. Therefore, your paradox doesn't exist IMO.

I think daj you still neglect the parallel existence of the side loop via r9c9 as was pointed out in my first posting and again by RW.

I didn't write this!!!

[ronk]

daj writes:

... neither prove nor disprove the existence of a candidate in the cells of the xy-ring. Therefore, your paradox doesn't exist IMO.

I think daj you still neglect the parallel existence of the side loop via r9c9 as was pointed out in my first posting and again by RW.

You quoted me, not daj. And I think you still neglect the parallel existence of both continuous and discontinuous xy-chains. xy-rings are continuous xy-chains and do not result in an exclusion in a cell of the xy-ring.

Discontinuous xy-chains have a discontinuity ... a cell at which a contradiction occurs ... causing a valid exclusion at the discontinuity. That a continuous chain exists using even most of the same cells matters not. The exclusion is still valid.

[Max Beran]

Sorry daj to blame you for something ronk wrote.

The original puzzle is not quite as you say as this was the position after the usual naked pairs, tied to a row etc etc; in other words up to the point where Simple Sudoku would say "no hint available". I can recommend the site referred to in my initial posting - it provides inter alia 24 fiendish puzzles per month in downloadable pdf booklet form.

Thanks too, RW and ronk for those further thoughts about the nature of xy-chain logic. It is very helpful and illuminating. I have encountered many puzzles with such chains and I am confident in stating that this was the first time that a chain revealed an actual resolution so directly. While branch points are common - indeed there's a couple in the chain in question - mostly they don't lead anywhere. I think it was the fact that the branch line through r9c9 had an odd number of links before rejoining the short loop that led to the chain having its own seed of resolution.

Anyway, of course RW, you're right that uniqueness means that only one candidate can be the right one in the cells along the chain. I also take daj's implied point that the actual truth value of the candidates along the chain are held in a sort of limbo - both are true/false until there is a collapse of symmetry that permits an assignment. The pleasure in finding chains lies in the fact that the chain's mere existence carries solid information that allows a reduction in the clutter of possibilities.

I always feel there's something of the Schrodinger Cat about this simultaneous truth/falsity, especially as it needs a collapse of symmetry to unlock all the locked pairs and triples that puzzles eventually reduce to. How's that for a tangent