Strong Nice Loop: a new concept

Advanced methods and approaches for solving Sudoku puzzles

Strong Nice Loop: a new concept

Postby Carcul » Fri Dec 02, 2005 12:50 am

While I was looking into the second step in Bennys’s solution of the puzzle posted by MikeF, I was wondering if that conclusion could be expressed by some sort of nice loop, necessarily different from the classic nice loops that are already known. It turns out that it is indeed possible to do so, but for that we have to extend one of the concepts involved in nice loop construction: the one of strong link. Allow me to start my reasoning by making the following definitions:

Domain: a row, a column, or a box.
D1: a domain in which all cells containing candidate “x” belong to only two other domains, D2 and D3.
Cells “a”: cells containing candidate “x” and lying in the interception of domains D1 and D2.
Cells “b”: cells containing candidate “x” and lying in the interception of domains D1 and D3.
Na, Nb: the number of cells “a” or “b”.

Usually, in a nice loop, we draw a strong link between the only two cells in a domain where a candidate “x” can be placed. For example, [r1c1]=8=[r1c7], and the logic of this link is: if 8 is in r1c1, then it cannot be in r1c7, and if 8 is not in r1c1, then it must be in r1c7 (and vice-versa for r1c7). But we can extend this concept by making use of a special property of boxes: they can have more than one cell in their interception with a column or a row. Consider Grid 1 as an example:

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

        Grid 1


Box 5 has more than two possible cells for candidate 5. However, we can consider that these four cells are in only two possible locations inside box 5: columns 4 and 6. So, we can say that, if 5 is not in one of the cells r4c4/r5c4, then it must be in one of the cells r5c6/r6c6; and if 5 is in one of the cells r4c4/r5c4, then it cannot be in cells r5c6/r6c6. With this idea in mind, we are able to make the following generalization of the rule for draw a strong link:

Code: Select all
If a candidate ‘x’ is distributed among the cells of a domain D1 in such a way that these cells belong to only two other domains, D2 (cells ‘a’) and D3 (cells ‘b’), then we can draw a strong link between cells ‘a’ and cells ‘b’, with label ‘x’.


We can call this type of strong link a generalized strong link. It is easy to see that Na + Nb can have the maximum value of six. Grid 2 provides some examples, where “a” and “b” are cells containing candidate “x”:

Code: Select all
 a . . | . a a | . b .
 a . b | . . . | a . a
 . . b | b b b | . b .   
-------+-------+------
 . . . | a . b | . . .
 . . . | a . b | . . .
 . . . | a . b | . . .
-------+-------+------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .

        Grid 2


For this type of strong link, I propose a notation that is similar to the already known notation: the only difference is in putting the “a” or “b” cells between square brackets and separated by a vertical line. For example, for box 2 we can write: [r1c5|r1c6]=x=[r3c4|r3c5|r3c6].
Now, for this type of strong link to be inserted in a nice loop, it must be propagated but in a restricted way: we can only propagate from the set of cells “a” (or “b”) to another cell with a weak link having the same label “x”, and that cell can be of only one of two types: a bivalue cell containing candidate “x”, or a bi- or polivalue cell containing candidate “x” and having a strong link with same label “x”. Furthermore, that cell must be in the same domain common to all cells “a” (or “b”).
We can see that, besides its probable scarcity, the generalized strong link as I have defined so far cannot be used to make eliminations in cells “a” or “b”. However, this can be possible if Na (or Nb) = 1. Please consider the examples in grid 3 (“ab” denotes a cell that can function as an “a” cell or as a “b” cell):

Code: Select all
 ab. b | a . . | . a .
 . . ab| . . b | . . .
 . . . | . . b | b . b   
-------+-------+------
 a . b | . . . | . a .
 . . b | . . . | . . .
 . . b | . . . | . . .
-------+-------+------
 . . . | . . . | . b .
 . a . | . b b | . b .
 . . . | . . . | . b .

        Grid 3


Boxes 1, 2, 3, and 4 show some examples with D1 = box and D2, D3 = rows and/or columns. Boxes 6 and 9, and 7 and 8 exemplify the case for D1 = column/row, and D2, D3 = boxes. In each case, we can draw a generalized strong link between cell “a” and the set of cells “b”.
Now, please note that this type of generalized strong link can be more useful because, although the set of cells “b” can only be propagated as described above, cell “a” can be propagated as in classic nice loops: with a strong or weak link, with the same or a different label, which can be used to remove a candidate from this cell.
Now, allow me to make the following definition:

Strong Nice Loop: a nice loop that includes one or more generalized strong links.

To exemplify all this, let’s return to the puzzle I have mentioned in the beginning of this thread:

Code: Select all
 579  5789 12   | 3    4    12   | 589  59   6     
 459  6    249  | 7    8    29   | 1    3459 3459 
 34   89   1349 | 19   6    5    | 489  7    2     
----------------+----------------+----------------
 79   4    8    | 5    2    79   | 3    6    1     
 6    1    5    | 89   3    489  | 7    2    49   
 2    3    79   | 6    1    479  | 459  8    459   
----------------+----------------+----------------
 1    2   *39*  | 4    7   *38   | 6    359  3589 
 3457 57   6    | 18   9   *138  | 2   *34   3478 
 8   *79  *3479 | 2    5    6    |*49   1    3479 


With the definitions that I have made above, I have noted that Bennys’s observation can be described by the following strong nice loop:

[r7c3]=9=[r9c2|r9c3]-9-[r9c7]-4-[r8c8]-3-[r8c6]=3=[r7c6]-3-[r7c3] => r7c3<>3.

(in the grid, the cells marked with “*” are the ones used in the loop, and the cell marked “**” is where the discontinuity arises). Let’s confirm the logic inside this loop: if r7c3 is not 9 then it is 3; then one of the cells r9c2/r9c3 is 9; which means that r9c7 is 4, and r8c8 is 3, and r8c6 cannot be 3, so r7c6 is 3, and this is an impossible situation because we have already a 3 in row 7, in cell r7c3: so, r7c3 cannot be 3.

Another example can be seen in the following puzzle, which was posted in this forum in a thread entitled “Wondering if there is a solving technique for this?” (November 22).

Code: Select all
 . . 1 | . 8 . | 6 . 4
 . 3 7 | 6 . . | . . .
 5 . . | . . . | . . .   
-------+-------+------
 . . . | . . 5 | . . .
 . . 6 | . 1 . | 8 . .
 . . . | 4 . . | . . .
-------+-------+------
 . . . | . . . | . . 3
 . . . | . . 7 | 5 2 .
 8 . 2 | . 9 . | 7 . .


After some basic steps, we can remove a 4 from r7c2 with a Turbot Fish, a 7 from r5c2 with a nice loop, and a 2 from r4c5 and r6c5 with two forcing nets, and we get:

Code: Select all
 29    29     1    | 57   8    3      | 6     57     4     
 4     3      7    | 6    25   129    | 129   1589   12589 
 5     6      8    | 1279 247  1249   | 1239  1379   1279   
-------------------+------------------+--------------------
 12379 124789 349  | 2789*367  5      | 12349 134679 12679     
 2379  249    6    | 279  1    29     | 8     34579  2579   
 12379 12789  5    | 4   *367  *2689  | 1239  13679  12679   
-------------------+------------------+--------------------
 1679  179    49   | 1258 2456 *12468*| 149   14689  3 
 1369  149    349  | 18  *46   7      | 5     2      1689 
 8     5      2    | 3    9    146    | 7     146    16


From here, we can make another elimination using the following strong nice loop:

[r7c6]=8=[r6c6]=6=[r4c5|r6c5]-6-[r8c5]-4-[r7c6]

which implies r7c6<>4.

Let’s look at a final example. The following puzzle was also posted by Bennys, in his recent thread entitled “Not almost locked sets”:

Code: Select all
 12   7    126  | 5    126  9    | 3    4    8     
 3    5    9    | 8    126  4    | 126  26   7     
 4    8    126  | 3    1267 67   | 126  5    9     
----------------+----------------+--------------
 169  1349 7    | 12   46   368  | 5   *289  14   
 5    2    14   | 19   49   78   |*78   3    6     
 169  1349 8    |*127  4567 3567 |*27  *279  14   
----------------+----------------+--------------
 1289 149  124  | 6   *579 *57   | 478 *78   3     
 89   49   5    | *79* 3    1    | 4678 678  2     
 7    6    3    | 4    8    2    | 9    1    5 


Bennys made a clever observation (which concludes that r6c4<>7) that allows the grid to be easily solved from here. However, I have noted that we can arrive at the same conclusion with the following strong nice loop:

[r8c4]=7=[r7c5|r7c6]-7-[r7c8]-8-[r4c8]=8=[r5c7]=7=[r6c7|r6c8]-7-[r6c4]=7=[r8c4]

(or [r8c4]=7=[r8c7|r8c8]-7-[r7c8]…), which implies r8c4 = 7.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby rubylips » Fri Dec 02, 2005 1:03 am

I think this is what I refer to as an extended link later in that thread (how to spot this pattern?) and denote with the symbol '='.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Carcul » Fri Dec 02, 2005 1:28 am

Rubylips,

I have read now your reply to that thread with more attention and, in fact, your extended link is equivalent to my generalized strong link. So, I am sorry if I have named differently a concept that you have discovered and named first. Nevertheless, do you agree with the designation "strong nice loop"?

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

Re: Strong Nice Loop: a new concept

Postby Jeff » Fri Dec 02, 2005 7:56 am

Carcul wrote:Strong Nice Loop: a nice loop that includes one or more generalized strong links.

This is an excellent idea which pushes the application of the bilocation/bivalue plot technique to a new limit. Another further application of the technique would be triple implication chains with trivalue and trilocation cells.

Thank you for the description which is very easy to understand. Perhaps my initial confusion was with the word 'strong', because both 'strong' and 'weak' could mean a number of different things in this forum.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby rubylips » Fri Dec 02, 2005 10:32 pm

Carcul wrote:I have read now your reply to that thread with more attention and, in fact, your extended link is equivalent to my generalized strong link. So, I am sorry if I have named differently a concept that you have discovered and named first.

Please don't apologize as others have used the technique (though perhaps not the name) before me e.g. earlier in the thread (how to spot this pattern) bennys had written R9C7=9 => R7C3=9 while back in September (stuck on this one) Glenn had used the technique when he wrote if r5c5==2 then r4c1==2. I have simply implemented the technique (after Glenn had used it).
Carcul wrote:Nevertheless, do you agree with the designation "strong nice loop"?

I like to distinguish between the concept of a link, which in my world is a single component of a chain, and the chain itself. The algorithm implemented in my solver first builds a list of all the links that exist within a partially-completed grid then attempts to string them together to form a cyclic chain. So, as far as I'm concerned, an extended link is simply a new type of link. Cyclic chain theory, i.e. the rules that dictate whether a given cyclic chain allows a candidate to be eliminated, remains unaltered, so I think it's perhaps a little misleading to talk about a new loop type. However, please feel free to disagree.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Carcul » Fri Dec 02, 2005 11:56 pm

Jeff,

That's a good idea, one that also came to my mind a few weeks ago, but I didn't bother very much with it. When you refer to the concepts of trivalue and trilocation cells, do they correspond to the following definitions?

Trilocation cell: a cell from which we can draw three strong links.
Trivalue cell: a cell containing only three candidates.

If they do, then allow me to propose the following definition:

Triple Nice Loop: a nice loop that includes a trilocation cell and/or a trivalue cell.

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

Postby Jeff » Sat Dec 03, 2005 7:43 am

Carcul, I don't want to disturb the line of thinking under this thread. So, I would just briefly answer your questions here and start a new thread to discuss how to make use of the bilocation/bivalue plot to identify triple implication chains.
Carcul wrote:Trilocation cell: a cell from which we can draw three strong links.
No
Carcul wrote:Trivalue cell: a cell containing only three candidates
Yes
Carcul wrote:Triple Nice Loop: a nice loop that includes a trilocation cell and/or a trivalue cell.
A triple chain has more than one nice loop.
Jeff
 
Posts: 708
Joined: 01 August 2005

Another example

Postby Carcul » Sun Dec 04, 2005 4:12 pm

The puzzle in grid 1 is one classified as “Diabolical” that I took from a book published in Portugal (author: Michael Mepham), which contains puzzles originally printed in “The Daily Telegraph”.

Code: Select all
 8 . 3 | 2 . 4 | 1 . .
 . . . | . 7 3 | . . .
 4 6 2 | . . . | . . .   
-------+-------+------
 . . 5 | . . . | 4 . 3
 . 4 . | . . . | . 5 .
 1 . 7 | . . . | 9 . .
-------+-------+------
 . . . | . . . | 6 7 9
 . . . | 9 5 . | . . .
 . . 9 | 1 . 7 | 5 . 8

         Grid 1


After some basic steps we get:

Code: Select all
 8   7   3  | 2     69     4    | 1  69   5
 9   5   1  | 68    7      3    | 28 246  246
 4   6   2  | 58    189    1589 | 38 39   7   
------------+-------------------+-------------
 26  9   5  | 7     1268   1268 | 4  1268 3
 236 4   68 | 368   123689 12689| 7  5    126
 1   238 7  | 34568 23468  2568 | 9  268  26
------------+-------------------+-------------
 5   1   48 | 348   2348   28   | 6  7    9
 7   238 468| 9     5      68   | 23 1234 124
 236 23  9  | 1     46     7    | 5  234  8

                    Grid 2


I have tried to solve this puzzle with Angus simple sudoku solver. After the solver have reached the state of the puzzle in grid 2, he goes on by eliminating three “6” with colouring and multi-colouring, and then gets stuck.
However, the only thing that is needed to solve grid 2 is the following strong nice loop:

[r9c5]=4=[r7c4|r7c5]-4-[r7c3]-8-[r5c3]-6-[r8c3]=6=[r8c6]-6-[r9c5]

which implies r9c5<>6. After this deduction, a naked pair emerges in row 9 and from there we have only singles.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby rubylips » Sun Dec 04, 2005 8:56 pm

Just to clarify, simple chains (or colouring) remove the following 6s:
Code: Select all
Consider the chain r2c4-6-r1c5~6~r9c5-6-r8c6-6-r8c3-6-r5c3~6~r5c4.
When the cell r5c4 contains the value 6, so does the cell r2c4 - a contradiction.
Therefore, the cell r5c4 cannot contain the value 6.
- The move r5c4:=6 has been eliminated.
Consider the chain r6c4-6-r2c4-6-r1c5-6-r1c8~6~r6c8.
When the cell r6c8 contains the value 6, so does the cell r6c4 - a contradiction.
Therefore, the cell r6c8 cannot contain the value 6.
- The move r6c8:=6 has been eliminated.
Consider the chain r5c5~6~r5c3-6-r8c3-6-r8c6-6-r9c5.
When the cell r5c5 contains the value 6, so does the cell r9c5 - a contradiction.
Therefore, the cell r5c5 cannot contain the value 6.
- The move r5c5:=6 has been eliminated.


In fact, it's not necessary to use a chain to solve the puzzle from here:
Code: Select all
Consider the cell r8c3.
When it contains the value 6, the value 8 in Row 8 must occupy the cell r8c6.
When it contains the value 4, the value 8 in Box 7 must occupy the cell r7c3.
Whichever value it contains, the cells r8c1 and r8c2 cannot contain the value 8.
- The move r8c2:=8 has been eliminated.
The cell r6c2 is the only candidate for the value 8 in Column 2.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby ronk » Mon Dec 05, 2005 1:54 am

rubylips wrote:
Code: Select all
Consider the chain r2c4-6-r1c5~6~r9c5-6-r8c6-6-r8c3-6-r5c3~6~r5c4.
When the cell r5c4 contains the value 6, so does the cell r2c4 - a contradiction.
Therefore, the cell r5c4 cannot contain the value 6.
- The move r5c4:=6 has been eliminated.
Consider the chain r6c4-6-r2c4-6-r1c5-6-r1c8~6~r6c8.
When the cell r6c8 contains the value 6, so does the cell r6c4 - a contradiction.
Therefore, the cell r6c8 cannot contain the value 6.
- The move r6c8:=6 has been eliminated.

So some equations are meant to be read right to left?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Another example

Postby Jeff » Mon Dec 05, 2005 4:36 am

Carcul wrote:
Code: Select all
 8   7   3  | 2     69     4    | 1  69   5
 9   5   1  | 68    7      3    | 28 246  246
 4   6   2  | 58    189    1589 | 38 39   7   
------------+-------------------+-------------
 26  9   5  | 7     1268   1268 | 4  1268 3
 236 4   68 | 368   123689 12689| 7  5    126
 1   238 7  | 34568 23468  2568 | 9  268  26
------------+-------------------+-------------
 5   1   48 | 348   2348   28   | 6  7    9
 7   238 468| 9     5      68   | 23 1234 124
 236 23  9  | 1     46     7    | 5  234  8

strong nice loop:
[r9c5]=4=[r7c4|r7c5]-4-[r7c3]-8-[r5c3]-6-[r8c3]=6=[r8c6]-6-[r9c5]
which implies r9c5<>6. After this deduction, a naked pair emerges in row 9 and from there we have only singles.

This is equivalent to a triple implication chain where the vertices of the trilocation triangle are r7c4, r7c5 and r9c6

Chain notation:
[r9c5]=4=[r7c4]-4-[r7c3]-8-[r5c3]-6-[r8c3]=6=[r8c6]-6-[r9c5]
[r9c5]=4=[r7c5]-4-[r7c3]-8-[r5c3]-6-[r8c3]=6=[r8c6]-6-[r9c5]
[r9c5]-6-[r8c6]=6=[r8c3]-6-[r5c3]-8-[r7c3]-4-[r7c4]=4=[r7c5]-4-[r7c3]-8-[r5c3]-6-[r8c3]=6=[r8c6]-6-[r9c5]
All imply r9c5<>6

Normally, identification of this chain is not easy and your grouped nice loop has made this deduction so easy to spot with simple notation too.:D Excuse me for avoiding the term 'strong'.
Last edited by Jeff on Thu Dec 08, 2005 12:02 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby rubylips » Mon Dec 05, 2005 11:39 am

ronk wrote:So some equations are meant to be read right to left?

That's right. The first end-point listed always preceds (i.e. belongs to an earlier row or, when they are on the same row, an earlier column) the second end-point. I agree that things would be more helpful if I wrote the chain in an order consistent with the logic.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby ronk » Mon Dec 05, 2005 12:23 pm

rubylips wrote:
ronk wrote:So some equations are meant to be read right to left?

That's right. The first end-point listed always preceds (i.e. belongs to an earlier row or, when they are on the same row, an earlier column) the second end-point. -- (emphasis added)

If it were actually "always" that way, it wouldn't be quite so maddening. In that same post you had an equation which read the more normal left-to-right ...
Code: Select all
Consider the chain r2c4-6-r1c5~6~r9c5-6-r8c6-6-r8c3-6-r5c3~6~r5c4.
When the cell r5c4 contains the value 6, so does the cell r2c4 - a contradiction.
..............
Consider the chain r5c5~6~r5c3-6-r8c3-6-r8c6-6-r9c5.
When the cell r5c5 contains the value 6, so does the cell r9c5 - a contradiction.

The first eq'n right-to-left, and the second left-to-right.
I agree that things would be more helpful if I wrote the chain in an order consistent with the logic.

It's within your power to "be more helpful".
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA


Return to Advanced solving techniques