View source for X-Chain

From Sudopedia, the Free Sudoku Reference Guide

← X-Chain

You do not have permission to edit this page, for the following reason:

---

You can view and copy the source of this page.

A '''X-Chain''' is a [[single-digit]] [[solving technique]] which uses a [[chain]] consisting of [[link]]s that alternate between [[strong link]]s and [[weak link]]s, with the starting and ending link being strong. In other words, the chain involves an even number of [[cell]]s having the target [[digit]] as a [[candidate]]. The target digit can be [[eliminate]]d from any cell that is seen by both ends of the X-Chain. The X-Chain technique and the [[Multi-Colors]] technique are equally powerful. Also, a X-Chain is also a [[Double Implication Chain]] and an [[Alternating Inference Chain]]. == Example == This is an example of a X-Chain of length six for the digit 3. [[Image:XChain.png]] In this example, the X-Chain is marked using blue lines, with solid lines indicating strong links and dotted lines indicating weak links. In [[Nice Loop]] notation, the X-Chain can be expressed as follows: [r4c4]=3=[r5c5]-3-[r5c9]=3=[r6c8]-3-[r9c8]=3=[r8c7] The two ends of the chain are '''r4c4''' and '''r8c7''', and either end not being 3 will result in the other end being 3. This means that '''r8c4''', which is [[see]]n by both '''r4c4''' and '''r8c7''', cannot contain 3. One proof for this is that we can formulate these two [[Forcing Chain]]s, with the second due to the X-Chain: r4c4=3 => r8c4<>3 r4c4<>3 => r5c5=3 => r5c9<>3 => r6c8=3 => r9c8<>3 => r8c7=3 => r8c4<>3 == X-Chain and Multi-Colors == X-Chain can be replicated by [[Multi-Colors]] by treating each pair of [[cell]]s connected by a [[strong link]] as a color [[cluster]] and [[weak link]]s as [[bridge]]s between clusters. Multi-Colors can be replicated by X-Chain by the reverse of the above, and treating some of the strong links induced by the color clusters as weak links. == Minimum Length of X-Chain == In an ordinary Sudoku, the shortest useful X-Chain that allows eliminations to be made must involve at least four cells. However, in [[Sudoku Variant]]s such as [[Sudoku-X]] and [[Killer Sudoku]], the shortest useful X-Chain can involve only two cells. An example is illustrated in the [[Crossover]] technique for [[Sudoku-X]], made possible due to the [[diagonal]] [[constraint]]s. When we eliminate candidates using a X-Chain of two cells, the same elimination can be performed using [[Common Peer Elimination]]. == See Also == * [[Chain]] and [[Loop]] * [[Multi-Colors]] * [[XY-Chain]] * [[Nice Loop]] * [[Double Implication Chain]] * [[Alternating Inference Chain]] [[Category:Chains and Loops]] [[Category:Solving Techniques]]

Return to X-Chain.