## Nice loops for advanced level players - b/b plot

Advanced methods and approaches for solving Sudoku puzzles

### Nice loops for advanced level players - b/b plot

The b/b plot, short for bilocation/bivalue plot , is extended from Eppstein's paper where individual bilocation plot and bivalue plot were discussed. Although the operation is quite tedious, it is nevertheless a human executable non-T&E technique for identification of double implication forcing chains.

In this post, you will be shown how to identify double implication forcing chains known as simple nice loops using the b/b plot. In a simple nice loop, each node contains only one cell.

A double implication forcing chain is defined as a chain with 2 implications in which a node implies only the next node downstream. In any network where a node implies more than one node, such network is regarded as a forcing net.

In a bilocation/bivalue plot, 'strong links' and 'links' with 'strong inference' and 'weak inference' between nodes are constructed and labelled for identification of simple nice loops as follows: (refer definitions of 'link', 'strong link', 'strong inference' and 'weak inference' here):

b/b plot construction procedure:

1) Use solid lines and +ve labels to show 'strong links' with both strong and weak inferences.
2) Use broken lines and -ve labels to show 'links' with weak inference only.
3) Draw solid line between bilocation nodes with conjugate relationship in a unit.
4) Draw broken line between bivalue nodes sharing same candidate.
5) Draw broken line between ends of 2 solid lines with same labels.
6) Draw broken line from the end of a solid-line to a bivalue node with a candidate matching the label of the solid line.
7) Identify nice loops. Draw additional broken lines (refer 8 & 9 below) to complete nice loops as required.
8) Additional broken line can be from any node to the end of a solid line with label matching a candidate of the node.
9) Additional broken line can be from any node to a bivalue node sharing the same candidate.

The plot (without additional broken lines) should look something like this:

Via the bilocation/bivalue plot, simple nice loops can be identified with each loop representing a double implication forcing chain. These nice loops must follow a set of nice loop propagation rules which enables valid forcing chain inferences to take place as follows:

Nice loop propagation rules:

1) A strong link, can be interpreted as a strong inference or a weak inference.

2) To propagate from a link with strong inference to a link with strong inference (ie. solid/solid), the labels must be different.

3) To propagate from a link with weak inference to a link with weak inference (ie. solid/solid, solid/broken, broken/solid or broken/broken) the labels must be different and the node between links must be bivalue. (typical xy-chain propagation)

4) To propagate from a link with strong inference to a link with weak inference (ie. solid/solid or solid/broken) or vice versa, the labels must be same but opposite in signs. (typical x-cycle propagation)

There are 2 types of nice loops, namely continuous type and discontinuous type. If the set of propagation rules is obeyed continuously within a nice loop in a cyclic manner, the loop is said to be a "continuous nice loop", otherwise "discontinuous".

Each continuous nice loop would allow candidates to be eliminated as follows:
THEOREM 1:
If a cell between 2 links with strong inference belongs to a continuous simple nice loop, then the cell can only be filled with one of the 2 digits that label the links; thus other candidates in the cell can be eliminated.

For example, due to the continuous nice loop below, a 3 in r4c6, a 3 in r8c6 and an 8 in r8c1 can be eliminated.

Nice loop notation (see explanation for nice loop notation below):
-[r4c2]=1=[r4c6]=6=[r8c6]=2=[r8c1]=1=[r6c1]-1-[r4c2]=
implies r4c6<>3, a r8c6<>3, and r8c1<>8

THEOREM 2:
If a link with weak inference straddling 2 cells belongs to a continuous simple nice loop ,then the digit labeling it must be placed at one of the 2 cells; thus this digit can be eliminated from any other cells that lie in the same row, column or box housing the link.

For example, due to the continuous nice loop below, 7 in r4c1, 24 in r9c7 and 7 in r4c9 can be eliminated.

Nice loop notation (see explanation for nice loop notation below):
-[r1c7]-9-[r3c9]-1-[r3c3]-3-[r4c3]-7-[r4c5]-4-[r6c5]-7-[r6c7]-4-[r7c7]-2-[r1c7]-
implies r4c1<>7, r9c7<>2, r9c7<>4, and r4c9<>7

A discontinuous nice loop has link inferences that obey the set of propagation rules except at one of the nodes known as a discontinuity. This allows a candidate to be fixed or eliminated in the node as follows:

THEOREM 3:
At the discontinuity of a simple nice loop where 2 links with strong inference of same labels meet, the digit that labels the links can be fixed in the cell between the links.

THEOREM 4:
At the discontinuity of a simple nice loop where 2 links with weak inference of same labels meet, the digit that labels the links can be eliminated from the cell between the links.

THEOREM 5:
At the discontinuity of a simple nice loop where a link with strong inference and a link with weak inference meet, the digit that labels the broken line can be eliminated from the cell between the links.

For example, due to the discontinuous nice loop below, 8 in r9c6 can be fixed as per Theorem 3:

Nice loop notation (see explanation for nice loop notation below):
[r9c6]=8=[r9c7]=5=[r8c8]-5-[r3c8]=5=[r3c5]=8=[r3c2]-8-[r1c3]=8=[r8c3]-8-[r8c6]=8=[r9c6] => r9c6=8

For example, due to the discontinuous nice loop below, 1 in r7c2 can be eliminated as per Theorem 4:

Nice loop notation (see explanation for nice loop notation below):
[r7c2]-1-[r2c2]=1=[r2c7]=2=[r3c9]-2-[r3c6]-4-[r7c6]-1-[r7c2] => r7c2<>1

For example, due to the discontinuous nice loop below, 8 in r3c6 can be eliminated as per Theorem 5:

Nice loop notation (see explanation for nice loop notation below):
[r3c6]=6=[r3c5]=5=[r3c8]-5-[r8c8]=5=[r9c7]=8=[r9c6]-8-[r3c6] => r3c6<>8

Double implication chains identified via the b/b plot can be expressed in a nice loop notation format where the inferences and deduction(s) can be easily observed. In the notation, '=x=' represents a link with strong inference and '-x-' represents a link with weak inference, with label x:

Nice loop notation for continuous nice loops:

1) Strong Inference Loop (loop with pure strong inferences, eg. strong ring):
=[Node 1]=a=[Node 2]=b=[Node 3]=c=[Node 4]......[Node N]=n=[Node 1]=

2) Weak Inference Loop (loop with pure weak inferences, also known as xy-chain):
-[Node 1]-a-[Node 2]-b-[Node 3]-c-[Node 4]......[Node N]-n-[Node 1]-

3) Alternating Inference Loop (loop with alternate strong and weak inferences, also known as x-cycle, eg. x-wing):
=[Node 1]-x-[Node 2]=x=[Node 3]-x-[Node 4]=x=[............]-x-[Node N]=x=[Node 1]-

4) Mixed Inference Loop (loop consists of mixed inferences):
=[Node 1]-a-[Node 2]-b-[Node 3]=c=[Node 4]=d=[Node 5]......[Node N]=n=[Node 1]-

where: all inferences (including links a and n) obey the nice loop propagation rules and candidates are to be eliminated in accordance with Theorem 1 and 2.

Nice loop notation for discontinuous nice loops:

1) Strong Inference Loop (loop with pure strong inferences, eg. strong wing):
[Node 1]=a=[Node 2]=b=[Node 3]=c=[Node 4]......[Node N]=n=[Node 1] => Node 1=a, where a=n

2) Weak Inference Loop (loop with pure weak inferences, also known as xy-chain):
[Node 1]-a-[Node 2]-b-[Node 3]-c-[Node 4]......[Node N]-n-[Node 1] => Node 1<>a, where a=n

3) Alternating Inference Loop (loop with alternate strong and weak inferences, also known as x-cycle):
[Node 1]-x-[Node 2]=x=[Node 3]-x-[Node 4]=x=[Node 5]-x-[............]=x=[Node N]-x-[Node 1] => Node 1<>x
[Node 1]=x=[Node 2]-x-[Node 3]=x=[Node 4]-x-[Node 5]=x=[............]-x-[Node N]=x=[Node 1] => Node 1=x

4) Mixed Inference Loop (loop consists of mixed inferences):
[Node 1]=a=[Node 2]-b-[Node 3]=c=[Node 4]=d=[Node 5]......[Node N]=n=[Node 1] => Node 1=a, where a=n
[Node 1]-a-[Node 2]-b-[Node 3]=c=[Node 4]=d=[Node 5]......[Node N]-n-[Node 1] => Node 1<>a, where a=n
[Node 1]=a=[Node 2]-b-[Node 3]=c=[Node 4]=d=[Node 5]......[Node N]-n-[Node 1] => Node 1<>a, where a<>n

As an exercise, you may like to try out this technique on the following grid. Initially, 5 simple nice loops can be identified before this grid has to be updated. It would finally require between 9 to15 nice loops to solve this grid.
Last edited by Jeff on Thu Mar 23, 2006 12:12 pm, edited 23 times in total.
Jeff

Posts: 708
Joined: 01 August 2005

I've only read through about half of this so far but I'm very impressed.
Well done.
angusj

Posts: 306
Joined: 12 June 2005

### Double implication chain applications

Your understanding of the bilocation/bivalue plot will extend your knowledge for other existing techniques that can be described by the nice loop principle. It is important that you write out the implications while going through the examples in order to appreciate the rules of nice loop propagation.

Listed below are some current techniques that can be shown as nice loops:

Continuous bilocation chain:
• Hidden pair
• Hidden triple of (ab*,bc*,ca*) format
Continuous bivalue chain:
• non-repetitive xy-chain
• Naked pair
• Naked triple of (ab,bc,ca) format
Continuous combination chain:
• x-wing
• Swordfish of 222 formation
Discontinuous bilocation chain:
• None
Discontinuous bivalue chain:
• xy-wing, xy-chain
Discontinuous combination chain:
• Turbot fish, Turbot chain
• Solve by colours (Simple colouring)
• Some special cases of Almost locked set
Please note that xyz-wing, xyz-chain and their derivatives are forcing nets or poly-implication chains.
Last edited by Jeff on Sat Dec 03, 2005 9:32 am, edited 1 time in total.
Jeff

Posts: 708
Joined: 01 August 2005

There seems to be some resistance to using these pathway techniques, people generally favouring more structured tabling approaches. That might be because of a perception that the plots such as those shown by Jeff further up this topic are just too complicated and spaghetti-like to make sense of.

However I always preferred geometry to algebra at school and I stick with the graphical approach modified to de-spaghettify the diagrams. You need two extra pieces of paper, one to mark up the bivalue and bilocation arrows, and another one to redraw them in the same way as one draws mind-maps.

Click HERE for the "arrow" diagram for this puzzle . The Simple Sudoku programme is perfect for identifying the bilocation and the bivalue cells. As to my cell labelling scheme, others will no doubt develop their own, but I try to anticipate a little and give new letters to cells that are "masters" and give a prime or double prime to cells that are mere hangers on. I use double letters for cells that are bivalue - generally puzzles work out with weak links from bivalue cells that are NOT already bilocation but I don't think that there is a rule that says this.

The next stage is the fun one and involves redrawing the arrow diagram in line or mental map form. Click HERE for the one coresponding to this puzzle.

I tend to search first among the strong links for pathways that form repetitive and non-repetitive links and conflicting ends before adding the weak links from the bivalue cells. Use Jeff's rules - strong to strong and weak to weak, change values, weak to strong and vice versa, change signs.

The loop that I found for this puzzle was of the repetitive variety: B,A,E,O,BB,Q,G and back to B. This forces a "1" into B (ie r1c9).

BTW - I'm still stuck in the mould of Eppstein's original paper. See Jeff's first posting above to see how he has unified these different patterns into a single structure.
Last edited by Max Beran on Fri Dec 02, 2005 12:59 pm, edited 1 time in total.
Max Beran

Posts: 57
Joined: 17 August 2005

Hi Max

I can see that you are enjoying this so much. I like your drawings as they don't have to rely on the computer at all. It means that you can work on these drawings and find those nice loops anywhere you want and anytime you want.

BTW, have you or anyone managed to complete the exercise in the first post using basic deductions and bilocation/bivalue plot alone?
Jeff

Posts: 708
Joined: 01 August 2005

I don't see an exercise. I see a frog that invites me to visit ImageShack.us. Please repost the puzzle in ASCII text.

Thanks.
rubylips

Posts: 149
Joined: 01 November 2005

Jeff,

I have solved the exercise you posted, but I did not found all the nice loops you said were necessary. I have used only about a few nice loops and one forcing net (in an empty cell contradiction argument). Could you list your chains?

Regards, Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Sorry for that slightly offbeat post. It's true - Firefox does display a frog instead of a puzzle. Here's an ASCII version for others out there who might be overrun with amphibian images at the moment:
Code: Select all
` . 3 . | . . . | . . .  . 7 8 | 2 . 6 | 3 1 .  6 9 . | . . . | . 5 2 -------+-------+------  . 5 7 | 9 . 1 | 4 . .  . 6 . | . . . | . 7 .  . . 3 | 6 7 8 | 5 2 . -------+-------+------  3 8 . | 5 . . | . 4 7  7 2 5 | 1 4 3 | 6 9 8  . . . | . . . | . 3 5 `

My solver can't crack it without use of tables - I can't wait to see your chains.
rubylips

Posts: 149
Joined: 01 November 2005

rubylips wrote:Firefox does display a frog instead of a puzzle.
r.e.s.

Posts: 337
Joined: 31 August 2005

In box 6 r5c9 must be a "9" according to my understanding of the BUG rule.

Proceeding on from there, I got to contradictions. I checked it out with Simple Sudoku and sure enough it too says it's insoluble when that 9 is forced.
Max Beran

Posts: 57
Joined: 17 August 2005

Here is my solution using only nice loops.

We can begin by noting that r3c4 must be 3:

Chain 1: [r3c4]=3=[r3c5]–3–[r4c5]–2–[r4c1]–8–[r4c8]–6–[r1c8]
-8–[r3c7]–7–[r3c6]–4–[r5c6]=4=[r5c4]=3=[r3c4] => r3c4 = 3.

If this chain were not possible, we could still prove that r3c4 <> 4, 7, due to the following nice loops:

Chain A: [r3c4]=3=[r5c4]=4=[r5c6]–4–[r3c6]–7–[r3c4] => r3c4 <> 7.

Chain B: [r3c4]=3=[r5c4]–3–[r4c5]=3=[r4c9]=6=[r4c8]=8=[r1c8]–8–
[r3c7]–7–[r3c6]–4–[r3c4] => r3c4 <> 4.

Next, we can show that r1c5 <> 8, 9:

Chain 2: [r1c5]=1=[r3c5]–1–[r3c3]–4–[r3c6]–7–[r1c4]–8–[r1c5]
=> r1c5 <> 8.

Chain 3: [r1c5]=1=[r3c5]–1–[r3c3]–4–[r2c1]–5–[r2c5]–9–[r1c5]
=> r1c5 <> 9.

Now, let's prove that r1c6<>7:

Chain 4: [r1c6]=4=[r3c6]-4-[r3c3]-1-[r3c5]-8-[r1c4]-7-[r1c6] =>
r1c6<> 7.

Although not necessary, we can also prove that r19c3 <> 1:

Chain C: [r1c3]=2=[r5c3]–2–[r4c1]–8–[r4c8]=8=[r1c8]–8–[r3c7]–7–
[r3c6]–4–[r3c3]–1–[r1c3] => r1c3 <> 1.

Chain D: [r9c3]=6=[r9c5]=8=[r3c5]–8–[r3c7]–7–[r3c6]–4–[r3c3]–1–
[r9c3] => r9c3 <> 1.

Now, let's see an example of what I have proposed to call a "triple nice loop":

Chain 5: [r1c7]=9=[r5c7]-9-[r5c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]=7=
[r1c7]-8-[r1c8]-6-[r4c8]-8-[r4c1]-2-[r5c3], which implies
r1c7<>8.

Here, r1c7 functions as a "modified" trilocation cell, because it has two strong links and one weak link, and r5c3 is the trivalue cell. A discontinuity arises in this loop in cell r1c7, because it has two strong links with different labels, and a weak link with a label different from the other two. If you follow the logic inside this loop, the conclusion is straightforward.

To solve the puzzle, I needed the following two nice loops:

Chain 6: [r2c5]-5-[r1c5]-1-[r3c5]=1=[r3c3]=4=[r3c6]=7=[r3c7]-7-
[r1c7]=7=[r1c4]=8=[r1c8]=6=[r1c9]=4=[r2c9]-4-[r2c1]
-5-[r2c5] => r2c5<>5.

Chain 7: [r3c6]-4-[r3c3]-1-[r3c5]-8-[r1c4]=8=[r1c8]=6=[r1c9]-6-
[r4c9]-3-[r4c5]=3=[r5c5]=5=[r5c6]-5-[r1c6]-4-[r3c6] =>
r3c6<>4.

Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Carcul wrote:Now, let's see an example of what I have proposed to call a "triple nice loop":

Chain 5: [r1c7]=9=[r5c7]-9-[r5c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]=7=
[r1c7]-8-[r1c8]-6-[r4c8]-8-[r4c1]-2-[r5c3], which implies
r1c7<>8.

Here, r1c7 functions as a "modified" trilocation cell, because it has two strong links and one weak link, and r5c3 is the trivalue cell. A discontinuity arises in this loop in cell r1c7, because it has two strong links with different labels, and a weak link with a label different from the other two. If you follow the logic inside this loop, the conclusion is straightforward.

I think this is where you were at chain 5:

Code: Select all
`1245 3    124  | 78   15   459  | 789  68   469  45   7    8    | 2    59   6    | 3    1    49   6    9    14   | 3    18   47   | 78   5    2    ---------------+----------------+---------------28   5    7    | 9    23   1    | 4    68   36   1289 6    129  | 4    235  25   | 89   7    139  149  14   3    | 6    7    8    | 5    2    19   ---------------+----------------+---------------3    8    169  | 5    269  29   | 12   4    7    7    2    5    | 1    4    3    | 6    9    8    149  14   1469 | 78   2689 279  | 12   3    5  `

Triple chain requires that all implications must meet the exclusion criteria. There are more than one nice loop in chain 5 and one of them is invalid. ie.

[r1c7]=9=[r5c7]-9-[r5c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]=7=[r1c7] doesn't force anything.

Hint: from here, there is a uniqueness rectangle. Of course, I would be much happier if the uniqueness rule is not needed.
Jeff

Posts: 708
Joined: 01 August 2005

Jeff,

I am sorry but I disagree with you. If you make r1c7 = 8 and follow the three implications of chain 5, you will end up with no candidate for r5c3. So, r1c7<>8.

Regards, Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Carcul, the chain can't eliminate the 1 in r5c3.
Jeff

Posts: 708
Joined: 01 August 2005

Max Beran wrote:In box 6 r5c9 must be a "9" according to my understanding of the BUG rule.

Max, I am afraid it is too early to apply the BUG rule.
Jeff

Posts: 708
Joined: 01 August 2005

Next