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
Order Str8ts Book 1
Order Now!
Order Str8ts Book 2
Order Now!
  Grouped X-Cycles
Chaining strategies such as 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 - Off-Chain Eliminations. The output from the solver says:

X-CYCLE (Grouped Alternating Inference Chain) Rule 1:
-4[A4]+4[A9]-4[J9]+4[J6]
-4[E6]+4[D4|E4]-4[A4]
- Off-chain 4 taken off C9 - weak link: A9 to J9
- Off-chain 4 taken off H9 - weak link: A9 to J9
- Off-chain 4 taken off H6 - weak link: J6 to E6
- Off-chain 4 taken off C4 - weak link: D4 to A4
 Figure 2: 4-Cycle with Grouped Cells
Figure 2: 4-Cycle with Grouped Cells: Load Example or : From the Start
The Grouped node is [D4|E4] and it points up column 4 to A4 (a weak link since there is another 4 at C4. Three 4s can be eliminated in one fell swoop since all 4s that are on units with links of weak inference can go. These are highlighted in yellow.
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 [G7|G8|G9]-8[G2] and [G3|J3]. The first is aligned on column 3 and points to G2. The second points along the row to D3. All other 8s in any unit shared by any of the Weak links can be removed (Nice Loop Rule 1).

X-CYCLE (Grouped Alternating Inference Chain) Rule 1:
-8[D3]+8[D8]-8[H8]+8[G7|G8|G9]-8[G2]+8[G3|J3]-8[D3]
- Off-chain 8 taken off C8 - weak link: D8 to H8
- Off-chain 8 taken off E8 - weak link: D8 to H8
- Off-chain 8 taken off G8 - weak link: D8 to H8
- Off-chain 8 taken off G3 - weak link: G7 to G2
- Off-chain 8 taken off E3 - weak link: G3 to D3
- Off-chain 8 taken off F3 - weak link: G3 to 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 6):
+1[C9]-1[H9]+1[H3]-1[A3|B3]+1[C2]-1[C9]
- Contradiction: When C9 is set to 1 the chain implies it cannot be 1 - it can be removed 		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, but the grouped node [B1|C1] on 8 makes the chain possible. 8 is eliminated on J1.

AIC on 8 (Grouped Discontinuous Alternating Nice Loop, length 10):
+8[J1]-8[J4]+8[H5]-8[B5]+4[B5]-4[A6]+4[A3]-8[A3]+8[B1|C1]-8[J1]
- Contradiction: When J1 is set to 8 the chain implies it cannot be 8 - it can be removed

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 8-Cycle
Figure 5: Grouped 8-Cycle: Load Example or : From the Start
Nice Loop Rule 3

Rule 3 tells us that two weak links joined at H8 imply 2 can be removed from that cell. But the interesting part of the chain is the grouped cell in [A8|B8]. The chains comes along row 3 from C4 (ON) and forces 2 to be OFF in C9. That still leaves two more 2s in box 3, but they are nicely aligned on column 8. So we don't care which one may be the solution, only that they point down the column to H8.

X-CYCLE on 2 (Grouped Discontinuous Alternating Nice Loop, length 6):
+2[H8]-2[H4]+2[C4]-2[C9]+2[A8|B8]-2[H8]
- Contradiction: When H8 is set to 2 the chain implies it cannot be 2 - it can be removed 		Figure 6: 2-Cycle with Grouped Cells
Figure 6: 2-Cycle with Grouped Cells: Load Example or : From the Start
If you want to continue reading about this strategy family, the next chapter is entitled Alternating Inference Chains.
 
Comments

Monday 12-Dec-2011

... by: Eric

The text at figure 3 does not match with the figure:
I see groups {G2,G3} and {G8,H8}.

Concerning elimination of G3 and G8 in figure 3:
I think this elimination is solved by Nice Loop Rule 3 for the following series:
1. For elimination of G3: D3 - D8 - {G8-H8} - G9 - G3 (which is a 5-nodes Grouped X-Cycle with 2 weak links ending up at G3)
2. For elimination of G8 (after elimination of G3):
D3-D8-G8-G2-J3 (which is a 5-node standard X-Cycle with 2 weak links ending up at G8).

So it is perfectly right to eliminate G3 and G8, but I don't think that you needed to adapt your solver for this situation.

Tuesday 1-Nov-2011

... by: Andrew Stuart

I’ve tweaked the solver to allow eliminations of elements of a grouped cell - I have today tested this extensively because this is unusual. Normally I don’t allow an elimination of any candidate that forms part of the ‘pattern’ that finds eliminations. But in the case of grouped cells in X-Cycles this did not lead to any false positives. The example that prompted me to check is is Figure 3 above. Many thanks to Mario Anselmi for pointing me in the right direction.

Such eliminations can lead one down the wrong path if it is a grouped cell in an AIC so I continue to disallow this.

Tuesday 5-Jul-2011

... by: Roman Malyniak

Should not the 4 in cell C4 in Fig. 2 be removed ?
Tuning the 4's ON/OFF in Fig. 4 indicates this.

Andrew Stuart writes:

Yes you are correct. Sorry it took so long to see your comment, for some reason the alert are not coming through. Solver updated as of 1st November 2011

Monday 16-May-2011

... by: Anton Delprado

It should be noted that it is possible for the node of interest in rule 2 and 3 to in fact be a group of cells. If you have type 3 with a group then it is fairly intuitive that none of the group can be the chaining value.

It is a slightly more complicated for type 2 because only one of the cells in the group will have the chaining value. However this means that any cell that "sees" the entire group cannot have the chaining value.

Monday 5-Jul-2010

... by: Filolexes

In the "more complex example" (the grid with A1=3), there exist only two possibilities: the continuous nice loop can proceed clockwise or counterclockwise. Clockwise, the 8 in D8 becomes true, which kills the 8 in G8. Counterclockwise, the 8 in G2 becomes true, which again kills the 8 in G8. Therefore, this loop yields another kill: the 8 in G8 can be removed. Via a similar argument, the 8 in G3 can also be removed.

 Post a Comment using Facebook...
or post a Comment or Question here...
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

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.


Article created on 12-April-2008. Views: 25796
This page was last modified on 31-January-2012, at 18:18.
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