SudokuWiki.org
Strategies for Popular Number Puzzles
X-Cycles (Part 2)
So far, I been looking at X-Cycles which alternate perfectly all the way round. There are two interesting rules that lead to eliminations when we identify an imperfection in a loop which is called a discontinuity.
A discontinuity occurs when we find two strong links next to each other (that is, with no weak link between them) or two weak links next to each other (with no strong link dividing them). These rules work only if there is exactly one discontinuity, and such a loop will always have an odd number of nodes.
'Discontinuity' doesn't mean that the loop is broken or that it's not chain; it refers only to the imperfection that would otherwise make links alternate strong/weak/strong, and so on.
A discontinuity occurs when we find two strong links next to each other (that is, with no weak link between them) or two weak links next to each other (with no strong link dividing them). These rules work only if there is exactly one discontinuity, and such a loop will always have an odd number of nodes.
'Discontinuity' doesn't mean that the loop is broken or that it's not chain; it refers only to the imperfection that would otherwise make links alternate strong/weak/strong, and so on.
Nice Loops Rule 2
If the adjacent links are links with strong inference (solid line), a candidate can be fixed in the cell at the discontinuity.
This rule allows us to know the solution of a certain cell absolutely, no matter how many other candidates there may be on that cell. Unlike the case of the first Nice Loop rule, we are not looking at a mass of eliminations outside the loop; instead, this rule tells us something about the loop itself. Let’s look at an example before examining the logical proof.
For discontinuous X-Cycles, the notation always starts with the discontinuity. In Figure 1, our Nice Loop on number 1 is:
X-CYCLE on 1 (Discontinuous Alternating Nice Loop, length 6):
-1[J1]+1[G3]-1[E3]+1[E8]-1[J8]+1[J1]
- Contradiction: When 1 is removed from J1 the chain implies it must be 1 - other candidates 3/9 can be removed
We have two strong links joined at J1; therefore, J1 is 1. One way to make sense of this logically is to trace round the alternative. If J1 was not a 1 G3 and J8 would have to be 1s. That would remove the candidate 1 from E3 and oblige E8 to be a 1. But hang on - that forces two 1s in column 8. A contradiction so the 1 must exist in J1.
Nice Loops Rule 3
Our third rule dictates what happens when two weak links form a discontinuity in a loop:
If the adjacent links are links with weak inference (broken line), a candidate can be eliminated from the cell at the discontinuity.
The solver would return this message:
X-CYCLE on 1 (Discontinuous Alternating Nice Loop, length 6):
+1[C3]-1[C7]+1[G7]-1[G2]+1[H3]-1[C3]
- Contradiction: When C3 is set to 1 the chain implies it cannot be 1 - it can be removed
X-CYCLE on 8 (Discontinuous Alternating Nice Loop, length 6):
+8[B7]-8[B1]+8[C3]-8[E3]+8[E7]-8[B7]
- Contradiction: When B7 is set to 8 the chain implies it cannot be 8 - it can be removed
Weak and Strong Links
X-Cycles introduced the idea of Weak and Strong links but I want to make a more precise definition of terms since there are subtleties which will be useful in other chaining strategies. The rough and ready distinction between Strong and Weak links is to do with how many candidates are in a unit – namely, Strong links are formed when only two are present, while three or more imply a Weak link.
From a strong link we can infer that
if not A, then B
From a weak link, we can infer only that
if A then not B, C, D according to how many candidates there are in a unit
This implies that:
However, the following is also true that for a strong link:
if A, then not B
So, some Strong links can be reversed to give us a "link with weak inference" - if the occasion calls for it. It is perfectly logical to assert on a unit with two candidates of X both:
In Figure 5 we have an array of 6 candidates on a board. A number of strategies can show that the 6 on H9 can be eliminated. I have coloured some cells using Simple Colouring Rule 2 which link up some pairs on the board - either all of the yellow cells will be 6 or all of the cyan cells will be 6. Since H9 can see C9 (yellow) and H5 (cyan) it cannot be a 6 since it can see cells with both colours.
From a strong link we can infer that
if not A, then B
From a weak link, we can infer only that
if A then not B, C, D according to how many candidates there are in a unit
This implies that:
- Strong links are "links with strong inference"; and
- Weak links are "links with weak inference".
However, the following is also true that for a strong link:
if A, then not B
So, some Strong links can be reversed to give us a "link with weak inference" - if the occasion calls for it. It is perfectly logical to assert on a unit with two candidates of X both:
- If Not A then B (!A =>B)
- If A then Not B (A => !B)
In Figure 5 we have an array of 6 candidates on a board. A number of strategies can show that the 6 on H9 can be eliminated. I have coloured some cells using Simple Colouring Rule 2 which link up some pairs on the board - either all of the yellow cells will be 6 or all of the cyan cells will be 6. Since H9 can see C9 (yellow) and H5 (cyan) it cannot be a 6 since it can see cells with both colours.
If a strong link can have weak inference, then let’s just change the link from C4 to A5 to imply such. Simple. We get our pattern. If 6 is on C4, then it is not on A5 (weak inference), or if it is on A5, then it is not on C4 (also weak inference – and all very logical).
I have coloured the Strong link with weak inference red in Figure 5.
X-Cycle Exemplars
These puzzles require the X-Cycle strategy at some point but are otherwise trivial.They also require just one Naked Pair.
They make good practice puzzles.
Comments
Comments TalkMonday 17-Jan-2022
... by: Anonymous
While yes Rule 3 covers all eliminations from rule 1 and 2, the first two types are much useful overall so it's better to look for them first.Tuesday 10-Nov-2020
... by: Ed Logg
Your rule for Nice Loops Rule 2 can be extended. If you have any even number of links in a row you can remove all entries in every other strong link. So in the example below:5.9..8.14...9..53.3..25.987.5.1..8.....4851791...2.45.8..5..7.1.156.73.8.7.81..95
When you remove 2 & 4 at G8, you can also remove the 2 at A7!
Wednesday 20-May-2020
... by: Robert
Hi there,I have recently discovered this fascinating website, and found it immensely useful. I have written my own software, and am continuing to improve it, more for my own understanding than any other reason.
It seems to me that the x-cycles with two consecutive weak links subsumes the other two cases. If you have two consecutive strong links, just let one of them be "pseudo-weak", then there are two consecutive weak links. Together with "last cell in a unit", this gets you as much inference as the two consecutive strong-link case.
An x-cycle with alternating strong-weak links (no discontinuity) can also be used as a special case. With this type of loop, you can eliminate the value from any cell with links to a "red" or "green" cell in the loop. But we can just construct a loop that goes from the "red" cell to the one that is off the loop, back to the "green" cell, then around the loop in one direction or the other. In one of the two directions, this leads to a loop with an odd number of links, and two consecutive weak links (or strong links that can be treated as weak). The "off loop" cell is the one that is between the two weak (or pseudo-weak) links. So the value is eliminated from this cell, which is the same thing that happens if we use the loop with the even number of links, alternating strong and weak.
I have also convinced myself that the stipulation in the text, that no cell occurs in the loop twice (I started to picture such a configuration as a "figure eight") is not restrictive - any such configuration can be broken into two loops, and together with "only value in a cell" or "only cell in a unit", we get at least as much inference from the two sub-loops as we do from the "figure eight" loop. So not allowing a cell to occur twice costs us nothing.
I cannot convince myself that it is possible to ignore loops where there are links between non-consecutive cells. Such loops could also be broken into distinct sub-loops, but it seems to me in some cases, you do not get the same inference from the two sub-loops that you get from the overall loop.
The x-loop with two consecutive weak links also would seem to completely subsume the two rules of the simple chain strategy.
How does all that sound?
Great work, glad I came across this site!
Tuesday 15-Mar-2016
... by: YBB
"Load Example" (or "From the Start ") for Figure 2 (& 3) do not show the shown exampleThursday 24-Apr-2014
... by: Lou Maser
In Figure 5, how do we know which strong link to use with weak inference when multiple choices present themselves? Note that the link from C4 to C9 could also qualify as a weak link here but would give us an incorrect result. With the benefit of your analysis in Figure 5 we can easily work out which link to change, but what about starting from scratch, and, especially, given more complicated chains; will it always be so easy? How can we be sure we always choose correctly and get the right result?Thursday 14-Mar-2013
... by: megmrl1
Allow me to put aside the "rules" for the moment. Constuct a loop with 5 nodes A to E and with all links strong. I then have the contradiction of (A) implies (not B) implies (C) inplies (not D) implies E implies (not A). But I also have a contradiction (B) implies (not C) implies (D) implies (not E) implies (A) implies (not B). Rule or not I have a contradiction what ever is assigned and A or B or C or D or E must be assigned.Friday 4-May-2012
... by: djinks
I 'm still not sure how to pick candidates for a loop. For example, why is the 6 at G4 not linked in Figure 5?Monday 12-Dec-2011
... by: Eric
@Roger: Figure 2 now contains a nice loop on 1 (although the figure title states differently)@Gary: You are right. If a link is strong it implies that the link also meets the conditions of a weak link. Please note that a weak link becomes strong if and only if 2 candidate locations are left in any row, column or box
@patriotkiller18: The best way to understand, is to forget that the 2 sixes in box 2 are connected by a strong link. Then notice that the 2 sixes in box 2 are connected by a weak link: If A5 contains a 6 than C4 cannot contain a 6, and if C4 contains a 6, then A5 cannot contain a link.
Another way to overcome your problem is simply a redefinition of the X-Cycle requirements: An X-Cycle is a series of links hopping from one candidate to another, where at least an alternate series of strong links exist. I am afraid this might be a bit too theoretical, so I suggest you just forget about the stong link in box 2.
Tuesday 28-Jul-2009
... by: roger freeman
Hello to you.In 'x-cycles pt2'/nice loop rule3/fig2, concerning elimination of candidate 3 in cellB6, where two weak links converge; can this loop be routed thro cellC6 and therefore allow that candidate 3 also be eliminated in cellC6.
Sorry if I'm being v silly. If another loop thro' cellC6 and elimination of
candidate3 at that cell is not legitimate, could you explain please.
I feel fearful of serious confusion!
Many thanks indeed for your site.
Bests,Roger Freeman
Corbridge,Northumberland
Monday 27-Apr-2009
... by: Gary Maness
I would like to point out that ALL strong links, by definition have a weak inference.!A=>B ~ A=!B
But not all weak inferences are strong ones,
A=>!B !~ !A=B.
Am I right? I think I remember proving this in my foundations of Mathematics course.
Saturday 11-Apr-2009
... by: patriotkiller18
I cannot understand how the 2 sixes is box 2 can be a weak link in any way. I understand what your saying if not a then b, but that's every strong link. I know I am the problem but do you have any further examples or info about where i can go to get more details. thank you very much for this site, it must take alot of your time and it is appreciated.