Solver App for Android and iPhone Strategies for Number Puzzles of all kinds
 
Print Version Get the SudokuWiki Newsletter
 
Solvers
Puzzles
Basic Strategies
Tough Strategies
Diabolical Strategies
Extreme Strategies
Depreciated Strategies
Str8ts
Other
The Logic of Sudoku
Order Str8ts Book 1
Order Now!
Order Str8ts Book 2
Order Now!
  X-Cycles
X-Cycles are the start of a large family of 'chaining strategies' which are fundamental to solving the harder Sudoku puzzles. X-Cycles are strongly related to Simple Coloring.

A 'chain' is a series of links hopping from one candidate to another following very simple rules. A candidate can either be ON or OFF. That is, we either think it is a possible solution to that cell, or we do not. There are consequences to the rest of the board when we 'link' these two states.
In the X-Wing structure in Figure 1, as an example, we can consider B3 to be OFF. This forces the the 9 in B8 to be ON since it's the only remaining 9 in the row. If B8 is ON then that removes the 9 in H8. Again, the consequence is to turn ON the 9 in H3 - and that closes the loop by forcing the 9 back in B3.

In this X-Wing example three things are apparent. I went round clock-wise, but I could easily make the same logical chain going round from B3 to H3 to H8 to B8 and back to B3. Also, could decide that the start cell was ON and follow the loop round. And lastly, B3 is arbitrary, I could start on any of those four cells.
 Figure 1: Nice Loop on 9
Figure 1: Nice Loop on 9
Another important way of thinking about this situation is from the point of view of the links. When a candidate is turned OFF AND there are only two candidates in the unit, then we can create a Strong link, as between B3 and B8 (marked in a thick blue line) and H8 and H3. Because there are just two 9s in each row, we know that if one is not a 9, the other must be. A strong link is where:
!A => B (if not A, then B)

Weak links are the opposite:

A => !B (if A, then not B)

Strong and Weak links alternate just as candidates are turned OFF and ON. When we turn a candidate X ON we effectively remove ALL other candidates of X in ALL other units. However, when we turn a candidate X OFF it has no effect unless the unit has only two of X in it.

A "Cycle", as the name implies, is a loop or joined-up chain of single digits with alternating strong and weak links, as the X-Wing in Figure 1 shows.

In Figure 2, we have a 2-2-2-formation Sword-Fish re-drawn to show the strong and weak links. The loop characterises the X-Cycle, and the strong/weak links alternate.
 Figure 2: Nice Loop on 4
Figure 2: Nice Loop on 4
Nice Loops have evolved a notation which is useful when accompanying a diagram or as part of an explanation. X is, of course, the digit, and we use the row letter and column number notation to identify cells (e.g., B2, F8). The cells in the loop are linked with a minus to indicated X has been turned OFF, and a + to indicated X has been turned ON - you will see these colours on the solver. An example:

+x[cell 1]–x[cell 2]+x[cell 3]–x[cell 4]

The 2-2-2 Sword-Fish above can be expressed as:

+4[B2]–4[B4]+4[H4]–4[H8]+4[F8]–4[F2]

The only thing not explicit in this notation is that the last cell joins back onto the first cell. Thus, 4[F2]+[B2].
Loops can be of any length but they don't re-use any candidate.

Chains like these that go in a loop are called Continuous. They have three characteristics:
  • Firstly, it doesn't matter which way you walk round the loop - clockwise or anti-clockwise
  • Secondly, it doesn't matter which cell you start with (although the convention is to start with the top left-most cell)
  • Thirdly, each cell could be ON or OFF - as long as you alternate.

Even with the convention of starting with the top left-most cell, there are four ways we could write down a chain:
  • Clockwise with B2 ON +4[B2]-4[B4]+4[H4]-4[H8]+4[F8]-4[F2]
  • Clockwise with B2 OFF -4[B2]+4[B4]-4[H4]+4[H8]-4[F8]+4[F2]
  • Anti-clockwise with B2 ON +4[B2]-4[F2]+4[F8]-4[H8]+4[H4]-4[B4]
  • Anti-clockwise with B2 OFF -4[B2]+4[F2]-4[F8]+4[H8]-4[H4]+4[B4]

I've deliberately used neutral colours in the diagram above (yellow and blue) not to given the impression there only one way to write the same chain. However, the solver will return very positive red and green highlighting but that's because it has discovered one of those four ways first and discarded the other three identical ways.

Here is the notation for the 8-Cycle in Figure 3:

-8[B3]+8[B4]–8[C6] +8[D6]–8[F5]+8[F3]–8[B3]

The yellow cells are units where other 8s can be eliminated, which in this case correspond to the third column and boxes 2 and 5 – because that’s where the weak links are located. 		Figure 3: Nice Loop on 8
Figure 3: Nice Loop on 8
Nice Loops Rule 1

Nice Loops that alternate all the way round are said to be 'continuous', and they must have an even number of nodes. With a continuous X-Cycle, candidates are not removed from the loop since the loop does not have any flaws. Instead we are looking to eliminate on the units that can be seen by two or move cells that belong to the loop.
Figure 4 is a real-life example of an X-Cycle based on 8. The cells with links are in red and green. We can immediately see that C2/C7 is a weak link across the row because of the 8 in C3. G2/H3 is also a weak across the box because of the third 8 in G3. The last weak link is in box 9, J7/H9. Any other 8s in these units can be removed, which makes it a powerful technique. We end up with a loop containing only strong links – a result identical to a Colouring (Singles Chains) solution.

The output from the solver will contain the following information:

X-CYCLE (Alternating Inference Chain):
+8[C2]-8[C7]+8[J7]-8[H9]+8[H3]-8[G2]+8[C2]
- Off-chain candidate 8 taken off C3 - weak link: C2 to C7
- Off-chain candidate 8 taken off C9 - weak link: C2 to C7
- Off-chain candidate 8 taken off G9 - weak link: J7 to H9
- Off-chain candidate 8 taken off G3 - weak link: H3 to G2
 Figure 4: Nice Loop on 8
Figure 4: Nice Loop on 8: Load Example or : From the Start
In summary we can see that

  • X-Wing is a Continuous X-Cycle with the length of four.
  • Sword-Fish of the 2-2-2 formation is a Continuous X-Cycle with the length of six.

Although there are many other parallels as well.


Go back to Remote PairsContinue to X-Cycles (Part 2)



  
   
Comments

Your Name/Handle

Email Address - required for confirmation (it will not be displayed here)

Your comment or question

Please enter the
letters you see:
arrow		Enter these letters Remember me


Please keep your comments relevant to this article.
Email addresses are never displayed, but they are required to confirm your comments. When you enter your name and email address, you'll be sent a link to confirm your comment. Line breaks and paragraphs are automatically converted — no need to use <p> or <br> tags.


Comments - Talk

Friday 25-Jan-2013

... by: snaponit

I second this question:

MONDAY 26-NOV-2012
... by: Hilary
Your site is very helpful. The main problem I have with the puzzles that require diabolical strategies is that I don't know how to pick 'x' for the x-cycle for example. So I usually pick 'x' at random. But to me, that's trial and error and I was wondering if you had suggestions for a systematic approach

Thanks !

Andrew Stuart writes:

That's true, it isn’t always obvious where to start looking and sometimes it jumps out. I'd go for numbers that are thin on the ground. The solver can highlight individual numbers which makes it clearer how to spot the two-per-unit links you need.

Monday 26-Nov-2012

... by: Hilary

Your site is very helpful. The main problem I have with the puzzles that require diabolical strategies is that I don't know how to pick 'x' for the x-cycle for example. So I usually pick 'x' at random. But to me, that's trial and error and I was wondering if you had suggestions for a systematic approach

Thanks !

Tuesday 1-May-2012

... by: Dolores

I am working on Andrew Stuart 8 Ex.1. I do not understand this explanation: X-CYCLE on 5 (Discontinuous Alternating Nice Loop, length 8):
-5[E8]+5[J8]-5[J7]+5[B7]-5[A6]+5[A4]-5[E4]+5[E8]
- Contradiction: When 5 is removed from E8 the chain implies it must be 5 - other candidates 2/4/8/9 can be removed

Also, how do you choose which 5's to include and which to exclude in the chain. Because most of the squares had a 5.

Andrew Stuart writes:

That elimination is an X-Cycle "Nice Loops Rule 2", two string links. An example is at the top of this page.

Basically, if 5 is removed the knock on effect - if you trace it all the way round the chain - is that 5 is put back in that starting place - which is a contradiction. So we can deduce 5 must be the solution to that cell and we can remove everything else.

Monday 27-Feb-2012

... by: Cathy

Figure 1 is missing from your article (the url in the page's source ends in .jpg, but the actual image ends with .png)

Andrew Stuart writes:

Try refreshing your cache or hitting F5 a few times. I've replaced a great number of GIF/JPG image files with PNG. Some are so old they are heavily cached by the server and intermediate servers and probably your browser. I can see requests for the old files in the logs but I am pretty sure all the new images are in place.

Friday 31-Dec-2010

... by: JimS

Laura,

Maybe Andrew answered your question privately or maybe it is posted somewhere else on this site but I thought that I would try to answer your question.

As you follow a continuous, alternating nice loop along the path some of the weak links can actually be strong links -- they just don't have any digits that can be eliminated. Imagine an X Wing which only has digits that can be eliminated in one unit not two.

Andrew might be more accurate if he said "weak or strong links" instead of just "weak links" but that would be cumbersome and wouldn't really help the understanding of the concepts.

Hope this helps.

Friday 12-Feb-2010

... by: Laura

I thought only strong links could have weak interference - not the other way around. I have come across several puzzles in which your solver showed a weak link and it should have been strong- there were only 2 of that number in the square. Is there a special circumstance where this could happen? Please advise thanks

Saturday 11-Apr-2009

... by: ECC

The missing detail in the explanation is that any odd length sequence of strong links counts as a single strong link, except that it cannot close the loop. That is, two consecutive strong links in a loop gives you an answer as described under discontinuous loops, but four does not.

Sunday 5-Apr-2009

... by: Elleda Katan

I'm finding again a problem I have encountered before : what seems like a contradiction between your explanation here and how x-cycles are 'used' in some of the daily puzzles. I'll use 4/5 [todays] as my example but I hit the same problem in 2/28 & elsewhere.
[1] In none of the x-cycle demos is the digit removed from the cells forming the loop. Instead it is eliminated " from cells that can be seen by two or more [loop] cells." In the 4/5 puzzle 7 is eliminated from E1, the beginning and end of the loop.
[2] The end result says your explanation is a loop containing strong links. However, in 4/5, eliminating 7 from E1 destroys the loop.
[3] In the documentation under the 4/5 puzzle, the loop is described as : 7[E1]-7[E4]=7[J4]-7[J3]=7[G1]-7[E1] "Discontinuity is two weak links joined……" However, 7[G1] to 7[E1] is a strong link, not a weak one, no? Shouldn't it read : 7[G1]=7[E1]?
Please I love love love your puzzles and am trying to get smarter at understanding the more advanced strategies, but this confusion has me X-ing out x-cycles from solutions because I am so baffled by them. Thank you for your time.

 Post a Comment using Facebook...


Article created on 12-April-2008. Views: 95665
This page was last modified on 22-June-2012, at 12:12.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles Inc, 2012