SudokuWiki
SudokuWiki.org
Strategies for Popular Number Puzzles

XY-Chains

XY-Chain example 1
XY-Chain example 1 : Load Example or : From the Start
The Y-Wing Chains are infact part of a more encompassing strategy called XY-Chains. The commonality is the same pincer-like attack on candidates that both ends can see and that the chain is made of bi-value cells. With Y-Chains the hinge was expanded to a chain of identical bi-value cells but in an XY-Chain these can be different - as long as there is one candidate to make all the links. The "X" and the "Y" in the name represent these two values in each chain link.

The example here is a very simple XY-Chain of length 4 which removed all 5's highlighted in yellow. The chain ends are 5 A7 and C2 - so all cells that can see both of these are under fire. It's possible to start at either end but lets follow the example from A7. We can reason as follows

  • If A7 is 5 then A3/C7/C9 cannot be.
  • if A7 is NOT 5 then it's 9, so A5 must be 2, which forces A1 to be 6. If A1 is 6 then C2 is 5.

Which ever choice in A7 the 5's in A3/C7/C9 cannot be 5. The same logic can be traced from C2 to A7 so the strategy is bi-directional, in the jargon.

XY-Chain example 2
XY-Chain example 2 : Load Example or : From the Start

This next Sudoku puzzle contains an entertaining series of XY-Chains, starting with this rectangular one. It proves that 8 must be in either B3 or B8 and therefore we can remove the other three 8s in row B. Starting on B3 if that cell is either 8 or 6. If it is 6 then D3 must be 4 which pushes 2 into D8 which in turn makes B8 8. You can trace this from B8 back round for the same effect. A nice short XY-Chain, but as the next example shows, these four cells are a rich seam.
Same cells - different XY-Chain
Same cells - different XY-Chain : Load Example or : From the Start

Looking at exactly the same starting cell it appears we can make further eliminations, this time 6s in column 3. We go clock-wise, this time, round the rectangle. It proves 6 will either be on B3 or D3.

If you want to finish the puzzle by yourself, look out for a third elimination with those same four cells using 2s on column 8, or step through with the solver.

XY-Chains Exemplars

These puzzles require the XY-Chains strategy at some point but are otherwise trivial.
They also require one Naked Pair (except for #5).
They make good practice puzzles. Thanks to Klaus Brenner for number 5

Go back to Y-Wing ChainsContinue to 3D Medusa


Comments

Comments
Talk

... by: Regan

Thursday 14-Dec-2023
Found an exemplar for 12 length chain (link opens straight to the point where you need the chain):

https://www.sudokuwiki.org/sudoku.htm?bd=2i240i8141g10611090a44480h11210681g1g1811109050341210h110i8ig10o058841214109211103810hg10505g18g210o41110a828q0i0541g11o210q922q604805811og10q128o11g103210o880541

REPLY TO THIS POST

... by: Nick

Friday 10-Nov-2023
I’m struggling to complete puzzles that need a y wing or xy chain to complete , How do you spot these ? Are there any tips ?
REPLY TO THIS POST

... by: Andy Potvin

Tuesday 3-Jan-2023
For Exemplar 5, in its current orientation, my solver only needed 6 XYchain's.

RU S# DL Technique Details (only showing steps requiring Dlevel>=UR1=9)
37 18 45 XYchain:8 eliminated 6 from p25 via chain p23 p53 p73 p93 p99 p39 p35 p45.
37 19 45 XYchain:8 eliminated 8 from p79 via chain p73 p53 p23 p26 p46 p45 p35 p39.
37 20 37 XYchain:5 eliminated 5 from p78 via chain p73 p93 p99 p39 p79.
37 21 37 XYchain:5 eliminated 2 from p19 p29 via chain p39 p99 p93 p73 p79.
37 22 37 XYchain:5 eliminated 8 from p19 via chain p39 p79 p73 p93 p99.
37 23 37 XYchain:5 eliminated 7 from p17 p27 p89 via chain p87 p99 p39 p79 p19.

And if I transform the matrix/puzzle (in MATLAB notation to transpose(fliplr(Mp))) my solver needs only 4 XYchain's: one 8-link followed by 3 5-link.

I haven't yet developed a function to find the "simplest" solution possible. (And I don't have any plans to develop such a function.)

Best,
Andy




REPLY TO THIS POST

... by: Pieter, Newtown, Oz

Saturday 30-Jul-2022
Hi Andrew
Where has my head been at? Only just discovered the new Fireworks strategy 8 months later!!! 🙁

Anyway, this comment is re a possible bug!? In your daily example for 2022-07-16, we reach this board which finds an XY-Chain length 9 eliminating the 6 in F7. However, the solver does so via 3 sides of a previously discovered X-Wing "box", whereas it could have simply gone via one side and been of length 7. Curious!

Kudos as always for your fantastic and always expanding Solver!!!

Ciao, Pieter
REPLY TO THIS POST

... by: Anonymous

Friday 1-Apr-2022
Hi! I was trying to make a sudoku with a XY-Chain of length 4, and accidentally found a puzzle with one of length 12! Here is the link if you are interested
Andrew Stuart writes:
Thanks! - [Del]
Add to this Thread

... by: ush

Wednesday 13-Oct-2021
Today's XY chain stated: 10/13/21
XY-Chain
length=4, chain ends: B7 and J8
This proves 8 is the solution at one end of the chain or the other
-8[B7]+9[B7]-9[F7]+7[F7]-7[F8]+9[F8]-9[J8]+8[J8]
8 taken off A8
8 taken off G7
8 taken off J7

However cell B6 was also 89...so why can it be ignored as not the start or end of the '8 ' chain? I thought a chain has to go as far as it can before you decide where it started or ends.
REPLY TO THIS POST

... by: Bondye

Saturday 3-Jul-2021
I have crafted a puzzle that includes 10 xy-chains (and several wings and 3Dmedusa). check it out here
REPLY TO THIS POST

... by: Gordon

Sunday 27-Sep-2020
I have noticed that in XY chains, if the two pincers share the same 2 numbers, and these numbers are also contained in the target cell, then both can be eliminated. I don't know if you have this mentioned elsewhere, but your solver missed such an opportunity on a puzzle I ran through it this morning, and only eliminated the first number - (4) and not the second one (7).
REPLY TO THIS POST

... by: AB

Sunday 13-Sep-2020
I'm not sure if I'm understanding this correctly, but isn't this just a special case of X-Cycles Rule 3, where all the strong links are within cells, and the candidates to be eliminated can be joined to the two ends of the XY-Chain by weak links (thus forming a loop with a discontinuity of two weak links)? Or does X-Cycles in your solver not consider links between candidates in the same cell?
Anonymous replies:Sunday 9-Jan-2022
Strong links within cells are outside the scope of X-cycles, as X-cycles is a single digit technique.
Add to this Thread

... by: Mike Hopkins

Wednesday 2-Sep-2020
I am rather proud of the output from my solver program when fed the first of the examples on your page:

XY chain: initial candidates X and Y are (5) and (3).
Chain is: A7(5,9), A5(2,9), A1(2,6), C2(5,6),
No other cell in the common scope of the two ends of that chain can be (5).
C7 was (3,5,9) is now (3,9)

XY chain: initial candidates X and Y are (5) and (6).
Chain is: C2(5,6), A1(2,6), A5(2,9), A7(5,9),
No other cell in the common scope of the two ends of that chain can be (5).
A3 was (2,4,5) is now (2,4)
C9 was (3,5,6) is now (3,6)

Happy to share the source code, it is (Ada)

REPLY TO THIS POST

... by: Robert

Sunday 21-Jun-2020
Thought about this one, it seems to be a somewhat strange special case of alternating inference chains.

We can define links in two ways - they can be between the same value in two different cells in the same row, column, or box, or they can be between different values within the same cell. We get three of the strategies described at this website by using different definitions for strong and weak links.

(1) Strong links required to be between different cells, weak links also required to be between different cells - original "nice loops". In the database of 100 puzzles I am using, 60 are solved this way.

(2) Strong links can be either between different cells or within the same cell, weak links can also be either between different cells or within the same cell - alternating inference chain. Of my 100 puzzles, 89 are solved this way.

(3) Strong links required to be within the same cell, weak links required to be between different cells - xy_chain. Of my 100 puzzles, 45 are solved in this way.

In (3), "strong links" refer to links that are required to be strong, and "weak links" refer to those that are not required to be strong. If a "weak" link happens to be strong, it still follows the rule for weak links, not strong links.

But there are three other combinations of strategies that I don't see described at the website. However, it was a pretty each job to modify my alternating inference chain software to handle them.

(4) Strong links required to be between different cells, weak links required to be within the same cell. Of my 100 puzzles, 21 are solved this way.

(5) Strong links can be either between different cells or within the same cell, weak links are required to be between different cells. Of my 100 puzzles, 80 are solved this way.

(6) Strong links are required to be between different cells, weak links can be either between different cells or within the same cell. Of my 100 puzzles, 83 are solved this way.

So there are three additional strategies :) Although (1), (3), (4), (5), and (6) are also special cases of (2), alternating inference chains. Simple colouring is also a special case of nice loops, and therefore of alternating inference chains. Medusa without Rule 6 is also a special case of alternating inference chains.
Anonymous replies:Sunday 9-Jan-2022
It's not at all strange when you think about it. Since there are strong links within cells, they are bivalue cells. Bivalue cells are also ALSs, which allows us to extend this technique to ALSs and not just bivalue cells, which is exactly what the ALS-XY-Chain technique does.

And it is very useful to split strategies into X-cycles, Colouring, Medusa and all that, as it simplifies things and you can look for the more common patterns first.
Add to this Thread

... by: John

Friday 1-May-2020
In the first example, you stop progressing the chain as soon as you find a confluence, i.e. you could have continued to H2, H5 etc with this chain. Is this just a programmer decision for efficiency, or is there some underlying reason?

Can an XY-Chain therefore consist of as little as 3 cells?
Anonymous replies:Sunday 9-Jan-2022
Eliminations depend on the two ends of the chain. You could extend the chain, but it would not get us any more eliminations. And an XY-chain can contain as few as three cells, but that is the same as an XY-wing / Y-wing.
Add to this Thread

... by: Eli

Wednesday 4-Mar-2020
very thankful
REPLY TO THIS POST

... by: pie314271

Sunday 1-Dec-2019
Through attempting to make various sudoku puzzles, I've wondered if the maximum length for an XY-chain is 12. Every time I've seen these chains, most of them only hit 12 at most. Is there a proven maximum on the XY-chain length?
Andrew Stuart writes:
In fact that is a limit in my solver due to concerns over CPU usage. I cap it. I do have another version of the solver (well, same solver, just a flag) which looks for chains in a breath-first-tree order which has no limit and I've seen chains in the 20 links or more. Uses much more memory and I'm reluctant to make it the default solver on the site. One day maybe. - [Del]
Add to this Thread

... by: Kavala

Thursday 18-Jul-2019
I don't know if this has already been mentioned, however...

Often you can find an XY Chain, but it is one that does not result in an elimination.
This chain can still be useful, however, when combined with a 3D Medusa chain.

For example, if one end of the XY Chain has a known color that is part of a 3D Medusa
Chain, then the other end of the XY Chain can be assumed to be the opposite color.
This helps extend the reach of the 3D Medusa in situations where that is not possible
following the usual logic of the 3D Medusa.
REPLY TO THIS POST

... by: kvnviktor

Wednesday 2-Jan-2019
Exemplar 3, x4 (score 113) Avoidable Rectangle Type 1: 4/8 in r3c12,r7c12

in the third example, the death rectangle c12, g12, numbers 8 and 4 in the corners
REPLY TO THIS POST

... by: TG

Wednesday 17-Oct-2018
You're a really helpful web site; couldn't make it without ya!
REPLY TO THIS POST

... by: CH

Sunday 7-Oct-2018
Just simply needed to emphasize Now i'm pleased I stumbled in your web site.
Andrew Stuart writes:
Thanks! - [Del]
Add to this Thread

... by: Mike Van Emmerik

Wednesday 17-Feb-2016
> So both ends can be filled in.

Oops. I don't have time right now to sort out why, but it's not always that both ends can be filled in. So you just get the usual "must be opposite colour" information, and that often allows one end to be filled in, sometimes both.
REPLY TO THIS POST

... by: Mike Van Emmerik

Tuesday 16-Feb-2016
Guy Renaldon posted:
"At first I select a bi value cell. Not anyone, but rather one containing two candidates regarding the digits missing the most. "

I agree that when attempting to solve puzzles manually (say with a phone app), it helps to cut down the forest of possibilities by considering first those bi-valued cells that there are less commonly represented. I now scan through the candidate numbers noting which numbers have the fewest unsolved cells. I'm not sure that both candidates for the initial bi-value cell need to be rare, just one of them. In fact, the last puzzle I did involved one of the rarer numbers paired with the most common unsolved number.

There is an additional "sanity check" that I like to perform. With the rarer numbers, there are often only a few viable starting pairs, and often some of these can be eliminated by eye as being involved in a strong link, or otherwise already related as opposite in colour. If you start with one such candidate bi-value cell, you are likely, after some effort, to prove something that you knew trivially to be true already. By contrast, if the candidates are already "like coloured" by simple colouring (X chains), meaning that you believe that one or the other is the solution, they make good candidates since if you can prove they are XY-chain linked (e.g.. this cell could be a 6, but if not it's a 4 so that has to be a 2 ... and this has to be a 6, then you've proved that each end is either a 6, or it's a 6. So both ends can be filled in. No doubt you can make stronger general statements about the other elements in the chain, but these tend to take care of themselves.

With these two checks reducing the effort needed to find these XY-chains, they are becoming more fun and much less of a chore.
REPLY TO THIS POST

... by: Steve

Wednesday 5-Aug-2015
Thanks very much for your website, which has been a delight as well as a great education.

I believe I have found an alternative solution to Exemplar 3 on www.sudokuwiki.org/XY_Chains that requires only 1 XY-chain (or is it something else?) rather than four.

After all simpler strategies have been exhausted, I have the following chain:
1 on F2 -> 2 on F4 -> 8 on F8 -> 5 on F1 -> 4 on E3 -> 9 on E5
Alternatively, a 9 on F2.
So, any cell that can see F2 and E5 (i.e. E2 and F5) cannot contain a 9.

When I remove the 9s in these cells, the remainder of the Sudoku is solved with simple strategies.

I've checked this in the solver and it works. Have I got it right?

Cheers,

Steve Strain
Memphis, TN USA
REPLY TO THIS POST

... by: Eric

Monday 6-Apr-2015
Considering example 1 and building an XY-chain starting in A1 and ending in A5, we would be driven to remove candidate 2 from A3. Such a chain is made of bi-value cells and A3 sees both ends of the chain, which show a different color for candidate 2.

What is the additional condition to be statisfied by an XY-chain that is not met by the A1-A5 chain?
REPLY TO THIS POST

... by: Sherman

Friday 11-Apr-2014
Shum and Andrew - the number of cells in the chain does NOT have to be even. See Figure 22.1 on page 62 of "The Logic of Sudoku" for an example with 5 cells: 78, 86, 65, 53, 37 which removes 7 from any cell that sees both ends of this chain. Also, all Y-Wing chains, which are a subset of XY chains, have an odd number of cells.
REPLY TO THIS POST

... by: Shum

Sunday 29-Dec-2013
This isn't stated, but it seems to me a necessary condition is the length of the chain must be even (referring to the number of cells, not the number of links). All the examples here have length 4 and the alternate coloring seems to imply this restriction. Agree?
Andrew Stuart writes:
That is a good observation but I fail in my documentation to include longer examples. I think I was hung up on finding short simple ones and now I realise that I should show they can be several lengths. I also believe they will contain an even number of cells in total. I will have a hunt in my 2014 stock for longer ones and also try and find a crazy super length one, there has to be a 'longest' - [Del]
Add to this Thread

... by: suneet shrotri

Monday 21-Oct-2013
I have discovered a new method to eliminate a possibility by 2 chains with one common end & other 2 ends are part of a set then if common end is not X then if in some cases other ends come to have XY possibilities then possibility X can be eliminated from other remaining members of the set. I am sure that no other method on this website can do this.
REPLY TO THIS POST

... by: gg fuller

Tuesday 11-Jun-2013
I'm unsure about the description as it mentions it is a more encompassing version of "Y-Wing Chains" and also refers to "Y-chains". Since there are no such strategies described on this site, I don't know if that refers to "Y-wing" or "X-chains" or both. If I just look for XY-chains will that catch all Y-Wings and X-chains, or is X-chains separate? X-chains seems to require a loop to make any eliminations.
Andrew Stuart writes:
Hi, yes there is a page, click here but I subsumed this into the more general chaining strategies and that opening line needs to be edited. This goes way way back to the early days. - [Del]
Add to this Thread

... by: Guy Renauldon

Thursday 2-Jun-2011
The Exclamation Mark Method

This is to answer to François Tremblay and John Robinson question.

Yes François, there is a trick to discover an XY chain.

Recently, I settled a kind of method which I name the “Exclamation Mark Method”

That is what it is:

At first I select a bi value cell. Not anyone, but rather one containing two candidates regarding the digits missing the most.

Let’s say the cell I select contain “a” and “b” as candidates.

Then I make a double bet.
First bet: “a” true,
Second bet: “b” true.

Regarding the first bet, I draw a small vertical line “I” just under the “a” of the bet cell. Then I consider the other bi values cells only and I mark all the candidates deducted by this first bet by an “I”, drawn just under the candidates.

Regarding the second bet “b” I do the same but the mark will be a small point “.”under the “b” in the bet cell.

Most of the time, soon or later, if a XY chain exists, I obtain a cell containing a candidate marked with an exclamation mark “!” (This is the reason of the name of my “method”, although the exclamation mark can be reverse, the point on the top)

So a candidate , let’s say “k”, will be marked with an exclamation mark. It means it is true in both bets. So “k” is a true digit. (Although I can’t say anything on “a” or “b”). Most of the time, this true digit will solve the Sudoku, when the Sudoku is not difficult too much.

But I do not consider the job as finished. I have to find my XY chain.

Let’s see the simplest case at first: the cell where we have the “!” is a bi value cell too. I consider the other candidate in that cell, the one without the “!”, let’s say “m”. “m” have to be eliminated, so “m” must see two other bi value cells containing an “m”, which will be the two ends of my XY chain (to understand that, you have to know what an XY chain is exactly). Then I consider each end of my chain and I follow the reverse itinerary from each end. I draw the links between the bi value cells really, with a pen. Doing so I’ll automatically reach my double bet cell. And that it is, I’ve drawn my XY chain! Very easily, without the headaches y suffered before I applied that method. And doing so, you can find very long XY chains, containing ten links for example, or more.

Note that you can find a shorter chain which does not go through the double bet cell, but with the same ends. The reason is that more than one XY chain exists on a same grid most of the time.

If the cell which sees the two ends of the chain is not a bi value cell, it is a little bit more complicated. But the “method” works too. If the cell contains three candidates, you will have two candidates marked with an exclamation mark. Then the third candidate can be removed. If a cell contains four candidates, you’ll find three exclamation marks in that cell. Generally speaking, if the cell contains N candidates, you’ll find N-1 candidates with an exclamation mark. The other one left without the “!” can be removed. This chain does not give a true digit directly.

Sorry, I’ve been little bit long in my explanation, and please excuse my English, being French (perhaps François Tremblay will understand me better, his name sounding very French …)

I’d like to add some remarks, if Andrew Stuarts give me some more place.

1/An xy chain is in fact a multi value X Cycle in three dimension, containing bi values cells only from one end to the other. The strong links are located inside the bi value cells. The other links can be either strong or weak, except the links between “m”, which must be weak. In fact it is a special AIC, with bi value cells only.
3/ This “method” is not mine…in fact it is the well known Forcing Chain Strategy. But the exclamation mark trick is mine, I think.

Many thanks to Andrew Stuart if he accepts to publish my comment, which maybe he can find a bit too long and not very clear (it is to me, but may be not to all the readers due to my bad English…).

Guy Renauldon
REPLY TO THIS POST

... by: John Robinson

Sunday 30-Jan-2011
I have the same question as Francois Trembly on 28-Oct-2009
REPLY TO THIS POST

... by: S.Monta

Tuesday 18-Jan-2011
Hello,

First i would like to thank you very much for your great website witch made me dramatically improve my Sudoku skills.
I have a question : could the chain 56-67-67-78-83-89-96 be an XY-Chain?
REPLY TO THIS POST

... by: Marshal L. Merriam

Wednesday 8-Sep-2010
I think I have another type of xy chain. In a sudoku I'm doing now (not one of these examples), I find the sequence 28-87-73-36-68-82 where the first pair and the last are the same cell! If its value were 8, then xy chain logic demands that it also be 2, a contradiction. No such contradiction prevents it being 2.

Alternatively we could argue that the xy chain demands that at least one of the endpoints be a 2. Since they are the same, the cell must be a 2.
REPLY TO THIS POST

... by: Marshal L. Merriam

Monday 30-Aug-2010
I now understand Anton's confusion. It stems from the explanation of example 1. I would add one more bullet:

If C2 is not 5 then it must be 6. A1 cannot be 6, A5 cannot be 2 and A7 cannot be 9. Ergo, if C2 is not 5, then A7 must be 5. As noted in the first bullet, if A7 is not 5 then C2 must be 5. So either A7 or C2 must be 5.

When stated this way, the chain does not require locked sets. If C2 is not 5, then no other cell in box 1 can be 6, so even if there were a 6 at B3(say), all of the bullets would still hold.
REPLY TO THIS POST

... by: Marshal L. Merriam

Saturday 28-Aug-2010
Is it fair to say that this technique exposes a new strong link? That is, in the first example 5a7 = 5 c2. In the second, 6A2 = 6C8.

If I haven't overlooked something, this allows XY chains to connect to other single number techniques that use strong link information (eg x- cycles, red-black)
REPLY TO THIS POST

... by: Matt Lala

Monday 16-Nov-2009
I read something on a different site (if I understand this correctly) is that when you reach the end of the chain, you are using the "leftover" value to make your elimination. In the first example, the last green arrow is to a 6, and the leftover in that cell is a 5, which is what gets eliminated. If the last link had been to the 5, then the leftover is 6, and you cannot use that to end the chain and eliminate the 5's. Not sure what conditions are needed for the start. I may be wrong on this.

Francois, I don't think you need a solver, but it does help to have a program that highlights all of them. I glance at the 'busiest' groupings of bivalue cells and then pick one and just start driving. If a fork presents itself I'll choose whichever option seems to steer me back towards the start of the chain.

Anton, I don't think they have to be locked, they just need to be bivalue. Try plugging in a 2 at the start of that chain in the 2nd example, and follow the links, and you'll see how the green cell at the end becomes a 6 (despite the unlocked cells used). And plugging in a 6 at the start makes the eliminations pretty obvious.
REPLY TO THIS POST

... by: Francois Tremblay

Wednesday 28-Oct-2009
I understand the logic but my problem is how do you spot this without the help of a solver? Visually, the start and end of such a chain are tough to find. Do you go through all the grid to start the chain at all possible bi-value cells? In the "simple" cases above, you have respectively 21 & 22 bi-value cells (even your book's example on page 62, figure 22.1 shows 21 of them) which would represent a lot of permutations that only a computer could run through. As a human solver, is there a trick to find those chains?
REPLY TO THIS POST

... by: Anton Delprado

Thursday 18-Jun-2009
Maybe I am missing something but it looks like 4E and 8E are not locked for the value 6 because 9E is potentially 6 as well.

An XY-Chain is possible from this although it would have the pivot chain below:
3A - 3C - 3H - 6H - 6F - 5F - 9F
REPLY TO THIS POST
Article created on 11-April-2008. Views: 333097
This page was last modified on 27-December-2014.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles, Privacy, 2007-2024
Playwire