## XY-Chains Non-Deterministic ???

Everything about Sudoku that doesn't fit in one of the other sections

### XY-Chains Non-Deterministic ???

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.
Last edited by daj95376 on Tue Jul 18, 2006 12:33 pm, edited 3 times in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: XY-Chains Non-Deterministic ???

daj95376 wrote: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.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

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

Carcul

Posts: 724
Joined: 04 November 2005

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.

(I) If r2c8=8 then r7c8=4

(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.
tso

Posts: 798
Joined: 22 June 2005

[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.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006