XY-Chains, Loops & Almost Locked Sets

Remote Pairs

Remote Pairs are formed by several naked pairs linked to form chains of even number of bi-value cells. The chain must be of even length to allow eliminations: 2, 4, 6... cells. We may then remove both naked possibilities from all buddies of the end cells of the chain of even length. Long chains may allow several eliminations at once, by shortening them provided the sub-chains are of even length. There may be several such chains forming a tree or cluster allowing even more eliminations.

Here is a simple example of a remote pair on {39}:

The cells R2C2,R2C4,R3C6,R8C6 forms a chain of 4 cells with {39}. It follows that R2C2 and R8C6 contains either [39] or [93]. Whichever the case, R8C2 cannot hold 3 (nor 9) since it's a buddy of both cells.

Notice that the chain contains 4 cells, an even number of cells. We cannot make any elimination for chains with an odd number of cells. In the above example, R2C2,R2C4,R3C6 does not allow any elimination for R3C2 since it contains 3 cells and does not form a remote pair.

This forms an Alternating Inference Chain (AIC) of bi-value cells, a particular case of XY-Chain with only two candidates. This can also be viewed as two X-Chains for both candidates. The above example forms a Two String Kite for 3 and also a useless Two String Kite for 9. JSudoku does not use AIC for remote pairs, but simple coloring to form clusters, which allows elimination on several cells at once.

Here is another example of a cluster of remote pairs on {26} allowing several eliminations at once:

R23C8, R8C9<>{26} because there exist several chains of even length:
Skyscraper-like: R1C9-R1C1-R7C1-R7C8 -> R23C8, R8C9<>{26}
Two String Kite-like: R1C9-R1C1-R2C2-R8C2 -> R8C9<>{26}
Two String Kite-like: R2C2-R8C2-R7C1-R7C8 -> R2C8<>{26}

XY-Chain & Loop

An XY-Chain links several bi-value cells (with two possibilities). The XY-Wing can be viewed as an XY-Chain with 3 cells. It can be expressed using the strong and weak inferences known as Alternating Inference Chain (AIC). This is similar in logic to Turbot Fish and X-Chain, but here the strong inferences are bi-value cells instead of bi-location strong links. The weak links are any row, column, nonet...

As an introduction, here is the XY-Wing example expressed using AIC:

R2C5 has strong inference between the two candidates {46}: it must hold one of 4 or 6. Similarly, R2C7 has strong inference on {26} and R3C8 on {24}. R2 establishes a weak link between the two cells R2C57 for candidate 6 (they cannot both hold 6) and N3 establishes a weak link between R2C7 and R3C8 for candidate 2. This forms an AIC:

(4=6)R2C5-(6=2)R2C7-(2=4)R3C8 -> R2C9,R3C5<>4

Here is an example of an XY-Chain on 8 with 5 cells:

(8=5)r4c1-(5=1)r7c1-(1=7)r7c4-(7=4)r5c4-(4=8)r5c9 -> r4c7,r5c1<>8

An XY-Chain can form a continuous loop or cycle where each bi-value cell (strong link) of the chain is weak linked to the next and previous one through some row, column, block... Each of the weak link should then become a strong link which allow much more eliminations. This is similar in logic to Generalized X-Wing, except the strong links are bi-value cells instead of bi-location conjugate pairs. The simplest case of an XY-Loop would be a naked pair formed by two bi-value cells (strong links), linked to each other through a house (two weak links for the two candidates). For example we can write a naked pair on {12} in R1C34 using AIC where the weak links are 1 for R1 and 2 for R1:

...(1=2)r1c3-(2=1)r1c4... -> 1 locked in r1c34 for r1, 2 locked in r1c34 for r1

Here is an example of an XY-Loop with 4 cells:

...(7=3)r4c5-(3=8)r2c5-(8=5)r2c3-(5=7)r4c3... -> 7 locked in r4c35 for r4, 8 locked in r2c35 for r2

Notice this also locks 3 in r24c5 for c5 and 5 in r24c2 for c2, which was already the case.

XY-X-Chain & Loop

This solver combines a mix of bi-value cells with bi-location strong links. The Y-Wing pattern can also be viewed as an XY-X-Chain with two bi-value cells and one bi-location strong link:

(6=2)R2C6-(2)R7C6=(2)R7C5-(2=6)R4C5 -> R2C5,R56C6<>6

This example shows an XY-X-Chain on 6 with 2 bi-value cells and 2 bi-location strong links

The two bi-location strong links are: 6 of R9 locked in R9C78, and 2 of C8 locked in R79C8. These two strong links are weak linked through the cell in R9C8 since it cannot hold both a 6 and a 2. The chain continues through weak link in R7 to the bi-value cell R7C4={23} then weak link in C4 to the bi-value cell R5C4={36}. Following the AIC shows that either R9C7=6 or R5C4=6 and therefore R5C7 cannot hold a 6 (nor could R9C4):

(6)R9C7=(6)R9C8-(2)R9C8=(2)R7C8-(2=3)R7C4-(3=6)R5C4 -> R5C7<>6

The chain do not have to end with nodes for the same candidate. This may allow elimination of the opposite candidate for the end nodes as long as both end cells share some house. More generally, we can eliminate any candidate node for which there exist weak links to both end nodes of the chain. These two weak links are usually ommited in the AIC, but may be explicitly listed. For the above chain, the full AIC gives:

(6)R5C7-(6)R9C7=(6)R9C8-(2)R9C8=(2)R7C8-(2=3)R7C4-(3=6)R5C4-(6)R5C7 -> R5C7<>6

Here is an XY-X-Chain where the end nodes contains candidates 4 and 5 and are buddies of each other:

The full AIC gives:

(5)R1C6-(4)R1C6=(4)R1C8-(1)R1C8=(1)R2C8-(1=5)R2C5-(5)R1C6 -> R1C6<>5

This shows that either R1C6=4 or R2C5=5. Whichever the case, R1C6 cannot hold a 5 because (5)R1C6 is weak linked to (4)R1C6 (R1C6 cannot hold both 4 and 5) and to (5)R2C5 (N2 cannot hold two 5s). Similarly, R2C5 could not hold a 4.

The chain may form a continuous loop or cycle, each strong link of the chain is weak linked to the next and previous one. Each of the weak link must then become a strong link which allow much more eliminations. This is similar in logic to XY-Loop, Generalized X-Wing, naked or hidden pair. This example shows an XY-X-Loop with 3 bi-value cells and 3 bi-location strong links:

...(1=3)R6C9-(3)R6C5=(3)R7C5-(3=2)R7C4-(2)R8C4=(2-6)R8C2=(6)R8C3-(6=1)R6C3... -> 1 locked in R6C39 for R6, R8C2={26}, 6 locked in R68C3 for C3

Note: JSudoku will first search for loops, then for the case where end nodes have same candidate and finally the case with different candidates.

Grouped XY-Chain & Loop

This is like XY-X-Chain & Loop, but will also search for chains using grouped strong links.

Sue de Coq alias Two Sectors Disjoint Subsets

To come. See Sudopedia

Almost Locked Sets (ALS) XZ Rule

To come. See Sudopedia

Aligned Pair Exclusion (APE)

JSudoku catches APE using ALS-XZ rule which yields the same eliminations. See also Sudopedia


Simple Techniques | Fishes & Single Digit | Wings | XY-Chains, Loops & ALS | Uniqueness | Jigsaw, Windoku & Gatai | Greater/Less Than & Non-Consecutive | Killer | Innies/Outies | Advanced Killer | Square Wisdom | Contents

Copyright (C) 2006-2008 Jean-Christophe Godart. All rights reserved.