Until now, most posts in this forum that describe forcing chains and related methods as nodes consisting of cells which are connected by labeled linkages which are related to contents of the cells being linked. There are dozens of methods and types of these chains out there, some of which are brute force methods, and some which satisfy the algorithmic information theory requirements for theoretical methods.

It turns out that all chains found so far which qualify as theoretical can be described as Alternating Inference Chains. XY-Wings, X-Cycles, Bivalue XY-Chains, Bilocation XY-Chains, Mixed XY-Chains, Continuous and Discontinuous Nice Loops, Dual Implication Chains, chains employing Unique Rectangles, XYZ-Wings, even the ALS XZ-Rule deductions are all Alternating Inference Chains (AICs). Furthermore, AIC's are all guaranteed to be pattern-based, theoretical, and not brute force.

Definitions

Candidate, Candidate Premise In the following I am going to keep it simple at the start and just say "candidate" instead of "candidate premise". The simplest "candidate premise" is "candidate n is true in this cell," which is what most people mean when they talk about a candidate. Note that more complicated premises are possible, such as "candidate n is true in one of the cells marked with an A" (typical candidate grouping), or even "candidates i, j, and k are all true in cells A, B, and C", which is handy for a wxyz-wing. Simple AICs use only the simplest candidate premises.

Alternating Inference Chain (AIC) is a chain which starts with an endpoint candidate which has a strong inference on the next candidate, which has a weak inference on the next candidate, which has a strong inference on the next candidate, and so on alternating weak and strong inferences until it ends with a strong inference on the final candidate at the other endpoint. The nodes of an AIC are really just the candidate premises themselves.

In the following inference definitions, A and B are candidates (or candidate premises).

Weak Inference: For two premises, if A and B cannot both be true then there is a weak inference between A and B. To extend to multiple premises, if at most only one of a set of premises can be true, then those premises satisfy the weak inference requirement. Another way of saying this for this is, "One premise being true implies the rest are false."

Strong Inference: For two premises, if A and B cannot both be false, then there is a strong inference between A and B. To extend to multiple premises, if at least one of a set of premises must be true, then those premises taken together satisfy the strong inference requirement. As long as the set of premise choices encompasses all possible choices, then that set can be divided in any fashion, and a strong inference exists between any division of that set. For the two premise case, a strong inference is often represented as A being false implies B is true.

Note that due to the rule of the contrapositive, the weak and strong inferences work in both directions. For example, take the weak inference: A = true implies B = false. From the other direction we would have B = true implies A = false. Since this is just the contrapositive of the weak inference, we know that it is a valid assertion as well. Thus AICs are bidirectional.

The following candidate link definitions aren't really necessary, but they do provide examples of weak and strong inferences.

Link, Weak Link: Any two candidates (same digit) which satisfy the weak inference requirement can be thought of as weakly linked. Sometimes the weak link term is reserved for candidates that have a weak inference, but do not have a strong inference. Examples of this latter case are, any two candidates in a cell containing three or more candidates; and any two candidates that are the same digit sharing a house(s) that contain at least three of that digit. This distinction is not really necessary, but it seems to be historical, so what are you going to do. Simple candidates which are said to "see" each other are at least weakly linked.

Strong Link, Conjugate Link: Historically, this is a link between two candidates, A and B, which satisfies the following relationship. "A = not B". This is really overkill, since that relationship satisfies both the weak inference and the strong inference requirements. Don't be confused by the fact that a strong link can be used for a weak inference--once again, it is terribly hard to buck tradition. Examples of strong links are, the two candidates in a cell that contains only two candidates; and two candidates, which are the same digit and are the only two candidates of that digit in a house. A strong/conjugate link is a wildcard link that can be used for either a strong or a weak inference.

Inverse Link, Converse Link, Strong-Only Link:This is a relatively new type of link that comes up with Almost Unique Rectangles and groupings of candidates. This link satisfies the strong inference requirement, but does not satisfy the weak inference requirement.

Deductions

Quite simply, at least one or the other (possibly both) of the two endpoint candidates (or candidate premises) of an AIC is true. Any deductions that you can make based on that are valid. This tends to produce the best results if the endpoints either share a group, or if the endpoints involve the same candidate. When your chain endpoints satisfy one of those conditions, it is time to check for any deductions.

If the two endpoints candidates are weakly linked, then you have an AIC loop. In this case, you could cut the loop at any weak link and end up with a valid AIC. Thus, for every weak link in the loop, either one or the other of the candidates joined by that weak inference are true, and you can make all appropriate deductions based on that.

That is pretty much all you need.

Examples

In the examples below, an '=' indicates where a strong inference is used, and a '-' indicates where a weak inference is used. The capital letters indicate the cell(s) where the premise holds. Many of these have been taken from Jeff's post on B&B loops.

- Code: Select all
`*-----------------------------------------------------------*`

| 247 5 G28 | 479 4789 1 | 6 379 3789 |

| 3 147 6 | 479 45789 2 | 578 179 5789 |

| 17 F178 9 | 3 E578 6 | 2 D157 4 |

|-------------------+-------------------+-------------------|

| 79 6 4 | 5 3 79 | 1 8 2 |

| 129 1239 23 | 8 6 4 | 57 3579 359 |

| 8 379 5 | 1 2 79 | 4 6 39 |

|-------------------+-------------------+-------------------|

| 6 248 1 | 479 479 5 | 3 27 78 |

| 245 2348 H238 |-6 -47 -38 | 9 C257 1 |

|-59 -39 -7 | 2 1 A38 |B58 4 6 |

*-----------------------------------------------------------*

A8=B8-B5=C5-D5=E5-E8=F8-G8=H8

(8)r9c6 = (8-5)r9c7 = (5)r8c8 - (5)r3c8 = (5-8)r3c5 = (8)r3c2 - (8)r1c3 = (8)r8c3

Either the 8 in A (r9c6) or the 8 in H (r8c3) is true, therefore no 8's can exist in r8c456 or r9c123.

- Code: Select all
`*--------------------------------------------------------------------*`

| 39 2 39 | 6 1 8 | 5 4 7 |

| 7 A156 4 | 25 235 -9 |B12 36 8 |

| 156 156 8 | 2457 23457 D24 | 9 36 C12 |

|----------------------+----------------------+----------------------|

| 2689 3 69 | 1 2489 7 | 248 5 2469 |

| 1259 1589 1579 | 24 249 6 | 2347 789 2349 |

| 2689 4 679 | 3 289 5 | 278 1 269 |

|----------------------+----------------------+----------------------|

| 139 -189 2 | 4578 457 E14 | 6 789 39 |

| 4 1689 1369 | 278 27 12 | 137 789 5 |

| 158 7 15 | 9 6 3 | 148 2 14 |

*--------------------------------------------------------------------*

A1=B1-C1=C2-D2=D4-E4=E1

(1)r2c2 = (1)r2c7 - (1=2)r3c9 - (2=4)r3c6 - (4=1)r7c6

Must be either a 1 in A (r2c2) or a 1 in E (r7c6). Therefore there can be no 1 in either r2c6 or r7c2.

- Code: Select all
`*--------------------------------------------------------------------*`

| 247 5 28 | 479 4789 1 | 6 379 3789 |

| 3 1478 6 | 479 45789 2 | 578 179 5789 |

| 17 178 9 | 3 B5678 -A68 | 2 C157 4 |

|----------------------+----------------------+----------------------|

| 79 679 4 | 5 3 679 | 1 8 2 |

| 129 12369 23 | 8 69 4 | 57 35679 359 |

| 8 3679 5 | 1 2 679 | 4 369 39 |

|----------------------+----------------------+----------------------|

| 6 2489 1 | 479 4789 5 | 3 27 78 |

| 245 2348 238 | 6 478 38 | 9 D257 1 |

| 59 39 7 | 2 1 -F389 |E58 4 6 |

*--------------------------------------------------------------------*

A6=B6-B5=C5-D5=E5-E8=F8

(6)r3c6 = (6-5)r3c5 = (5)r3c8 - (5)r8c8 = (5-8)r9c7 = (8)r9c6

Stopped AIC at F to check because A and F share a group (column 6). Chain means either cell A (r3c6) is 6, or cell F (r9c6) is 8. In either case, cell A cannot be 8 and cell F cannot be 6.

- Code: Select all
`pure bilocation loop:`

*--------------------------------------------------*

| 7 58 1 | 2 3 9 | 6 4 58 |

| 6 38 2 | 1 4 5 | 389 89 7 |

| 35 4 9 | 8 6 7 | 23 1 25 |

|----------------+----------------+----------------|

| 4 A123 38 | 369 5 B136 | 289 7 289 |

| 9 235 357 | 37 8 34 | 24 6 1 |

|E18 6 78 | 79 2 14 | 489 5 3 |

|----------------+----------------+----------------|

| 35 9 356 | 36 1 8 | 7 2 4 |

|D128 13 368 | 4 7 C236 | 5 389 89 |

| 28 7 4 | 5 9 23 | 1 38 6 |

*--------------------------------------------------*

A1=B1-B6=C6-C2=D2-D1=E1 (-A1)

(1)r4c2 = (1-6)r4c6 = (6-2)r8c6 = (2-1)r8c1 = (1)r6c1...

Since a weak inference exists between the candidate 1's in cells A and E, the loop is closed, and we know that one of the candidates at either end of each weak inference is true. Therefore, B = 16, C = 26, D = 12, and all 1's in box 4 that are not in A or E can be eliminated.

- Code: Select all
`pure bivalue loop:`

*-----------------------------------------------------------*

| 5 6 29 | 7 3 1 |G29 4 8 |

| 247 248 17 | 5 9 48 | 6 3 12 |

| 349 348 A13 | 48 6 2 | 5 7 H19 |

|-------------------+-------------------+-------------------|

| 367 9 B37 | 2 C47 5 | 1 8 467 |

| 27 25 4 | 68 1 68 | 3 59 579 |

| 16 15 8 | 3 D47 9 |E47 2 56 |

|-------------------+-------------------+-------------------|

| 1234 7 6 | 9 8 34 |F24 15 245 |

| 1349 134 5 | 46 2 3467 | 8 19 479 |

| 8 24 29 | 1 5 47 | 2479 6 3 |

*-----------------------------------------------------------*

A1=A3-B3=B7-C7=C4-D4=D7-E7=E4-F4=F2-G2=G9-H9=H1 (-A1)

(1=3)r3c3 - (3=7)r4c3 - (7=4)r4c5 - (4=7)r6c5 - (7=4)r6c7 - (4=2)r7c7 - (2=9)r1c7 - (9=1)r3c9...

Again, a weak inference exists between the endpoints of the chain, closing the loop. This means that one of the candidates at either end of each weak inference must be true. Kill, in this case, all 7's in row 4 not in B or C, all 4's in column 7 not in E or F, and all 2's in column 7 not in F or G.

- Code: Select all
`mixed loop`

*--------------------------------------------------------------------*

| 1 37 8 | 4 2 9 | 5 37 6 |

| 36 45 9 |D58 36 7 |C48 1 2 |

|A27 45 26 | 1 36 58 |B3478 9 34 |

|----------------------+----------------------+----------------------|

| 348 2 135 | 38 9 468 | 16 356 7 |

| 347 6 137 | 237 5 24 | 123 8 9 |

| 9 378 357 | 2378 1 26 | 236 4 35 |

|----------------------+----------------------+----------------------|

| 378 378 2367 | 9 4 125 | 367 23567 135 |

| 5 9 237 | 6 8 12 | 347 237 134 |

|F26 1 4 |E25 7 3 | 9 256 8 |

*--------------------------------------------------------------------*

A7=B7-B8=C8-D8=D5-E5=E2-F2=A2 (-A7)

(7)r3c1 = (7-8)r3c7 = (8)r2c7 - (8=5)r2c4 - (5=2)r9c4 - (2)r9c1 = (2)r3c1...

Here, we have a weak inference between the endpoints of the chain because they both lie in the same cell. Because the loop is closed, we can say A = 27, B = 78, 8's not in C or D can be eliminated from row 2, 5's not in D or E can be eliminated from column 4, and 2's not in F or E can be eliminated from row 9.

- Code: Select all
`Carcul's initial AUR example`

167 2 B13478| 468 3489 468 | 5 79 168

156 A138 9 | 7 358 2568 | 246 246 1268

567 H478 H478 | 24568 4589 1 | 79 3 268

-----------------+-----------------+-----------------

4 15 126 | 13 7 58 | 1236 2568 9

3 59 16 | 458 2 4589 | 16 58 7

8 1579 127 | 13 6 59 | 123 25 4

-----------------+-----------------+------------------

127 6 C38 | 9 1458 24578| 247 247 D235

1279 G147 G147 | 256 F15 3 | 8 2679 E256

279 38 5 | 2468 48 24678| 24679 1 236

A3=B3-C3=D3-D5=E5-F5=F1-G1=aur=H8

(3)r2c2 = (3)r1c3 - (3)r7c3 = (3-5)r7c9 = (5)r8c9 - (5=1)r8c5 - (1=4&7)r8c23 -UR- (4&7=8)r3c23

The almost unique 47 rectangle in r38c23 means that if neither of r8c23 is 1, then one of r3c23 is 8, a strong inference. Chain stopped for examination because A and H are both in box 1. Chain means that either A (r2c2) is 3 or one of the H cells (r3c23) is 8. In either case, A cannot be 8.

Next is a recent Ruud Daily Nightmare

- Code: Select all
`ALS example`

*-----------*

|.6.|5..|.1.|

|...|3..|..4|

|..8|.9.|2..|

|---+---+---|

|4.7|2..|...|

|.5.|.7.|.8.|

|...|..9|1.7|

|---+---+---|

|..3|.4.|6..|

|1..|..7|...|

|.8.|..5|.2.|

*-----------*

*--------------------------------------------------------------------*

| 2379 6 49 | 5 28 48 | 3789 1 389 |

| 259 179 159 | 3 1268 168 | 589 79 4 |

| 35 14 8 | 7 9 14 | 2 356 356 |

|----------------------+----------------------+----------------------|

| 4 A139 7 |-2 -1568 -1368 | 359 3569 3569 |

|A69 -5 A169 | 146 7 B36 | 349 8 2 |

| 8 23 26 | 46 56 9 | 1 3456 7 |

|----------------------+----------------------+----------------------|

| 59 79 3 | 18 4 2 | 6 579 18 |

| 1 249 24569 | 689 36 7 | 34589 3459 3589 |

| 679 8 469 | 169 136 5 | 3479 2 139 |

*--------------------------------------------------------------------*

A3=A(1&6&9)-B6=B3

(3=1&6&9)r4c2,r5c13 - (6=3)r5c6

The cells marked with an A form an ALS where there are N+1 digits in N cells. Either A contains a 3 or A must contain 1 & 6 & 9. The 6 in B sees all of the 6's in A so they are weakly linked. The AIC endpoints tell you that either A or B contains a 3, thus any cell seeing all the 3's in A & B cannot be a 3.

- Code: Select all
`LA Times 5-20-06: r.e.s.'s AUR & ALS chain solution`

*-----------*

|3..|9..|..7|

|..6|1.7|.49|

|...|8..|.5.|

|---+---+---|

|7..|6..|...|

|64.|...|.13|

|...|..2|..4|

|---+---+---|

|.7.|..9|...|

|83.|4.5|6..|

|5..|..1|..2|

*-----------*

Simple Sudoku - all singles then gets stuck here:

*--------------------------------------------------*

| 3 158 -148 | 9 45 6 | 18 2 7 |

| 2 58 6 | 1 35 7 | 38 4 9 |

|A149 19 7 | 8 2 34 | 13 5 6 |

|----------------+----------------+----------------|

| 7 2 C13 | 6 134 34 | 9 8 5 |

| 6 4 5 | 7 9 8 | 2 1 3 |

| 19 B189 C138 | 5 13 2 | 7 6 4 |

|----------------+----------------+----------------|

|-14 7 C14 | 2 6 9 | 5 3 8 |

| 8 3 2 | 4 7 5 | 6 9 1 |

| 5 6 9 | 3 8 1 | 4 7 2 |

*--------------------------------------------------*

A4=aur=B8-C8=C(1&3&4)

(4=1&9)r3c12 -UR- (1&9=8)r6c12 - (8=1&3&4)r467c3

Cells, such as r1c3 & r7c1 which see both the 4 in A and the 4 in C cannot be a 4. The AUR (19) is in r36c12, and the ALS is in the cells marked with C must either contain an 8 or will contain the 1&3&4 locked set.

Hopefully this very simple set of rules will help, both newcomers and those confused by all of the various methods out there, to make chain deductions as easily as the pros.

[Edits - made notation more compact, and added new example. Augmented definition of weak and strong inferences. Added alternate notations. Further augmented weak and strong inferences so that it becomes useful for nets as well as chains. Fixed comments on first ALS example. Replaced my goofy notation with Eureka notation]