Nice loops for elementary level players - the x-cycle

Advanced methods and approaches for solving Sudoku puzzles

Nice loops for elementary level players - the x-cycle

Postby Jeff » Mon Jan 02, 2006 9:19 pm

An x-cycle is a cycle in which all cells are linked by a single digit 'x'. It can be of any length. It can be continuous or discontinuous.

x-cycle is equivalent to all current techniques which operate on a filtered digit such as:

    Simple colouring - Discontinuous x-cycle of length n
    Turbot fish - Discontinuous x-cycle of length 5
    x-wing - Continuous x-cycle of length 4
    Swordfish of 222 formation - Continuous x-cycle of length 6
Due to its simplicity, like xy-chain, x-cycle is a subset of nice loops that can be identified without the need of a bilocation/bivalue plot.

In an 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), eg.

......[cell 1]-x-[cell 2]=x=[cell 3]-x-[cell 4]=x=[cell 5]-x-[cell 6]=x=[cell 7]-x-[cell 8].........

where:
the notation '=x=' is a link with a "strong inference" (+ve label)
the notation '-x-' is a link with a "weak inference" (-ve label)


In an 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 x-cycle, candidates can be eliminated outside the loop but within the unit of the links with weak inference (broken line) as demonstrated below:

Nice loop notation:
example 1 - x-wing: -[r2c2]=5=[r2c6]-5-[r8c6]=5=[r8c2]-5-[r2c2]=
example 2 - swordfish of 222 formation: =[r2c2]-8-[r2c4]=8=[r9c4]-8-[r9c8]=8=[r5c8]-8-[r5c2]=8=[r2c2]-
example 3: =[r2c1]-3-[r9c1]=3=[r7c3]-3-[r7c8]=3=[r5c8]-3-[r5c6]=3=[r3c6]-3-[r2c4]=3=[r2c1]-

Image


A 'discontinuous' x-cycle nice loop has exactly one discontinuity between 2 adjacent links of the same type (ie. both links with strong inference or both links with weak inference).

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

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

Nice loop notation always starts from the discontinuity:
example 4 - turbot fish: [r8c8]=7=[r3c8]-7-[r3c1]=7=[r1c3]-7-[r8c3]=7=[r8c8] => r8c8=7
example 5 - turbot fish: [r3c7]-2-[r3c2]=2=[r6c2]-2-[r6c9]=2=[r2c9]-2-[r3c7] => r3c7<>2
example 6: [r4c8]-4-[r7c8]=4=[r7c1]-4-[r3c1]=4=[r3c6]-4-[r1c4]=4=[r4c4]-4-[r4c8] => r4c8<>4

Image

Demonstrated below is the identification process for x-cycles. From the filtered grid of candidate '6', strong links (shown as double lines, one solid and one broken representing strong and weak inferences respectively) and a link (shown as broken line representing weak inference) are drawn for the '*6'-cells as shown.

Image

An x-cycle has alternate links with strong and weak inferences. Since a strong link has both strong inference and weak inference, the following 5 cases of x-cycle can be identified. The weak inferences selected from strong links are shown in red for clarity.

x-cycle 1 & 2 are equivalent to simple colouring.

Image

x-cycle 3, 4 & 5 are equivalent to turbot fish.

Image

An x-cycle can be proven by double implications. Consider x-cycle No.5 above:

Nice loop notation: [r3c4]=6=[r3c7]-6-[r1c9]=6=[r6c9]-6-[r6c4]=6=[r3c4] => r3c4=6

Proof (Implications can start from any node in the nice loop):
r1c9=6 => r3c7<>6 => r3c4=6
r1c9<>6 => r6c9=6 => r6c4<>6 => r3c4=6
Therefore r3c4=6[/quote]
Last edited by Jeff on Tue Mar 21, 2006 12:22 pm, edited 16 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Mon Jan 02, 2006 9:36 pm

Hi Jeff.

Very nice post. I have just a simple question for you: how do you make those schemes, with the solid and broken lines and the +ve and -ve labels? Do you have a special program for that?

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

Postby Jeff » Mon Jan 02, 2006 9:54 pm

Carcul wrote:how do you make those schemes, with the solid and broken lines and the +ve and -ve labels? Do you have a special program for that?

Thanks Carcul. I used Excel to produce the diagrams.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby rubylips » Tue Jan 03, 2006 12:03 am

Jeff,

A small point - it's not possible to express all swordfishes in terms of chains - check here for a counterexample that caught me out!
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Jeff » Tue Jan 03, 2006 5:14 am

rubylips wrote:it's not possible to express all swordfishes in terms of chains

All swordfishes can be expressed in terms of chains:

222 formation - continuous double implication x-cycle.
322 formation - continuous triple implication x-cycle.
other formations - continuous poly implication x-cycle.
Jeff
 
Posts: 708
Joined: 01 August 2005

x-cycle nice loops: identification process

Postby Jeff » Fri Jan 06, 2006 7:14 am

This post demonstrates the identification process for x-cycles. From the filtered grid of candidate '6' below, conjugate and unconditional links are drawn (in blue solid and broken lines respectively) for the '*6'-cells as shown.

Image

An x-cycle has alternative conjugate and unconditional links. Since a conjugate link can be treated as an unconditional link, the following 5 cases of x-cycle can be identified. The replacement links are shown in red for clarity.

x-cycle 1 & 2 are equivalant to simple colouring.

Image

x-cycle 3, 4 & 5 are equivalant to turbot fish.

Image
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: x-cycle nice loops: proof

Postby Jeff » Fri Jan 06, 2006 7:29 am

This post demonstrates how an x-cycle can be proven by double implications.

Consider x-cycle No.5 in the previous post:

Definitions:
Conjugate link implies if A is false, then B true
Unconditional link implies If A true, then B false

Nice loop notation: [r3c4]=6=[r3c7]-6-[r1c9]=6=[r6c9]-6-[r6c4]=6=[r3c4] => r3c4=6

Proof (Implications can start from any node in the nice loop):
r1c9=6 => r3c7<>6 => r3c4=6
r1c9<>6 => r6c9=6 => r6c4<>6 => r3c4=6
Therefore r3c4=6
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: x-cycle nice loops: identification process

Postby ronk » Fri Jan 06, 2006 11:41 am

Jeff wrote:x-cycle 1 & 2 are equivalant to simple colouring.

x-cycle 3, 4 & 5 are equivalant to turbot fish.

Based on your diagrams, I see no difference between x-cycle 3 and x-cycle 1 & 2. Each has two conjugate links (strong links) separated (connected) by a single unconditional link (weak link). So it seems all three should be tagged the same ... either equivalent to simple colouring or equivalant to turbot fish.

And "yes", I see the coloring differences of the 'unconditional links'. BTW, all five look like turbot fish to me.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: x-cycle nice loops: identification process

Postby Jeff » Fri Jan 06, 2006 12:05 pm

ronk wrote:Based on your diagrams, I see no difference between x-cycle 3 and x-cycle 1 & 2. ................And "yes", I see the coloring differences of the 'unconditional links'. BTW, all five look like turbot fish to me.

Hi Ronk, These x-cycles are all turbot fish simply because simple colouring (as defined in Angus' Simple Sudoku solver) of length 5 is a subset of turbot fish. BTW, turbot fish covers 4 cases and two of them are actually simple colouring.

x-cycle 1 & 2 are equivalent to simple colouring because they make use of the same cells to directly conclude the same deduction as simple colouring.

The deduction of x-cycle 3 cannot not be directly concluded by simple colouring, but can do so by turbot fish similar to x-cycle 4 & 5.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: x-cycle nice loops: identification process

Postby ronk » Fri Jan 06, 2006 1:40 pm

Jeff wrote:x-cycle 1 & 2 ... x-cycle 3 ... x-cycle 4 & 5.

Are we talking about names for the five cases you diagramed ... or a '1, 2, 3, 4, 5' definition elsewhere?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Fri Jan 06, 2006 6:16 pm

Yes, Ronk. I am talking about the 5 diagrams I posted regarding the x-cycle identification process. Weren't you talking about them?
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: x-cycle nice loops: identification process

Postby flip » Sun Jan 08, 2006 2:57 pm

Jeff wrote:This post demonstrates the identification process for x-cycles. From the filtered grid of candidate '6' below, conjugate and unconditional links are drawn (in blue solid and broken lines respectively) for the '*6'-cells as shown.

This refers to the x-cycle on digit 6 with four conjugate links and one unconditional link [r1c9]-6-[r3c7]. It is then shown that 5 cases of x-cycle can be identified (five discontinuous nice loops where one or more conjugate links can be treated as an unconditional link).

My question concerns the original unconditional link [r1c9]-6-[r3c7]. According to the rules for making an unconditional link, there are three cases:
    [1] link two bivalue cells on the same candidate
    [2] link a bivalue cell to the endpoint of a conjugate link(s) with the same label(s)
    [3] link the endpoints of two conjugate links with the same label
For the example given, I do not have a problem with cases 1 and 2. However, in the absence of a candidates list, assuming that case 3 applies, this means that the unconditional link [r1c9]-6-[r3c7] can be made only when the links [r3c4]=6=[r3c6] and [r1c9]=6=[r6c9] are conjugate links.

Does this mean that for case 3 of the unconditional link we cannot apply the turbot fish nice loops 'x-cycle 1' and x-cycle 2' since the conjugate links [r1c9]=6=[r6c9] and [r3c4]=6=[r3c7] are precluded from being treated as unconditional links because the unconditional link [r1c9]-6-[r3c7] is made assuming those two to be conjugate links?

Can someone post a one or more real examples so that this can be tested?

thanks, please ignore if this is a stupid question (this is my first post).

flip
flip
 
Posts: 17
Joined: 08 January 2006

Re: x-cycle nice loops: identification process

Postby Jeff » Sun Jan 08, 2006 5:03 pm

Hi flip, welcome to the forum. I am going to walk you through the process.

flip wrote:My question concerns the original unconditional link [r1c9]-6-[r3c7]. According to the rules for making an unconditional link, there are three cases:
    [1] link two bivalue cells on the same candidate
    [2] link a bivalue cell to the endpoint of a conjugate link(s) with the same label(s)
    [3] link the endpoints of two conjugate links with the same label
For the example given, I do not have a problem with cases 1 and 2. However, in the absence of a candidates list, assuming that case 3 applies, this means that the unconditional link [r1c9]-6-[r3c7] can be made only when the links [r3c4]=6=[r3c6] and [r1c9]=6=[r6c9] are conjugate links.

I can see that you have been following my posts regarding bilocation/bivalue plot. Please let me clarify that what you have listed there are not rules for making unconditional links. They are steps for constructing unconditional links on a grid as part of a bilocation/bivalue plot. The complete set of construction steps is shown in this post, which I am listing below for easy reference.
1) Use solid lines and +ve labels to show conjugate links.
2) Use broken lines and -ve labels to show unconditional links.
3) Draw solid line between conjugate nodes.
4) Draw broken line between bivalue nodes sharing same candidate.
5) Draw broken line between ends of 2 solid lines with same label.
6) Draw broken line between the end of a solid-line to a bivalue node with the same labels.
7) Identify nice loops. Draw additional broken lines to complete nice loops as required.

where:
A conjugate link is defined as a link between 2 cells with the same candidate which appears exactly 2 times in that unit.
An unconditional link is defined as a link between 2 cells with the same candidate which appears 2 times or more in that unit

According to the definition, an unconditional link is basically a link between any two cells that contain the same candidate digit in a unit. The term 'unconditional' means that it doesn't matter how many times the same candidate digit appears in that unit. From step 7, it is also clear that additional unconditional links may be required to be drawn to complete a nice loop. Following these steps, nothing more than the following diagram on the right can be resulted.

Image

Once this point is reached, there is no need to consider the construction steps apart from step 7 of course.

flip wrote:Does this mean that for case 3 of the unconditional link we cannot apply the turbot fish nice loops 'x-cycle 1' and x-cycle 2' since the conjugate links [r1c9]=6=[r6c9] and [r3c4]=6=[r3c7] are precluded from being treated as unconditional links because the unconditional link [r1c9]-6-[r3c7] is made assuming those two to be conjugate links?

I can see that you are very confused. You need to sort out the difference between the construction steps of links and nice loop propagation rules, then I am sure that everything would fall into place. BTW, x-cycle 1 & 2 are simple colouring nice loops.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: x-cycle nice loops: identification process

Postby flip » Sun Jan 08, 2006 8:59 pm

Jeff wrote:You need to sort out the difference between the construction steps of links and nice loop propagation rules, then I am sure that everything would fall into place.

Jeff, thanks for your kind explanation. I can see now that one must make a clear separation between the links construction step and the application of the nice loop propagation rules.

Also, thanks for the clear definition of the term unconditional link,

One last question please. In step 7 you say 'Identify nice loops. Draw additional broken lines to complete nice loops as required'. Can you elaborate on this please, perhaps with an example? What additional broken lines are implied here, not covered by the link construction steps?
Last edited by flip on Mon Jan 09, 2006 1:55 am, edited 1 time in total.
flip
 
Posts: 17
Joined: 08 January 2006

Re: x-cycle nice loops: identification process

Postby Jeff » Mon Jan 09, 2006 5:22 am

flip wrote:One last question please. In step 7 you say 'Identify nice loops. Draw additional broken lines to complete nice loops as required'. Can you elaborate on this please, perhaps with an example? What additional broken lines are implied here, not covered by the link construction rules (should be construction steps)?

Hi Flip, Here is an x-cycle that requires step 7.

Image

Fig. 1 is the filtered candidate grid on 6s with relevant cells highlighted.
Fig. 2 is the b/b plot for the relevant cells following the construction steps apart from step 7.
Fig. 3 shows that link [r3c4]=6=[r6c4] has been replaced by [r3c4]-6-[r6c4] (in red), and the unconditional links
[r7c8]-6-[r5c8]-6-[r6c9] have been added as per step 7 to form the nice loop.

Nice loop notation:
[r5c8]-6-[r6c9]=6=[r6c4]-6-[r3c4]=6=[r3c7]-6-[r7c7]=6=[r7c8]-6-[r5c8] => r5c8<>6
Jeff
 
Posts: 708
Joined: 01 August 2005

Next

Return to Advanced solving techniques

cron