Strategies for Number Puzzles of all kinds
  Print Version
Solvers
Puzzles
Basic Strategies
Tough Strategies
Diabolical Strategies
Extreme Strategies
Depreciated Strategies
Str8ts
Other
The Logic of Sudoku
  Grouped X-Cycles

This article needs updating in light of changes to the solver in March 2010, particularly the representation of chains

Chaining strategies like X-Cycles use links that connect cells on the board. It is possible to expand on the idea of a "cell" to something a bit larger, namely a "group" of cells. I prefer the word "node" - which in 90% of cases will be a single cell - but can be two or three cells in the same unit. You might wonder how we can use more than one cell and think of it as a node between two links, but there is some cool logic here.

We must go all the way back to Pointing Pairs and Pointing Triples. They attack cells along the row or column on which they are aligned. They also must be in the same box to be a coherent unit. Our “grouped” cells are just Pointing Pairs/Triples and we’re going to use them as part of a chain or Nice Loop.
Clearing the clutter on an example board, in Figure 1, we have a spread of candidate 4s. All the lettered cells are also candidate 4. There is a continuous Nice Loop starting with A. B-C is a weak link, and so is D-E.

The interesting part is the set of cells {X,Y,Z}. It does not matter which of X, Y, or Z (if any) is the solution; any of them will eliminate A and E. Likewise, if E is true, then all of XYZ are gone – and A is true. We can think of {X,Y,Z} as a single node for the purposes of our logic. This promotes the links from A and E to strong links, and the notation for this part of a loop is:

4[F8]=4[D7|D8|D9]=4[D3]=
E     X or Y or Z     A

Figure 1: Grouped X-Cycle
Figure 1: Grouped X-Cycle
The important characteristic is that the cells are all in the same box. One end of the chain (in this case, A) is pointed to by the node cells; the other (in this case, E) is usually within the same box as the node.
Nice Loop Rule 1

Check the article on X-Cycles for a review of Nice Loop Rule 1 in a cycle that does not contain Grouped Nodes.

Figure 2 invokes Nice Loop Rule 1. The output from the solver says:

X-CYCLE on 3 (Grouped Continuous Alternating Nice Loop, length 6):
3[A1]-3[E1]=3[E9]-3[H9]=3[G7|H7]-3[A7]=3[A1]-


The Grouped node is {G7,H7} and it points up column 7 to A7 (a weak link since there is another 3 at B7. Five 3s can be eliminated in one fell swoop since all 3s that are on units with links of weak inference can go.



Figure 2: Grouped 3-Cycle
Figure 2: Grouped 3-Cycle: Load Example or : From the Start
This is a much more complex example, but it does show how powerful the strategy is in tackling a bottleneck on the board. The Nice Loop contains two Grouped nodes at {G3,J3} and {G8,G9}. The first is aligned on column 3 and points to D3. The second points along the row to G2. All other 8s in any unit shared by any of the Weak links can be removed (Nice Loop Rule 1).

X-CYCLE: 8 taken off E8 (link: D8 / H8)
X-CYCLE: 8 taken off E3 (link: G3 / D3)
X-CYCLE: 8 taken off F3 (link: G3 / D3)
X-CYCLE on 8 (Grouped Continuous Alternating Nice Loop, length 6):
8[D3]=8[D8]-8[H8]=8[G8|G9]-8[G2]=8[G3|J3]-8[D3]=



Figure 3: Grouped 8-Cycle
Figure 3: Grouped 8-Cycle: Load Example or : From the Start
Nice Loop Rule 2

Check the article on X-Cycles for a review of Nice Loop Rule 2 in a cycle that does not contain Grouped Nodes.

In Figure 4 we have a an X-Cycle on 1 (a 1-Cycle) with a group of two {A3,B3} usefully working together as a node. This allows us to create a chain linking the coloured cells on this diagram. From Rule 2 we can deduce that H9 must be a 1.

X-CYCLE on 1 (Grouped Discontinuous Alternating Nice Loop, length 5):
1[H9]=1[C9]-1[C2]=1[A3|B3]-1[H3]=1[H9]=
- Discontinuity is two strong links joined at H9, all other candidates (9) can be removed from that cell



Figure 4: Grouped 1-Cycle
Figure 4: Grouped 1-Cycle: Load Example or : From the Start

In my second example in Figure 5 the chain is a little longer and bit more compact, but the grouped node {G4,G5} on 6 makes the chain possible.

X-CYCLE on 6 (Grouped Discontinuous Alternating Nice Loop, length 7):
6[C6]=6[C5]-6[J5]=6[G4|G5]-6[G8]=6[E8]-6[E6]=6[C6]=
- Discontinuity is two strong links joined at C6, all other candidates (8) can be removed from that cell

Rule 2 examples are probably the least likely of the three rules to be found. Most grouped X-Cycles will be two weak links and Rule 3, next.
Figure 5: Grouped 6-Cycle
Figure 5: Grouped 6-Cycle: Load Example or : From the Start
Nice Loop Rule 3

I couldn't resist this example as it has two grouped nodes - {B1,C1} and {E7,F7}. Don't be confused about {F9} and {G9}, they are just adjacent yellow cells that have a weak link on 2. You can see plenty of other 2s in column 9, but a grouped node has to be in the same box.

Rule 3 tells us that two weak links joined at B7 then 2 can be removed from that cell.

X-CYCLE on 2 (Grouped Discontinuous Alternating Nice Loop, length 6):
2[B7]-2[B3]=2[B1|C1]-2[G1]=2[G9]-2[F9]=2[E7|F7]-2[B7]-






Figure 6: Grouped 2-Cycle
Figure 6: Grouped 2-Cycle: Load Example or : From the Start
If you want to continue reading about this strategy family, the next chapter is entitled Alternating Inference Chains.

breakline

Add your comments

A confirmation email will be sent to you after submitting.

Your Name

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

Your comment or question

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. If you want to be remembered, the check box above will store a cookie with your name and email address on your computer.

Line breaks and paragraphs are automatically converted — no need to use <p> or <br> tags.



Article created on 12-April-2008. Views: 9836
This page was last modified on 8-March-2010, at 10:10.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Scanraid Ltd, 2010