The New Sudoku Players' Forum

[daj95376]

I'm new to XY-Chains and seem to have discovered an anomaly. Consider the following possibility of an XY-Chain on [r2c8]=78 forcing [r7c8]<>8. Here's how I get conflicting results. (Please forgive my chain notation. I did my best.)

Code: Select all

  Original
 *-----------*
 |.87|..9|23.|
 |.9.|4.6|1..|
 |..1|...|..5|
 |---+---+---|
 |...|6..|...|
 |.5.|.8.|.2.|
 |...|..1|...|
 |---+---+---|
 |5..|...|7..|

 |..6|2.3|.1.|
 |.42|7..|69.|
 *-----------*

  Reduced w/ Pencilmarks
 *-----------------------------------------------------------*
 | 46    8     7     | 15    15    9     | 2     3     46    |
 | 2     9     5     | 4     3     6     | 1     78ab  78b   |
 | 34    36    1     | 8     7     2     | 9     46    5     |
 |-------------------+-------------------+-------------------|
 | 1379  123   348   | 6     249   45a   | 348   57a   179   |
 | 16    5     349   | 39    8     7     | 34    2     16    |
 | 379   236   348   | 35    249   1     | 348   567   79    |
 |-------------------+-------------------+-------------------|
 | 5     13    39    | 19    6     48a   | 7     48ab  2     |
 | 89    7     6     | 2     49    3     | 5     1     48b   |
 | 18    4     2     | 7     15    58    | 6     9     3     |
 *-----------------------------------------------------------*

                              [r2c8]-8-[r7c8] => [r7c8]<>8   (the easy part)
a) [r2c8]-7-[r4c8]-5-[r4c6]-4-[r7c6]-8-[r7c8] => [r7c8]<>8   (XY-Chain seems valid)
b) [r2c8]-7-[r2c9]-8-[r8c9]         -4-[r7c8] => [r7c8]=8    (XY-Chain falls apart)


Since (a) and (b) can not both be true, then I'm left with [r2c8]<>7 -- which, indirectly, supports the XY-Chain. Any constructive suggestions -- besides not using XY-Chains? Is there a technique that I should have used on [r2c8] before trying the XY-Chain?

[Edit #1:] Aaack, I just realized that the (a) linkage <87><75><54><48> meets the definition of an XY-Chain and affected buddy cells, i.e. [r7c8]; whereas the (b) linkage <87><78><84> does not meet the definition of an XY-Chain. So much for trying to manually recreate my solver's logic.

[Edit #2:] However, my original suspicion that XY-Chains are non-deterministic still seems valid. If my solver had not followed path (a), then it might have followed path (b) and missed that an XY-Chain existed. To rectify this shortcoming, it seems to me that XY-Chains would need backtracking. This would definitely make it T&E.

[ronk]

Any constructive suggestions -- besides not using XY-Chains?

You are looking at two xy-chains which are not in conflict. The (a) chain is a discontinuous xy-chain with the discontinuity at r8c8 ...

r7c8-8-r7c6-4-r4c6-5-r4c8-7-r2c8-8-r7c8, implies r8c8<>8

The (b) chain is a continuous xy-chain ...

-r7c8-8-r2c8-7-r2c9-8-r7c9-4-r7c8-

... which would allow exclusions of digit 8 in c8 and c9, digit 7 in r2 and b3, and digit 4 in box 9. However, there are none.

Since the (a) chain exclusion is made in a cell that is also part of the (b) chain, placements consequentially occur in all other cells of the (b) chain.

[Carcul]

If my solver had not followed path (a), then it might have followed path (b)

How could your solver follow path (b) if it doesn't lead to any deduction?

[tso]

There is no anomoly. You are mixing two different tactics:


[1] If all possiblities lead to one result, that result must be TRUE.
This is proof by induction.

[2] If a single possiblity leads to more than one result, that possiblity must be FALSE.
This is a proof by contradiction.



Your first [unlettered] statement:
(I) If r2c8=8 then r7c8=4

Your second [a] statement:
(II) If r2c8=7 then r4c8=5 then r4c6=4 then r7c6=8 then r7c8=4

Your third [b] statement, with typos corrected:
(III) If r2c8=7 then r2c9=8 then r8c9=4 then r7c8=8


Statements (I) and (II) taken together prove that r7c8=4 by induction.

Statements (II) and (III) taken together prove that r2c8<>7 by contradiction.

Statements (I) and (III) taken together prove nothing.

There is no conflict nor need for backtracking.

[daj95376]

[Edited:]
Thanks tso for catching my typos in (b). I've corrected it.

My puzzle demonstrates that there are at least two chains -- (a) & (b) -- from [r2c8] to [r8c8] that lead to different conclusions. This sounds like [2] to me and supports my belief that XY-Chains -- and Forcing Chains in general -- may become non-deterministic if multiple chains exist from a starting cell to a destination cell for a candidate. If you want to positively determine if an XY-Chain exists, then you may have to examine multiple chains to the destination cell. This sounds like backtracking to me.