Una XY-Chain attraversa celle bivalore. Ogni passo condivide una cifra con il successivo, come pietre di guado con due lettere ciascuna. È un’altra AIC speciale.
Perché funziona
Se inizi e finisci con la stessa cifra D alle estremità della catena, D non può essere falsa a entrambe le estremità: la catena si contraddirebbe.
Quindi almeno un’estremità è D. Ogni cella che vede entrambe le estremità non può essere D.
Come individuarlo
Passa solo per celle bivalore. La cifra uguale alle estremità è il pungiglione.
Dimostrazione
Trova un percorso di celle bivalore che inizia e finisce con la stessa cifra.
Le celle verdi formano una XY-Chain. La cifra comune alle estremità è 9.
Le due estremità non possono essere entrambe false per 9. Almeno un’estremità è 9: controlla entrambi i mondi lungo il percorso.
Elimina 9 dalle celle che vedono entrambe le estremità (in rosso).
Esempio 1
Percorri una catena bivalore con cifre uguali alle estremità.
Questa XY-Chain elimina 6.
Rimuovi 6 dalle celle che vedono entrambe le estremità (in rosso). Almeno un’estremità deve essere quella cifra.
Esempio 2
Percorri una catena bivalore con cifre uguali alle estremità.
Questa XY-Chain elimina 8.
Rimuovi 8 dalle celle che vedono entrambe le estremità (in rosso). Almeno un’estremità deve essere quella cifra.