SudokuWiki.org
Strategies for Popular Number Puzzles
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.
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.
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
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.
At the point it's also worth re-capping something about Continuous Alternating Inference Chains. Firstly, its doesn't matter which way you walk round the loop - clockwise or anti-clockwise, secondly, it doesn't matter which cell you start with and 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 the chain:
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.
At the point it's also worth re-capping something about Continuous Alternating Inference Chains. Firstly, its doesn't matter which way you walk round the loop - clockwise or anti-clockwise, secondly, it doesn't matter which cell you start with and 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 the chain:
- Clockwise with D3 ON +4[D3]-4[D7|D8|D9]+4[F8]-4[J8]+4[J2]-4[G3]
- Clockwise with D3 OFF -4[D3]+4[D7|D8|D9]-4[F8]+4[J8]-4[J2]+4[G3]
- Anti-clockwise with D3 ON +4[D3]-4[G3]+4[J2]-4[J8]+4[F8]-4[D7|D8|D9]
- Anti-clockwise with D3 OFF -4[D3]+4[G3]-4[J2]+4[J8]-4[F8]+4[D7|D8|D9]
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.
Nice Loops Rule 1
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
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.
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
Nice Loop Rule 2
In Figure 4 we have a an X-Cycle on 2 (a 2-Cycle) with a group of two [G2|H2] 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 E1 must be a 2.
X-CYCLE on 2 (Grouped Discontinuous Alternating Nice Loop, length 8):
-2[E1]+2[E4]-2[H4]+2[J5]
-2[J3]+2[G2|H2]-2[F2]+2[E1]
- Contradiction: When 2 is removed from E1 the chain implies it must be 2 - other candidates 6 can be removed
X-CYCLE on 8 (Grouped RC Discontinuous Alternating Nice Loop, length 8):
-8[G9]+8[B9]-8[A8]+8[A2]
-8[D2|E2]+8[D1]-8[G1]+8[G9]
- Contradiction: When 8 is removed from G9 the chain implies it must be 8 - other candidates 1/6 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.
Nice Loop Rule 3
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
Consecutive Grouped Cells
A particularly nice Grouped X-Cycle on 2 appears in this puzzle. Row G shows that we can occasionally expect to see two Grouped Cells in the same unit consecutively - provided the entry and exits are available. One will be positive (ON) and the other negative (OFF).
+2[H2]-2[A2]+2[C1|C2|C3] -2[C8]+2[H8|J8]-2[G7|G9] +2[G1|G3]-2[H2]
When H2 is set to 2 the chain implies it cannot be 2 - it can therefore be removed
Patrick Fischer sent me this puzzle
To finished off I must include this brilliant find by Klaus Brenner.
Eight Grouped Cells in a single X-Cycle on 4.
+4[F7]
-4[A7|B7]+4[C8|C9]
-4[C1|C2]+4[A3|B3]
-4[H3|J3]+4[G1|G2]
-4[G8|G9]+4[H7|J7]
-4[F7]
- Contradiction: When F7 is set to 4 the chain implies it cannot be 4 - it can be removed
Note: we can also see a contradiction at the start when F7 is set to +4: it not only causes -4[A7|B7] it also causes -4[H7|J7] so when the chain swings round to make +4[H7|J7] we have conflict and that also proves F7 cannot be 4.
Comments
... by: LameGoat
BTW this site is awesome!
See this page
... by: Markismus
Looking at the example, I think the 4's at E7, G5, G6, E4, D4 and C5 can be removed, too, right? Doesn't really matter where you choose the discontinuity.
I read it as a rule 3 discontinuity, with F7 being the doubly weak-linked point, but it could also be a rule 1, continuous X-cycle deleting all 4's caught on the lines and column's of the X-cycle.
This example also seems to show that every eliminated value in an continuous X-cycle can also be thought of as being part of a rule 3, discontinuity, leading to its elimination.
Yes, if you continue with take step and undo all other strategies as they are used you get back to the same X-Cycle with those other 4s being the cause of a discontinuity, and they get picked off one at a time. That's because the solver is/can only look at one discontinuity at a time. One could re-program the algorithm to clean up in a single step but that would make it less easy to see the steps. As a human you can remove them all for those reasons.
... by: Str8tsFan
(1) There is (as far as I can understand it) a mix-up at the description text: the cells G2 and D3 should be the other way round.
You are writing:
"The first is aligned on column 3 and points to G2. The second points along the row to D3."
It should be:
"The first is aligned on column 3 and points to D3. The second points along the row to G2."
(2) The load example link is wrong. If you use it, you will get a sudoku with an additional solved 8 set at C7, which obviously prevents the solver from reproducing figure 3.
(3) If you fix that manually and give it a try, the solver finds a different grouped X-Cycle:
-8[D8]+8[D3]-8[J3]+8[J5]-8[H4|H5|H6]+8[H8]-8[D8]
Maybe your comment (Tuesday 1-Nov-2011) is the reason for that. And maybe you should talk about "removing a candidate which is part of the pattern" right there, as it is completely unmentioned up to this point of your documentation of strategies.
(4) I'm still wondering about how to discribe that a number was taken off a cell because of a weak link using at least one group. At your example you are writing:
"- Off-chain 8 taken off E3 - weak link: G3 to D3"
But there is no weak link G3 to D3, we are using the weak link [G3|J3] to D3. I'm wondering if naming the correct group instead of randomly one single cell of the group would help a lot more to understand the solving. That would be like this:
"- Off-chain 8 taken off E3 - weak link: [G3|J3] to D3"
Of course, I don't know if the solver is refusing to name the group, or if your text of the example is just not quite correct, as I couldn't reproduce the situation with the solver at all.
... by: Eric
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.
... by: Andrew Stuart
Such eliminations can lead one down the wrong path if it is a grouped cell in an AIC so I continue to disallow this.
... by: Anton Delprado
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.
... by: Filolexes