Common Cells in Basic and Grouped Nice Loops

Advanced methods and approaches for solving Sudoku puzzles

Common Cells in Basic and Grouped Nice Loops

Postby Mike Barker » Fri Nov 24, 2006 7:59 pm

When I first coded up nice loops and grouped nice loops, I would get invalid eliminations if one cell was common to multiple nodes in the loop, so at the time, I simply did not allow common cells. This is overly restrictive. In the case a strong link is being added to a loop, a set of sufficient conditions for a cell of the strong loop to share a common cell with an existing node of the loop (see here) are:
    1) the starting node of one stong link and the ending node of a second strong link can share a cell if the two nodes have different labels
    2) the starting (or ending) nodes of two strong links can share a cell if the two nodes have the same label (this may not be very useful since the loop created at the common node is not required for the nice loop)
    3) this can be expanded to grouped strong link nodes with possibly multiple overlaps as long as the first two rules are followed at the common nodes. Note this applies only to overlapping of non-contiguous nodes in a nice loop, not direct links which require the node be a single cell.
It turns out it is also possible to define sufficient conditions for an ALS to share cells with other nodes in the loop. In this case cells which do not contain link label digits can overlap without restriction. In addition:
    4) two ALS can share a common cell if the link labels coming into or exiting the ALS have the same label
    5) an ALS and the starting node of a strong link or a grouped strong link can share a cell if the link label into the strong link and the link label into the ALS are the same
    6) an ALS and the ending node of a strong link or a grouped strong link can share a cell if the link label of the strong link and the link label into the ALS are different
Rule #4 is especially interesting since it says that two ALS cannot share a common cell if they are adjacent nodes in an ALS which is the issue which was disscussed in the first set of posts. Based on an observation of Myth, here and following posts, it is also clear that
    7) the start and end nodes of a discontinuous nice loop can always share cells if at least one is a strong link
    8) the start and end nodes of a discontinuous nice loop can share cells if both are ALS and the loop contains at least 3 nodes or the common cell(s) do not contain the link label.
To demonstrate the idea here are a few examples. The first is an example of a Rule 1 common cell grouped nice loop. The end of the strong link, r8c4=9=r8c1, shares r8c1 with the start of a subsequent grouped strong link, r78c1=4=r8c2. Because the link labels are different the common cell can exist in both strong links.
Code: Select all
Common 3-element Grouped Nice Loop: r8c4=9=r8c1-9-r5c1-4-r78c1=4=r8c2~4~r8c4 => r8c4<>4
+-------------------+--------------------+-----------------+
|     2  157    37  |   357     6     4  | 359     8  139  |
|     6   45     8  |     1     9    35  |   7   235  234  |
|  1347    9   347  |     8     2   357  | 345     6  134  |
+-------------------+--------------------+-----------------+
|     8  147  2479  |     6  3457  3579  | 145  2359  234  |
|    49*   3   249  |   245     1     8  |   6   259    7  |
|  1479    6     5  |  2347   347   379  | 134   239    8  |
+-------------------+--------------------+-----------------+
| 3459*@   8     1  |  3459   345     6  |   2     7   39  |
| 3479*@  47*    6  | 379-4*  347     2  |   8     1    5  |
|  3579    2   379  |  3579     8     1  |  39     4    6  |
+-------------------+--------------------+-----------------+

This example demonstrates rule 5 with the start of the strong link, -5-r5c45=5=r6c5, sharing a common cell with the ALS, -5-ALS:r12358c5, with the same value for the link label.
Code: Select all
Common 3-element Grouped Nice Loop: ALS:r59c2-5-r5c45=5=r6c5-5-ALS:r12358c5~1~ => r9c5<>1
+-----------------+---------------------+-----------------+
|   9   368    5  |   26    137*$  137  |   16   28    4  |
|   1    36    2  |  469    349*$    8  |    7    5   69  |
|   7    68    4  |  269     19*$    5  |    3   28  169  |
+-----------------+---------------------+-----------------+
|  46   245   79  |    1       8  2467  |  459  479    3  |
| 368    45* 379  | 459*@ 4579*@$  467  |  489    1    2  |
|  48  1245  179  |    3    2459*   24  | 4589    6   78  |
+-----------------+---------------------+-----------------+
|  34     7   13  |    8       6   124  | 1249   49    5  |
|   2     9    6  |   45   1345*$  134  |  148   47   78  |
|   5    14*   8  |    7    24-1     9  | 1246    3   16  |
+-----------------+---------------------+-----------------+

The following rule 5 example also demonstrates common cells at the start (ALS:r1c128) and end (ALS:r12689c1) of the nice loop. Here the ALS (-4-ALS:r12689c1) overlaps the start of the strong link (-4-r6c12) with the same label on the input to both.
Code: Select all
Common 4-element Grouped Nice Loop: ALS:r1c128-3-ALS:r16c6-4-r6c12=4=r5c1-4-ALS:r12689c1~5~ => r7c1<>5
+-----------------------+---------------+---------------+
|    15*%     14*    8  | 7    56   36@ |   2  34*   9  |
|   3479%    479   379  | 8    45    2  |   1   6   35  |
|      6       2    35  | 9     1   34  |   7   8   45  |
+-----------------------+---------------+---------------+
|      8       5   679  | 3  4679    1  |  46   2  467  |
|    247*      3   267  | 5   467    8  |   9   1  467  |
|  1479$%  14679$ 1679  | 2  4679   46@ |   3   5    8  |
+-----------------------+---------------+---------------+
|   27-5      78   257  | 6     3   79  | 458  49    1  |
|   1357%    167  1367  | 4     8   79  |  56  39    2  |
|     39%    689     4  | 1     2    5  |  68   7   36  |
+-----------------------+---------------+---------------+

In the next example the ending node of the stong link, r6c7=5=r789c7, and the ALS, -1-r8c157, share a common cell, r8c7, with different labels (rule 6):
Code: Select all
Common 4-element Grouped Nice Loop: ALS:r1246c4-5-r6c7=5=r789c7-5-ALS:r79c8-1-ALS:r8c157~3~ => r8c4<>3
+-----------------+-------------------+---------------------+
|    1    35  34  |  3469*  29  2346  |      7     8   259  |
|  345     7   8  |   349*   1   234  |      6    25   259  |
|    6     2   9  |     7    5     8  |      3     4     1  |
+-----------------+-------------------+---------------------+
| 3489  3689   5  |  3469*  29  2346  |    148   136     7  |
|    7    36   1  |     8   34  3456  |      2     9   456  |
|    2  3689  34  | 34569*   7     1  |    458*  356  4568  |
+-----------------+-------------------+---------------------+
| 3589  3589   2  |  1345    6   347  |  14589@  157$   48  |
|  358%    4   7  |  15-3   38%    9  |   158@%   26    26  |
|  589     1   6  |     2   48   457  |   4589@   57$    3  |
+-----------------+-------------------+---------------------+

The next example is also rule 6 (-8-r2c78=8=r2c3 and -1-ALS:r2c238), but notice that since r2c8 doesn't contain a "1" it is possible for the start of the strong link and the ALS to have a common cell even though the labels are not the same.
Code: Select all
Common 4-element Grouped Nice Loop: ALS:r1389c7-8-r2c78=8=r2c3-8-ALS:r3c13|r1c3-1-ALS:r2c238~9~ => r2c7<>9
+----------------------+-------------------+---------------------+
|     4     5    1268$ |  78    178     9  |    128*   267    3  |
|     3   179%  1789@% |   2      6     5  |  148-9@  789@% 149  |
|  1268$  179    1268$ |  47  13478    34  |   1289*  2679    5  |
+----------------------+-------------------+---------------------+
|     9    14    1348  |  56   2358  2346  |      7    258  246  |
|    78     2    3478  |   1  34589   346  |   4589    589  469  |
|     5     6      48  | 489   2489     7  |      3      1  249  |
+----------------------+-------------------+---------------------+
|   127     3       5  |  79    279     8  |      6      4  129  |
|  1267   479  124679  |   3  24579   246  |   1259*   259    8  |
|    26     8    2469  |  56   2459     1  |    259*     3    7  |
+----------------------+-------------------+---------------------+

I'm going to have to keep looking for a good example of a rule 4 common cells (nothing popped up in last night's runs). Also these rules are only sufficient. Assuming I haven't made an error, the next step will hopefully be developing necessary rules.
Last edited by Mike Barker on Mon Nov 27, 2006 1:51 am, edited 7 times in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Havard » Sat Nov 25, 2006 7:00 pm

Very nice Mike!:) I'll go through the examples properly later, but it looks very good!

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Carcul » Sat Nov 25, 2006 8:02 pm

Mike Barker wrote:Common 4-element Nice Loop: r9c9=8=r7c7-8-r7c5-1-r7c7=1=r4c7=5=r8c7~5~r9c9 => r9c9<>5


Why not writing [r9c9]=8=[r7c7]=1=[r4c7]=5=[r8c7]-5-[r9c9]?

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Mike Barker » Sat Nov 25, 2006 8:40 pm

Carcul, you are correct. I need to find a better example. Not sure why I didn't see that in the first place.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Steve R » Sat Nov 25, 2006 9:30 pm

The examples are fine, with or without Carcul’s variation. However, if I understand your notation correctly, the legend of the last should end ~5~, not ~1~.

When I looked at grouped simple nice chains some time ago I see I then thought the traditional rules applied with minimal changes. Specifically, taking A as a set of cells and x and y as candidates:
for x= A =y propagation required x ≠ y and |A| = 1
for x= A –y (and so x- A =y) propagation required x = y
for x- A –y propagation required x ≠ y and A an almost locked set.
As far as I can remember it didn’t seem to matter whether the sets of cells overlapped or not.

Is this wrong or is a more complicated version of nice loops at issue?

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Steve R » Tue Nov 28, 2006 6:49 pm

Here’s everything I know about simple nice loops.

In what follows A, B, … represent sets of cells which lack an entry. x, y, … represent candidates.

Nice links.

There are three varieties. In each case x is a candidate for at least one cell in A and for at least one cell in B.
Strong, written A =x= B, means that x must be entry for a cell in at least one of A and B.
Weak, written A -x- B, means that x can be entry for a cell in at most one of A and B.
Indifferent, written A =x- B, means that, if x is not an entry for any cell in A, it is not an entry for any cell in B (so, if x is an entry for a cell in B, it is also an entry for a cell in A).

Nice Joins

x= A =y is nice if x ≠ y and |A| = 1.
x- A -y is nice if x ≠ y and A is an almost locked set.
x= A -y is nice if x = y.
x- A =y is nice if x = y.

Nice chains

A nice chain is a sequence of nice links which abut at nice joins, such as:
A -x- B =x= C = …-y- E –z- F
If F = A, the chain is also a nice loop.

Continuity in nice loops

A loop is continuous if the join implicit in the two ends is nice. For example, substituting A for F in the above, the join z- A –x needs to satisfy the criteria for a nice join. In other cases the loop is discontinuous and A is the node of discontinuity.

Deductions from continuous nice loops.

Eliminations arise by reference to the links in the loop. For any strong link, A =x= B, or weak link, A -x- B, x falls to be eliminated from any cell which is a common associate of all those cells in the union of A and B having x as a candidate.

Deductions from discontinuous nice loops

Eliminations and placements arise only in respect of the node of discontinuity, A. The outcome depends on the nature of the discontinuity:
Case x= A =y
If x = y, x falls to be eliminated from any cell which is a common associate of all those cells in A having x as candidate.
Case x- A –y
If x = y, x may be eliminated from any cell in A for which it is a candidate.
Case x= A –y
If x ≠ y and |A| = 1, y may be eliminated from the single cell which A contains.
Case x- A =y
If x ≠ y and |A| = 1, x may be eliminated from the single cell which A contains.

Some of this may be of help to programmers. Comments and corrections are most welcome.

Steve
Last edited by Steve R on Sun Dec 10, 2006 8:49 pm, edited 1 time in total.
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Mike Barker » Sat Dec 09, 2006 3:09 pm

Steve, excellent summary of basic and grouped nice loops including some of the special requirements for grouped strong links. It agrees with what I have implemented. I've searched for necessary conditions for nodes to share a cell and have so far only seen problems between adjacent nodes and with elimination in end nodes. I've searched for a case where these conditions are not both necessary and sufficient. I can't help but believe that if in a loop fails to meet normal contradiction conditions (an ALS is reduced to n-1 candidates or a strong link cell must contain two candidates) there should be a problem, but have been unable to find any. Granted that nice loops with common cells are rare, but for now I see the list of necessary conditions as:
    1) unnecessary
    2) unnecessary
    3) the ending and starting nodes of adjacent grouped strong links cannot share a common cell if the node consists of more than one cell
    4) two ALS cannot share a common cell if the the common cell(s) contain the link label
    5) an ALS and the adjacent starting node of a strong link or a grouped strong link cannot share a cell
    6) an ALS and the adjacent ending node of a strong link or a grouped strong link cannot share a cell
    7/8) the starting and ending nodes of an ALS, strong link or grouped strong link can overlap as long as the above rules are met and elimination within cells of these nodes is not performed
Rule 4 can be seen in this example from the CoALS thread. In this case the grouped nice loop/xz-rule ALS is only valid if r6c9 doesn't contain "7".
Code: Select all
Valid Overlap 2-element Grouped Nice Loop: ALS:r6c459-7-ALS:r6c89|r5c79~16~ => r6c7<>1,r6c7<>6
+---------------------+------------------+---------------------+
|    2  13469   1349  |   139    139  8  |   1467  1467     5  |
|  157   1478   1458  |   125    125  6  |      9     3  1248  |
| 1356  13689  13589  |     4  12359  7  |    126   126  1268  |
+---------------------+------------------+---------------------+
|   13      2      6  |   179     19  5  |   1347     8    14  |
|   15     18      7  |   168      4  3  |   1256@    9   126@ |
|    9   1348  13458  |  1678*   168* 2  | 357-16   157@  16*@ |
+---------------------+------------------+---------------------+
|    8    369    239  |  2356   2356  1  |   2456  2456     7  |
|    4      5     12  |    26      7  9  |      8   126     3  |
| 1367   1367    123  | 23568   3568  4  |   1256  1256     9  |
+---------------------+------------------+---------------------+

Here is an example of a loop which fails necessary rule 5 resulting in invalid eliminations.
Code: Select all
Invalid 4-element Grouped Nice Loop: r4c4=1=r8c4=6=r9c4-6-r9c1=6=r8c2-6-ALS:r8c249-1-r4c4 => r8c4=16,r8c6<>4,r1c9<>4,r7c7<>4
+------------------+---------------------+----------------+
|  9      5     1  |   247    47      3  |   246  8  6-4  |
| 36    367   367  |   248     1    248  |    24  5    9  |
|  8      4     2  |     5     9      6  |     3  7    1  |
+------------------+---------------------+----------------+
|  5  23678  3679  |  1278*   67  12789  |  1678  4   68  |
|  4   2678    67  |     3   567   1278  | 15678  9  568  |
|  1    678   679  |   478  4567   4789  |  5678  3    2  |
+------------------+---------------------+----------------+
|  2      1     8  |     9     3     45  |   5-4  6    7  |
|  7    36#@    5  |  16-4@    8    1-4  |     9  2   34@ |
| 36*     9     4  |    67*    2     57  |    58  1  358  |
+------------------+---------------------+----------------+

There are examples where a puzzle meets the necessity rules, but not the sufficiency rules and still allows for a valid elimination, in the sense that the contradiction conditions are not violated. Here is an example with a cell, r6c9, common to 2 ALS with different "input" labels. This violates the sufficiency rule 4, but the ALS still contains "n" candidates.
Code: Select all
Common 4-element Grouped Nice Loop: ALS:r7c3567-5-ALS:r456c7|r6c89-9-r6c3-8-ALS:r369c9~4~ => r7c8<>4
+--------------+------------------+---------------------+
| 7   24   34  |   9    6      1  | 2358    258     58  |
| 9   12    5  |   4  378    378  |  237    127      6  |
| 6    8   13  |   2    5     37  |    4    179     19$ |
+--------------+------------------+---------------------+
| 1  356   89  | 678  347  34679  |  578@   459      2  |
| 2   56    7  |  68   14     49  |  156@     3   4589  |
| 4   36   89* |   5  137      2  |  167@   179@  189@$ |
+--------------+------------------+---------------------+
| 3    9  246* |   1   48*   468* |  258* 258-4      7  |
| 5   14  146  |  67    2   4678  |    9    148      3  |
| 8    7  124  |   3    9      5  |   12      6     14$ |
+--------------+------------------+---------------------+

Here's a similar example where the common cell, r3c6, is shared by two ALS, but both ALS maintain "n" candidates.
Code: Select all
Common 5-element Grouped Nice Loop: r9c3-1-r9c4=1=r2c4-1-ALS:r1235c6-8-r5c9=8=r3c9-8-ALS:r3c2567~3~ => r3c3<>3
+-------------------+-------------------+-----------------+
|    5     4     9  |   6     8     17@ |    17    3   2  |
|  137     6     8  | 123* 2345   1357@ |  1457   57   9  |
|    2    13$ 17-3  |   9   345$  135@$ |  1458$ 567  68* |
+-------------------+-------------------+-----------------+
|  189   159     4  |   7    56    568  |   589    2   3  |
| 3789     2   357  |   4     1    358@ |  5789  567  68* |
|   78    35     6  |  23   235      9  |    78    1   4  |
+-------------------+-------------------+-----------------+
|  139  1359    15  |   8    36    136  |     2    4   7  |
|    6     7     2  |   5     9      4  |     3    8   1  |
|    4     8    13* |  13*    7      2  |     6    9   5  |
+-------------------+-------------------+-----------------+

In this example the common cell r4c2 is found in the start of two strong links with different labels. Again there is no hard contradiction because even if the cell doesn't contain 7 or 9 it can still can contain 1 or 8.
Code: Select all
Common 3-element Grouped Nice Loop: r4c23=7=r4c6-7-ALS:r6c45|r4c4-9-r4c12=9=r5c2~7~r4c23 => r5c2<>7
+---------------------+---------------------+------------------+
|  349       5   468  |    7     1      89  |  46    38     2  |
|    7      46     1  |    3   289     289  |   5    48    69  |
|   39     289    28  |    6     5       4  | 138  1378  1379  |
+---------------------+---------------------+------------------+
|  159$  1789#$  578# |  189@    6  135789* | 138     2     4  |
|  156  1689-7*    3  |    4  2789  125789  |  18  1578   157  |
|    2    1478  4578  |   18@   78@  13578  |   9     6  1357  |
+---------------------+---------------------+------------------+
|  456    2346   256  | 1289   489     189  |   7   134    13  |
|    8      23     9  |   12    47      17  | 246   145  1356  |
|   14    1247   247  |    5     3       6  |  24     9     8  |
+---------------------+---------------------+------------------+

In this example, r2c6 is common to two strong links. Because one is grouped there isn't a hard contradiction (for example no candidates in a cell). Again, this may be another case where the sufficiency conditions in the original post were overly conservative, but, honestly, I would rest alot easier if 1) I could find a case where the new "necessary" conditions are not sufficient, 2) understand why if the necessary rules are followed then internal inconsistencies simply don't matter, 3) show that a basic/grouped nice loop simply can't be constructed with internal inconsistencies which are not simply the result of a smaller nice loop in a larger one (sounds fishy:) ).
Code: Select all
Common 3-element Grouped Nice Loop: r3c5=2=r2c6-2-ALS:r2c8|r13c9-4-r2c7=4=r2c46~4~r3c5 => r3c5<>4
+------------------+-------------------+------------------+
|    25  14    16  |    7     9     3  |   25    8    46@ |
|  2569   7     8  |  456$    1  246$# | 2456*  29@    3  |
| 23569  34    69  |  456  25-4*    8  |    1    7   469@ |
+------------------+-------------------+------------------+
|     8   9     3  |  145    45    14  |    7    6     2  |
|     7   5     4  |    2     6     9  |    8    3     1  |
|     1   6     2  |    8     3     7  |    9    4     5  |
+------------------+-------------------+------------------+
|     4  13     5  |  169     7   126  |  236   29     8  |
|    69   8  1679  |    3    24  1246  |  246    5   679  |
|    36   2   679  |   49     8     5  |  346    1   479  |
+------------------+-------------------+------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Mike Barker » Sun Dec 10, 2006 4:27 am

Here's another example of adjacent ALS in a grouped nice loop with a common cell (a CCALS which I mistakenly thought was a COALS). In my investigations of common cell grouped nice loops this type and cases where the start and end nodes overlap are by far the most prevalent.
Code: Select all
Common 3-element Grouped Nice Loop: ALS:r7c25678-2-ALS:r246c7-6-ALS:r6c4789~1~ => r7c4<>1
+------------------+--------------------+-------------------+
|   8    145   14  |      7    35    2  |   349   349    6  |
|  45      3    7  |      9    58    6  |    48@    2    1  |
|   6      2    9  |     38     1    4  |     7    38    5  |
+------------------+--------------------+-------------------+
|   1    468   48  |      5     2    3  |    46@    7    9  |
|   7     49    2  |      6    49    8  |     5     1    3  |
|   3     69    5  |     14$   79   17  |  248@$  468$  28$ |
+------------------+--------------------+-------------------+
|   9   1458*   6  | 2348-1   348*  15* |  1238*  358*   7  |
| 245  14578  148  |  12348  3678    9  |  1236  3568   28  |
|  25   1578    3  |    128   678  157  | 12689  5689    4  |
+------------------+--------------------+-------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby leon1789 » Sun Dec 10, 2006 6:46 pm

Another example where als A is a subset of als D :

Code: Select all
     a       b       c         d       e       f         g       h       i
  +-------------------------+-------------------------+-------------------------+
1 | 246     8       26      | 7       3       9       | 5       124     124     |
2 | 2379 AD.79      1       | 5       4       6       | 29      8       37      |
3 | 34579   4579  C.379     | 2       1       8       | 49    B.37      6       |
  +-------------------------+-------------------------+-------------------------+
4 | 2479    3       279     | 19      8       457     | 6       12457   12457   |
5 | 4679    14679   5       | 169     2       47      | 3       147     8       |
6 | 2467    1467    8       | 16      57      3       | 24      9       12457   |
  +-------------------------+-------------------------+-------------------------+
7 | 1     D.569   C.369     | 34      579     57      | 8       23456   23459   |
8 | 8       2     C.369     | 34      59      1       | 7       3456    3459    |
9 | 3579 AD.579     4       | 8       6       2       | 1     B.35      359     |
  +-------------------------+-------------------------+-------------------------+


als A=b2b9, B=h3h9, C=c3c7c8, D=b2b7b9

A --5-- B --7-- C --6-- D

so -7b3 , -7b5 , -7b6 , -5a9 , -9b3 , -9b5:)
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby Steve R » Mon Dec 11, 2006 12:52 am

Mike, thank you for your comment and the very clear examples. As you know, my summary of nice loops can be improved. The note has been edited to introduce the change.

Taking your points in turn:

3) This condition is equivalent to saying “the join x= A =y is nice when x ≠y and |A| = 1." It is necessary and sufficient.

4) The condition for forming the link A -x- B is just that x is a restricted common candidate of A and B. This applies whether A and B are ALSs or not. I do not think your condition quite matches this but it may be a matter of interpretation.

5) and 6) I’m not sure that I understand the point here. It seems to me that example 2 fails because of the fake “link”

r8c2 -6- r8c249

It is improper because 6 is not a restricted common candidate of the two sets r8c2 and r8c249.

Is it possible to clarify 5)? Perhaps there is a general chain like A =x= B -y- C where you have doubts when x = y, x ≠ y, some set is not an ALS or whatever.

7/8) Again I may have misunderstood but mention of eliminations makes me wonder if you are thinking of deductions to be made in respect of the node of discontinuity, A, when it takes the form x= A =x. The first version of my note said “if |A| = 1, place x in the (single) cell which comprises A." The corrected version is more general in saying “x falls to be eliminated from any cell which is a common associate of all those cells in A having x as candidate.” The two are the same if |A| = 1. Certainly I agree that elimination from the cell(s) in A may occur only if |A| = 1.

All the examples other than the second are fine as far as I can see. There may be a curiosity in example 4. 7 is properly eliminated from the node of discontinuity, r5c2, but this cell is placed in the middle of the nice chain rather than at the end. A feature of the print command or a hint that we are coming from different directions?

I hope this helps to take us a step forward.

Leon

Yes, your example is fine, too. However what we’re really after is a nice loop which meets the requirements of my 28 November note but makes an invalid elimination. My story/hope is that there is none; Mike is not entirely convinced.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Mike Barker » Mon Dec 11, 2006 4:56 am

Steve, thanks for the review. To respond to your comments:
Steve wrote:5) and 6) I’m not sure that I understand the point here. It seems to me that example 2 fails because of the fake “link”

Probably a matter of perspective. I think of restricted common as pertaining to ALS. These rules deal with a link between a strong link and an ALS. The result is the same except that since every cell of the strong link will contain the link label, the rule can simply be stated that an ALS and a strong link cannot be linked if they share a common cell(s).
Steve wrote:7/8) Again I may have misunderstood but mention of eliminations makes me wonder if you are thinking of deductions to be made in respect of the node of discontinuity, A, when it takes the form x= A =x. The first version of my note said “if |A| = 1, place x in the (single) cell which comprises A." The corrected version is more general in saying “x falls to be eliminated from any cell which is a common associate of all those cells in A having x as candidate.” The two are the same if |A| = 1. Certainly I agree that elimination from the cell(s) in A may occur only if |A| = 1.

When I'm looking at common cells in the starting and ending node of a nice loop, they need not be the same node and there are no requirements on restricted common cells. These are examples of overlapping nice loops which Myth introduced here. Any candidate which can see all of the cells of the starting and ending nodes of a nice loop which contain the candidate can be eliminated. I believe this combined with the next comment produce all of the eliminations of a discontinuous nice loop. I'll identify this type of elimination as ALS:r6c459-7-ALS:r6c89|r5c79~16~ to show that the elimination is in cells which can see the starting and ending nodes (note that these can be part of the nice loop, but not these nodes). Because there can be multiple eliminations I don't show the loop completed.
Steve wrote:All the examples other than the second are fine as far as I can see. There may be a curiosity in example 4. 7 is properly eliminated from the node of discontinuity, r5c2, but this cell is placed in the middle of the nice chain rather than at the end. A feature of the print command or a hint that we are coming from different directions?

In my view of the world r5c2 is at the end of the loop (which I guess is better described as a chain). Candidates in the start and end nodes can be eliminated if, because of the cell locations only, a link could be made between the nodes, but the labels or candidates do not allow a link. In this case elimination(s) can occur in the starting node for any candidate which could label a link out of the ending node and vice-versa. I'll indicate this type of an elimination within the starting and ending node as: r4c23=7=r4c6-7-ALS:r6c45|r4c4-9-r4c12=9=r5c2~7~r4c23 where the "~" implies this is not a valid link
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Mon Dec 11, 2006 1:03 pm

Mike Barker wrote:
Code: Select all
Common 3-element Grouped Nice Loop: r4c23=7=r4c6-7-ALS:r6c45|r4c4-9-r4c12=9=r5c2~7~r4c23 => r5c2<>7
+---------------------+---------------------+------------------+
|  349       5   468  |    7     1      89  |  46    38     2  |
|    7      46     1  |    3   289     289  |   5    48    69  |
|   39     289    28  |    6     5       4  | 138  1378  1379  |
+---------------------+---------------------+------------------+
|  159$  1789#$  578# |  189@    6  135789* | 138     2     4  |
|  156  1689-7*    3  |    4  2789  125789  |  18  1578   157  |
|    2    1478  4578  |   18@   78@  13578  |   9     6  1357  |
+---------------------+---------------------+------------------+
|  456    2346   256  | 1289   489     189  |   7   134    13  |
|    8      23     9  |   12    47      17  | 246   145  1356  |
|   14    1247   247  |    5     3       6  |  24     9     8  |
+---------------------+---------------------+------------------+

Mike Barker wrote:
Steve wrote:There may be a curiosity in example [edit: 5]. 7 is properly eliminated from the node of discontinuity, r5c2, but this cell is placed in the middle of the nice chain rather than at the end. A feature of the print command or a hint that we are coming from different directions?

In my view of the world r5c2 is at the end of the loop (which I guess is better described as a chain). Candidates in the start and end nodes can be eliminated if, because of the cell locations only, a link could be made between the nodes, but the labels or candidates do not allow a link. In this case elimination(s) can occur in the starting node for any candidate which could label a link out of the ending node and vice-versa. I'll indicate this type of an elimination within the starting and ending node as: r4c23=7=r4c6-7-ALS:r6c45|r4c4-9-r4c12=9=r5c2~7~r4c23 where the "~" implies this is not a valid link

I haven't been following the "necessary and sufficient" discussion, so I've only a question about the notation. Instead of your ...

r4c23=7=r4c6-7-ALS:r6c45|r4c4-9-r4c12=9=r5c2~7~r4c23

... why not the "standard" nice loop notation?

r5c2-7-r4c23=7=r4c6-7-ALS:r6c45|r4c4-9-r4c12=9=r5c2, implying r5c2<>7

IOW ... rather than add an invalid link at the end, why not add a valid one at the beginning?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Mon Dec 11, 2006 2:38 pm

That is clearly another way to do it, but since r5c2 is neither a ALS/bivalue or a basic/grouped strong link it is not the place I would start the loop, rather the linking of r5c2 doesn't occur until the loop has been constructed (unless you traverse the loop in the opposite direction, but then you have the same issue with r4c23). The implication is that you are constructing a forcing chain rather than a nice loop.

I don't have to use the "~" in the notation, but I like the clear distinction between a continuous and discontinuous nice loop (I don't have to look at the labels to know which it is). If this is an issue I can drop the use, but I still like having r5c2 at the end for the above reasons.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Tue Dec 12, 2006 12:38 am

Mike Barker wrote:... since r5c2 is neither a ALS/bivalue or a basic/grouped strong link it is not the place I would start the loop, rather the linking of r5c2 doesn't occur until the loop has been constructed ...

By "start", I presume you mean you begin constructing a forcing chain by searching for a strong inference which, except for ALS, is due to a strong link. This makes perfect sense since
  • every forcing chain needs at least one strong inference, and more importantly,
  • every puzzle has far fewer strong inferences than weak ones.
But I fail to see how this relates to the final expression for the resulting loop. You might start near the middle, and work both ways to the discontinuity. Or you might start at the discontinuity and loop back to it. No matter the construction sequence, if the constructed chain is the same the loop expression should be the same too IMO.

... (unless you traverse the loop in the opposite direction, but then you have the same issue with r4c23). The implication is that you are constructing a forcing chain rather than a nice loop.

Sorry, but I don't see the issue. Would you please take another shot at explaining it?

As for "forcing chain" vs. "nice loop", I see little or no distinction ... at least not for simple chains (loops) with single inferences used for each node. "Forcing chain" is the technique ... and the "nice loop" is the expression for the associated double implication streams found by the technique.

I don't have to use the "~" in the notation, but I like the clear distinction between a continuous and discontinuous nice loop (I don't have to look at the labels to know which it is).

Aren't you then sometimes using "~" for a weak inference and other times for a strong inference? And isn't that different than using "~" to indicate "invalid link?"
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA


Return to Advanced solving techniques