Nice loops for intermediate level players - Grouped x-cycle

Advanced methods and approaches for solving Sudoku puzzles

Nice loops for intermediate level players - Grouped x-cycle

Postby Jeff » Tue Jan 03, 2006 9:35 am

A Grouped x-cycle is an x- cycle with grouped nodes in boxes. It can be of any length. It can be continuous or discontinuous.

Grouped x-cycle is equivalent to grouped colouring (Double Dragon) as described here.

Due to its simplicity, like xy-chain and x-cycle, grouped x-cycle is a subset of nice loops that can be identified without the need of a bilocation/bivalue plot.

In a grouped x-cycle, nice loop propagation always follows alternate links with 'strong inference' and 'weak inference' (refer definitions of 'link', 'strong link', 'strong inference' and 'weak inference' here). A link with strong inference or weak inference can enter or leave a grouped node (ie. a node made up of 2 to 3 cells) in a box, eg.

......[node A]-x-[node B]=x=[node C]-x-[node D]=x=[node E]-x-[node F]=x=[node G]-x-[code H].........

where:
[node] = [cell 1] or [cell 1|cell 2] or [cell 1|cell 2|cell 3]
the notation '=x=' is a link with strong inference (+ve label)
the notation '-x-' is a a link with weak inference (-ve label)

In a grouped x-cycle nice loop, if the links propagate alternately in a cyclic manner (ie. no adjacent links are of same type), the loop is said to be 'continuous'.

With continuous grouped x-cycle, candidates can be eliminated outside the loop but within the unit of the links with weak inference (broken lines) as demonstrated below:

A 'discontinuous' x-cycle nice loop has exactly one discontinuity at 2 adjacent links of the same type (ie. both links with strong inference (solid lines) or both links with weak inference(broken line). Nice loop notation for a discontinuous nice loop always starts from the discontinuity.

If the adjacent links are links wih strong inference (solid lines), a candidate can be fixed in the node at the discontinuity, as demonstrated below:

If the adjacent links are links with weak inference (broken links), a candidate can be eliminated from the node at the discontinuity, as demonstrated below:

Nice loop notation:
example 1: [r5c9]-5-[r8c9]=5=[r8c4]-5-[r4c4|r5c4|r6c4]=5=[r5c6]-5-[r5c9] => r5c9<>5
example 2: =[r1c1]-3-[r9c1]=3=[r7c3]-3-[r5c3]=3=[r5c9]-3-[r1c9]=3=[r3c7|r3c8]-3-[r3c2]=3=[r1c1]-
example 3a: [r2c9]=9=[r2c3]-9-[r5c3|r6c3]=9=[r4c1](-9-[r4c9])-9-[r8c1]=9=[r8c7]-9-[r7c9|(r4c9)]=9=[r2c9] => r2c9=9
example 3b: [r7c9]-9-[r2c9]=9=[r2c3]-9-[r5c3|r6c3]=9=[r4c1]-9-[r8c1]=9=[r8c7]-9-[r7c9] => r7c9<>9

Image

In example 3a, candidate '9' appears exactly 3 times in column 9. The expression (-9-[r4c9]) shown in blue is a multiple inference that enables the link [r7c9|(r4c9)]=9=[r2c9] to be treated as a link with strong inference, thus the placement of the '9' in [r2c9].
Last edited by Jeff on Sat May 13, 2006 3:59 am, edited 4 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Example

Postby Jeff » Wed Jan 04, 2006 6:05 am

This broken-wing can be proven by a grouped x-cycle.

Nice loop notation:
[r3c7|r3c8]-2-[r3c5]=2=[r6c5]-2-[r6c9]=2=[r1c9|r2c9]-2-[r3c7|r3c8]
which implies r3c7, r3c8<>2 => r3c5=2

Image

I must admit that I had under-estimated the power of the broken-wing. It is not just a derivative of simple colouring or turbot fish. When it can only be proven by grouped x-cycle, it is not elementary at all and should deserve more credits..:D
Last edited by Jeff on Sat Jan 07, 2006 2:45 am, edited 2 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sat Jan 07, 2006 6:36 am

A fillet-O-fish can be proven by grouped x-cycle.

Nice loop notation:
[r5c4]-1-[r2c4]=1=[r2c2]-1-[r4c2]=1=[r4c4|r4c5|r4c6]-1-[r5c4] => r5c4<>1.

Image

Even the sashimi of a fillet-O-fish can be proven by grouped x-cycle.

Nice loop notation:
[r5c4]-1-[r2c4]=1=[r2c2]-1-[r4c2]=1=[r4c5|r4c6]-1-[r5c4] => r5c4<>1.

Image

I would like to thank Myth Jellies:D and Carcul:D for their contributions to manual sudoku solving. In my opinion, POM is currently the most powerful non-T&E ultimate manual solving technique.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Sat Jan 07, 2006 11:12 am

I like this grouping a lot better than that X-thing that was put in the filet-o-fish post. Just to clarify, filet-o-fish and sashimi can find a whole bunch of new patterns, not just the one shown above. For example, I can return the favor and make an asterisked sashimi X-wing out of your example above.

Code: Select all
+-----------+-----------+-----------+
| 2   .   . | 2   .   . | 2   2  #2 |
| 2   .   . | 2   .   . | 2   2  #2 |
| .   .   . | .  *2   . |-2- -2- *. |
+-----------+-----------+-----------+
| .   2   . | 2   .   . | 2   .   . |
| .   2   . | .   .   . | 2   2   . |
| .   .   . | .  *2   . | .   .  *2 |
+-----------+-----------+-----------+
| .   .   . | .   .   . | 2   2   . |
| .   .   . | .   .   . | .   .   . |
| .   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+


It's viewer's choice whether you want to consider the #-marked 2's as the fin, and the -2-'s the deletion, or vice versa. There is also a 3-1-2 sashimi swordfish here as well.

While POMing out some filets in a generic three-boxes-solved for a digit case, I came up with the following. The first pattern reduces via a Filet-O-Fish swordfish, but the second one doesn't. Perhaps you can find some groups that form x-cycle reductions in these and give us some more cool pictures.

Code: Select all
+-----------+-----------+-----------+
| .   2   2 | .   2   2 | .   2   2 |
| .   2   2 | .   2   2 | .   2   2 |
| .   2   2 | .   2   . | .   2   . |
+-----------+-----------+-----------+
| .   2   . | .   2   . | .   2   . |
| .   2   2 | .   2   2 | .   2   2 |
| .   2   . | .   2   . | .   2   . |
+-----------+-----------+-----------+
| .   .   . | .   .   . | 2   .   . |
| .   .   . | 2   .   . | .   .   . |
| 2   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+

+-----------+-----------+-----------+
| .   2   2 | .   2   2 | .   2   2 |
| .   2   2 | .   2   2 | .   2   2 |
| .   2   2 | .   2   . | .   .   . |
+-----------+-----------+-----------+
| .   2   . | .   2   . | .   2   2 |
| .   2   2 | .   2   2 | .   2   2 |
| .   2   . | .   2   . | .   2   2 |
+-----------+-----------+-----------+
| .   .   . | .   .   . | 2   .   . |
| .   .   . | 2   .   . | .   .   . |
| 2   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+


One other question. X-cycles with groups seems to be a big gun. As with most big guns, the real trick is figuring out when to begin testing with it, searching for patterns and trying different groupings; and when to give up on it, and move on to something else. Any advice there?
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Sun Jan 08, 2006 12:58 pm

Myth Jellies wrote:While POMing out some filets in a generic three-boxes-solved for a digit case, I came up with the following. The first pattern reduces via a Filet-O-Fish swordfish, but the second one doesn't. Perhaps you can find some groups that form x-cycle reductions in these and give us some more cool pictures.

Hi MJ, Since a 3-3-3 swordfish is a continuous poly-implication chain with 3 trilocation triangles, the fillet-O-fish in the first grid cannot be expressed as a simple grouped x-cycle. However, it can be expressed a grouped almost swordfish nice loop as follows:

[r1c2|r2c2]-2-[almost swordfish:r3c258|r4c258|r6c258]=2=[r3c3]-2-[r1c2|r2c2] => r1c2<>2 and r2c2<>2

There is no deduction possible using nice loops for the second grid.
[Edit: This statement has been proven wrong by Carcul & Vidarino, refer here.]


Myth Jellies wrote:One other question. X-cycles with groups seems to be a big gun. As with most big guns, the real trick is figuring out when to begin testing with it, searching for patterns and trying different groupings; and when to give up on it, and move on to something else. Any advice there?

The good thing about nice loop is that it can be identifed without having to test any candidates. With difficult grids that involve all 9 digits, bilocation/bivalue plot is constructed to assist with the pattern recognition process. With x-cycles, since it only involves 1 digit, you should be able to just highlight the cells that contains the digit under consideration. This can either be done on paper or using the filtering function of a solver such as Simple Sudoku. With grouped x-cycles, candidate groups can easily be overlooked and therefore all linkable grouped nodes should be highlighted too.
Last edited by Jeff on Sat Jan 14, 2006 2:19 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Mon Jan 09, 2006 6:06 pm

Here is an example of a continuous grouped x-cycle where x=4:

Image

Continuous nice loop notation:
=[r5c2]-4-[r6c1]=4=[r6c8]-4-[r9c8]=4=[r9c1|r9c3]-4-[r7c2]=4=[r5c2]-
implies r4c1<>4, r7c1<>4 and r8c3<>4

Notes:
The link [r6c8]-4-[r9c8] is a strong link which is being treated as an weak inference.
Elimination of candidates for a continuous loop is outside the loop but within the units of the links with weak inference.
No elimination is available in column 8.
Last edited by Jeff on Fri Jan 20, 2006 12:30 pm, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sat Jan 14, 2006 6:23 am

Code: Select all
+-----------+-----------+-----------+
| .   2   2 | .   2   2 | .   2   2 |
| .   2   2 | .   2   2 | .   2   2 |
| .   2   2 | .   2   . | .   .   . |
+-----------+-----------+-----------+
| .   2   . | .   2   . | .   2   2 |
| .   2   2 | .   2   2 | .   2   2 |
| .   2   . | .   2   . | .   2   2 |
+-----------+-----------+-----------+
| .   .   . | .   .   . | 2   .   . |
| .   .   . | 2   .   . | .   .   . |
| 2   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+

Refer here for 2 excellent grouped x-cycles identified by Carcul & Vidarino for the above grid.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Sat Jan 14, 2006 10:48 am

Thanks Jeff.

Keep the good work.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Sun Jan 22, 2006 8:09 am

Here is a very heavy going example of a grouped x-cycle identified by Carcul, which has utilised multiple inferences and an almost x-wing.

[r1c7](-2-[r1c6])(-2-[r1c2])-2-[group:r78c7]=2=[group:r8c89]-2-[r8c6]=2=[almost x-wing:(r1c6)(r1c2)r46c26]-2-[group:r46c789]=2=[r5c7]-2-[r1c7] => r1c7<>2.

where
(-2-[r1c6])(-2-[r1c2]) are 2 multiple inferences.

Code: Select all
+----------------+----------------+----------------+
| .    2b"  2    | 2    2    2b   | 2A   2    2    |
| .    .    2    | 2    2    .    | 2    2    2    |
| .    .    2    | 2    2    .    | 2    2    2    |
+----------------+-----------------+---------------+
| .    2X   2    | 2    2    2X   | 2B   2B   2B   |
| .    .    2    | 2    2    .    | 2C   .    .    |
| .    2X   2    | 2    2    2X   | 2B   2B   2B   |
+----------------+----------------+----------------+
| .    .    .    | 2    2    .    | 2b'  .    .    |
| .    .    .    | 2    2    2d'  | 2b'  2c'  2c'  |
| 2    .    .    | .    .    .    | .    .    .    |
+----------------+----------------+----------------+
Last edited by Jeff on Sun Mar 12, 2006 2:52 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Sun Jan 22, 2006 8:56 am

Here is a little warning.

You have to be careful with these almost X-wing groups not to use four cells all in one box. Though the grid below looks like it might work, the X group cannot be treated as an almost X-wing because it cannot contain two true values (on opposite corners). Thus X being true would not imply that all of E was false.

Code: Select all
+----------------+----------------+----------------+
| .    2    2    | 2E   2E   2F   | 2A   2    2    |
| .    .    2    | 2E   2E   .    | 2    2    2    |
| .    .    2    | 2E   2E   .    | 2    2    2    |
+----------------+-----------------+---------------+
| .    2    2    | 2    2    2    | 2    2    2    |
| .    .    2    | 2    2    .    | 2    .    .    |
| .    2    2    | 2    2    2    | 2    2    2    |
+----------------+----------------+----------------+
| .    .    .    | 2X   2X   .    | 2B   .    .    |
| .    .    .    | 2X   2X   2D   | 2C   2C   2C   |
| 2    .    .    | .    .    .    | .    .    .    |
+----------------+----------------+----------------+
This would be an invalid grouping
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Wed Mar 01, 2006 5:49 pm

Image

Here is an example of a grouped x-cycle with a multiple inference.

[r4c9]-6-[r56c7](=6=[r6c4]-6-[r5c5])=6=[r7c7]-6-[r7c5|(r5c5)]=6=[r1c5]-6-[r2c6]=6=[r2c9]-6-[r4c9] => r4c9<>6

Proof:
r56c7=6 => r4c9<>6
r56c7<>6 => r6c7<>6 => r6c4=6 => r5c5<>6
r56c7<>6 => r7c7=6 => r7c5<>6 (with r5c5<>6 from above) => r1c5=6 => r2c6<>6 => r2c9=6 => r4c9<>6
Therefore, r4c9<>6

where:
[r56c7] is a grouped node.
[r56c7](=6=[r6c4]-6-[r5c5]) is a multiple inference.
[r7c5|(r5c5)]=6=[r1c5] is a strong inference due to the multiple inference on [r5c5]
Last edited by Jeff on Sat May 13, 2006 4:04 am, edited 5 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Thu Mar 02, 2006 9:46 am

This picture, as is, does not quite work for me.

I don't see how you get to declare the link along column 5 as a strong link unless you are considering r57c5 a grouped node, in which case I would think you should draw it that way. It would seem to be okay to consider a column group that spans two boxes so long as you are showing separate exiting linkages for cells from different boxes when the links do not follow the column.

Also noted that your strong link from r56c7 to r6c4 is really an "inverse link" that you cannot make into a weak link, similar to what you see in a type 5 uniqueness pattern. That is to say that it satisfies the strong link's "not A implies B" requirement, but you could not say that "A implies not B". Interesting to note that if only one cell in your group has a strong conjugate link to another cell, then the whole group still has a strong inverse-type link to that cell.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Thu Mar 02, 2006 2:17 pm

Hi MJ, I hope the proof added to the original post would clarify the situation.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Sat Mar 04, 2006 7:49 pm

Jeff wrote:I hope the proof added to the original post would clarify the situation.


(I am going to refer to your conversion of the weak links along column 5 as a "magic" conversion. It is done just for reference, and I don't mean to imply that it is an invalid move...only that I'm unsure about it.)

The proof certainly shows that r4c9 <> 6. I had no problem with that. My issue is the "magic" conversion of the links along column 5 from an obvious pair weak link to a pair of strong links.

If you draw your picture like this...
Code: Select all
.  .  . | .  6d . | .  6  6
.  .  . | .  .  6c| .  .  6b
.  .  6 | .  .  . | .  .  .
--------+---------+--------
.  6  . | 6  .  6 | .  .  6a
.  6  . | .  6e . | 6h 6  .
.  .  . | 6f .  . | 6h .  .
--------+---------+--------
6  .  . | .  6e . | 6g .  6
6  .  . | 6  .  . | .  .  .
6  .  . | .  .  6 | .  6  .

...then you have...
Code: Select all
                  (row 5 e) - f
                 /             \
a - b = c - d = e                = h - a
                 \             /
                  (row 8 e) - g

...and you only have to explain that you can decompose your group 'e' into subgroups when you fork into multiple threads. Something that seems fairly easy to digest.

Your magic conversion of the two weak links into two strong links is quite possibly legitimate as well, but in that case, maybe you don't need to bother with groupings at all. For example could you use two weak links between 'a' and the individual components of 'h' and magically convert what would otherwise be weak links from the components of 'h' to 'g' into strong links? Thus there would be no need for groupings at all in the diagram.

So, for your diagram, what I really want to know is what are the rules which allow you to convert weak links into strong links.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Sat Mar 04, 2006 9:37 pm

Myth Jellies wrote:.....My issue is the "magic" conversion of the links along column 5 from an obvious pair weak link to a pair of strong links........Your magic conversion of the two weak links into two strong links is quite possibly legitimate as well.....

Hi MJ, In my deduction, there was only one strong link due to a multiple inference. Are you referring to the 2 end nodes and counting it two instead of one? The move may be regarded as a conversion, or a result of multiple inference.

Myth Jellies wrote:......maybe you don't need to bother with groupings at all. For example could you use two weak links between 'a' and the individual components of 'h' and magically convert what would otherwise be weak links from the components of 'h' to 'g' into strong links? Thus there would be no need for groupings at all in the diagram.

Yes, I could have used multiple inference instead of grouped inference in this case. There are 2 issues which cause me to always consider using grouped inference first:

  • The nice loop notation of a grouped inference is always easier to understand than a multiple inference.
  • Once a multiple inference is applied, the loop can no longer be called a forcing chain; it can only be a net.
Whereas a grouped inference should only be applied to a link between 2 nodes, a multiple inference could involve 3 nodes or more.

Myth Jellies wrote:So, for your diagram, what I really want to know is what are the rules which allow you to convert weak links into strong links.

The simple rule of a strong inference applies: "if a candidate 'x' in the preceding nodes is false, then candidate 'x' in the following node is true".
Jeff
 
Posts: 708
Joined: 01 August 2005

Next

Return to Advanced solving techniques