The New Sudoku Players' Forum

[daj95376]

This chain is rare among those that I find using BFS. Does anyone find it to be common?

[cell]=n= ... =n=[cell] --> [cell]=n

Code: Select all

 +-----------------------------------------------------+
 |  1    3    6    |  8    4    5    |  27   9    27   |
 |  9    5    27   |  6    23   17   | b34   8   a134  |
 |  8    27   4    |  9    23   17   |  5    13   6    |
 |-----------------+-----------------+-----------------|
 |  4    1    3    |  2    7    9    |  6    5    8    |
 |  2    79   5    |  4    8    6    | c379  137  137  |
 |  6    8    79   |  1    5    3    |  47   2   d479  |
 |-----------------+-----------------+-----------------|
 |  37   6    1    |  5    9    2    |  8    4    37   |
 |  5    4    29   |  37   6    8    |  1    37   29   |
 |  37   29   8    |  37   1    4    |  29   6    5    |
 +-----------------------------------------------------+

 r2c9 =4= r2c7 =3= r5c7 =9= r6c9 =4= r2c9  =>  [r2c9]=4


Code: Select all

 +-----------------------------------------------------+
 |  5    3    49   |  7    6    2    |  8    1    49   |
 |  89   1   b279  |  3    4    58   |  25   6    79   |
 | a67  c24   68   |  58   9    1    |  25   3   d47   |
 |-----------------+-----------------+-----------------|
 |  2    8    59   |  1    3    59   |  4    7    6    |
 |  67   67   3    |  2    8    4    |  9    5    1    |
 |  4    59   1    |  59   7    6    |  3    8    2    |
 |-----------------+-----------------+-----------------|
 |  3    249  24   |  6    5    7    |  1    49   8    |
 |  89   57   57   |  4    1    89   |  6    2    3    |
 |  1    469  68   |  89   2    3    |  7    49   5    |
 +-----------------------------------------------------+

 r3c1 =7= r2c3 =2= r3c2 =4= r3c9 =7= r3c1  =>  [r3c1]=7


Code: Select all

 +--------------------------------------------------------------------------------+
 |  1      d6789B   579     |  589     2       4589    |  678     457     3       |
 | a2568    4       2357    |  1358    135     358     |  1278    9       1567    |
 |  2589    2389    2359    |  6       13459   7       |  128     125     145     |
 |--------------------------+--------------------------+--------------------------|
 |  259     1239    8       |  123579  13569   2359    |  4       137     1679    |
 |  7       139     13459   |  1359    8       34569   |  1369    13      2       |
 |  249     1239    6       |  12379   1349    239     |  5       8       179     |
 |--------------------------+--------------------------+--------------------------|
 | b2689D  c2789C   279     |  4       3569    1       |  2379    2357    579     |
 |  249     5       1279    |  2389    39      2389    |  12379   6       1479    |
 |  3       1269A   1249    |  259     7       2569    |  129     1245    8       |
 +--------------------------------------------------------------------------------+

 r2c1 =6= r7c1 =8= r7c2 =7= r1c2 =6= r2c1  =>  [r2c1]=6   -or-
 r9c2 =6= r1c2 =7= r7c2 =8= r7c1 =6= r9c2  =>  [r9c2]=6


Code: Select all

 +-----------------------------------------------------------------------+
 |  1      578    5789   | c569    2      49     | d6789   479    3      |
 |  279    4      23     |  1369   8      139    |  2679   5      267    |
 |  259    38     6      | b459    7      349    |  1     e489    24     |
 |-----------------------+-----------------------+-----------------------|
 |  679    1678   789    |  2      34     5      |  379    13479  147    |
 |  3      2      4      |  79     1      79     |  5      6      8      |
 |  579    157    579    |  8      34     6      |  2379   3479   1247   |
 |-----------------------+-----------------------+-----------------------|
 |  26     36     1      |  37     9     g28     |  4     f378    5      |
 |  4      9      37     |  137    5      1378   |  368    2      16     |
 |  8      57     2357   | a34     6     h124    |  37     137    9      |
 +-----------------------------------------------------------------------+

 r9c4 =4= r3c4 =5= r1c4 =6= r1c7 =8= r3c8 -8- r7c8 =8= r7c6 =2= r9c6 =4= r9c4  =>  [r9c4]=4


[ronk]

This chain is rare among those that I find using BFS. Does anyone find it to be common?

[cell]=n= ... =n=[cell] --> [cell]=n

Using my full arsenal of logical techniques -- except for franken and mutant fish -- I see 104 different chains of this type in the top1465. I wouldn't call that rare, but perhaps they occur much less frequently in a truly random puzzle collection.

These chains are actually found with a multi-digit coloring technique. The only other "chain technique" used was ALS-xz, but my implementation is not exhaustive.

What is "BFS?"

[daj95376]

What is "BFS?"

Breadth-First Search; i.e., short chains found and used before longer chains.

Although my solver is only able to solve 808 of the top1465 without resorting to forcing nets, it did manage to partially solve the remainder. Of the 6,082 chains generated, only 15 were of this type.

It would appear that something is impacting the presence of this chain in my solutions. Thanks for checking on it for me

[hobiwan]

I checked your four grids and found the following:

Code: Select all

First grid:
r2c9 =4= r2c7 =3= r5c7 =9= r6c9 =4= r2c9 => r2c9=4
r5c7 =9= r5c2 =7= r3c2 -7- r3c6 -1- r3c8 =1= r2c9 =4= r6c9 =9= r5c7 => r5c7=9
r5c9 =1= r5c8 -1- r3c8 -3- r2c7 =3= r5c7 =9= r6c9 =4= r2c9 =1= r5c9 => r5c9=1
r6c7 =4= r6c9 =9= r5c7 =3= r2c7 =4= r6c7 => r6c7=4

** r1c9 =2= r8c9 =9= r6c9 =4= r6c7 -4- r2c7 -3- r2c5 -2- r2c3 =2= r8c3 -2- r8c9 =2= r1c9 => r1c9=2

Second grid:
r2c9 =7= r2c3 =2= r3c2 =4= r3c9 =7= r2c9 => r2c9=7
r3c1 =7= r3c9 =4= r3c2 =2= r2c3 =7= r3c1 => r3c1=7
r5c2 =7= r5c1 -7- r3c1 =7= r3c9 =4= r3c2 =2= r2c3 =7= r8c3 -7- r8c2 =7= r5c2 => r5c2=7
r7c8 =9= r7c2 =2= r3c2 -2- r3c7 -5- r3c4 -8- r9c4 -9- r9c8 =9= r7c8 => r7c8=9
r9c2 =6= r9c3 =8= r3c3 -8- r2c1 -9- r2c9 -7- r2c3 =7= r8c3 -7- r8c2 =7= r5c2 =6= r9c2 => r9c2=6

Third grid:
r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r2c1 -6- r2c9 =6= r1c7 => r1c7=6
r2c1 =6= r7c1 =8= r7c2 =7= r1c2 =6= r2c1 => r2c1=6
r4c9 =6= r4c5 -6- r7c5 =6= r7c1 =8= r7c2 =7= r1c2 =6= r1c7 -6- r5c7 =6= r4c9 => r4c9=6
r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 => r5c6=6
r7c5 =6= r7c1 =8= r7c2 =7= r1c2 =6= r9c2 -6- r9c6 =6= r7c5 => r7c5=6
r9c2 =6= r1c2 =7= r7c2 =8= r7c1 =6= r9c2 => r9c2=6


** r1c6 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r1c6 => r1c6=4
** r3c9 =4= r3c5 -4- r6c5 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r1c6 -4- r1c8 =4= r3c9 => r3c9=4
** r4c1 =5= r5c3 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r5c3 =5= r4c1 => r4c1=5
** r5c3 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r5c3 => r5c3=4
** r6c5 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r6c5 => r6c5=4
** r8c1 =4= r6c1 -4- r6c5 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r5c3 -4- r9c3 =4= r8c1 => r8c1=4
** r9c8 =4= r9c3 -4- r5c3 =4= r5c6 =6= r5c7 -6- r1c7 =6= r1c2 =7= r7c2 =8= r7c1 =6= r7c5 -6- r4c5 =6= r5c6 =4= r5c3 -4- r9c3 =4= r9c8 => r9c8=4

Fourth grid:
r9c4 =4= r9c6 =2= r7c6 =8= r7c8 -8- r3c8 =8= r1c7 =6= r1c4 =5= r3c4 =4= r9c4 => r9c4=4


So except for the fourth grid IMO there are rather many of them.

It was a nice possibility to check my new nice loop algorithm. The NLs marked with "**" aren't really loops, more like Denis Berthier's lassos. Would you consider them valid nice loops?

[ronk]

I checked your four grids and found the following:

Code: Select all

First grid:
r2c9 =4= r2c7 =3= r5c7 =9= r6c9 =4= r2c9 => r2c9=4
r5c7 =9= r5c2 =7= r3c2 -7- r3c6 -1- r3c8 =1= r2c9 =4= r6c9 =9= r5c7 => r5c7=9
r5c9 =1= r5c8 -1- r3c8 -3- r2c7 =3= r5c7 =9= r6c9 =4= r2c9 =1= r5c9 => r5c9=1
r6c7 =4= r6c9 =9= r5c7 =3= r2c7 =4= r6c7 => r6c7=4

** r1c9 =2= r8c9 =9= r6c9 =4= r6c7 -4- r2c7 -3- r2c5 -2- r2c3 =2= r8c3 -2- r8c9 =2= r1c9 => r1c9=2

As I understand daj95376's filter, each strong inference must be due to a conjugate pair. If so, your 2nd, 3rd and 5th chains do not qualify.

[edit: Being unsure what a "lasso" is, my opinion about it was deleted.]

[daj95376]

Thanks hobiwan for all of the input. It will take me awhile to cross-check all of it with my results.

In the first grid, I never needed to go past chains of length matching these two from your results. That's why two of your chains are missing from my output.

Code: Select all

r2c9 =4= r2c7 =3= r5c7 =9= r6c9 =4= r2c9 => r2c9=4
r6c7 =4= r6c9 =9= r5c7 =3= r2c7 =4= r6c7 => r6c7=4


In addition, I discovered that my redundancy checking sub-module prevented your second chain (above) from being listed.

My solver actually stores eliminations; so, for your first chain (above), my output actually reads:

Code: Select all

 -4r2c9  4r2c7  3r5c7  9r6c9  4r2c9        [chain__4] <> 13 [r2c9]


When it came to cell [r6c7], my solver found a different chain first that performed the same elimination. (The final elimination in this chain is added for readibility but not counted in the length of the chain. Thus, the chain depth is the same as the chain above.)

Code: Select all

 -4r6c7  4r2c7  3r5c7  9r5c2  7r6c3 -7r6c7 [chain__2] <> 7  [r6c7]


My redundancy checking sub-module dropped the chain matching your second chain because it was deemed a redundant elimination. I now have one explanation for why I'm finding fewer of the chain__4 types -- chain__2 types are the most common reported by my solver.

[daj95376]

Although hobiwan's 5th chain (for instance) appears technically acceptable as an AIC.

Code: Select all

r1c9 =2= r8c9                                                                         (bilocation SL; SI)
      2= r8c9 =9                                                                      (?-value    WL; WI)
         r8c9 =9= r6c9                                                                (bilocation SL; SI)
               9= r6c9 =4                                                             (?-value    WL; WI)
                  r6c9 =4= r6c7                                                       (bilocation SL; SI)
                           r6c7 -4- r2c7                                              (peers      WL; WI)
                                 4- r2c7 -3                                           (bivalue    SL; SI)
                                    r2c7 -3- r2c5                                     (peers      WL; WI)
                                          3- r2c5 -2                                  (bivalue    SL; SI)
                                             r2c5 -2- r2c3                            (peers      WL; WI)
                                                      r2c3 =2= r8c3                   (bilocation SL; SI)
                                                               r8c3 -2- r8c9          (peers      WL; WI)
                                                                        r8c9 =2= r1c9 (bilocation SL; SI)
_________________________________________________________________________________________________________

r1c9 =2= r8c9 =9= r6c9 =4= r6c7 -4- r2c7 -3- r2c5 -2- r2c3 =2= r8c3 -2- r8c9 =2= r1c9 => r1c9=2


My solver would have found this shorter chain first and never encountered the longer chain.

Code: Select all

r8c9 =9= r6c9 =4= r6c7 -4- r2c7 -3- r2c5 -2- r2c3 =2= r8c3 -2- r8c9  => r8c9<>2
_______________________________________________________________________________


[Edit: removed 2= from front of second chain. removed incorrect comment about ronk's post.]

[ronk]

I believe this is what ronk is saying.

I was saying I thought there isn't supposed to be a ... -x- rMcN -y- ... anywhere in the chain. If it is permissible, then my count earlier for the top1465 is meaningless.

[daj95376]

I was saying I thought there isn't supposed to be a ... -x- rMcN -y- ... anywhere in the chain. If it is permissible, then my count earlier for the top1465 is meaningless.

ronk: I'm sorry if I left you with the impression that only conjugate links were allowed. The ellipsis (...) meant any legitimate intermediate chaining is allowed. Right now, my chain routine is limited to singles found in either bivalue cells or through conjugate links.

My examples above just happen to be predominantly conjugate links. It's possible the BFS approach finds them to (typically) be more efficient. (This is a guess!)

[hobiwan]

Thanks hobiwan for all of the input. It will take me awhile to cross-check all of it with my results.

When I started writing my solver I wanted it to be able to display all possible steps for a candidate grid. That's the reason why all my search routines are exhaustive (or at least should be...).
For your grids I was interested in how many of your "[cell]=n= ... =n=[cell] --> [cell]=n" where present (and "beeing present" of course doesn't mean "should be used" or even "should be found by a solver" - some of them are ridiculously long and complicated). I should have posted the ratios instead of the chains to make that clear. Here they are:

Grid 1: 5 out of 38
Grid 2: 5 out of 34
Grid 3: 13 out of 65
Grid 4: 1 out of 3

In addition, I discovered that my redundancy checking sub-module prevented your second chain (above) from being listed.

My solver actually stores eliminations; ...

My solver does the same, so the results should be taken with a grain of salt.

[hobiwan]

[edit: Being unsure what a "lasso" is, my opinion about it was deleted.]

A lasso is an nrc(z)t-chain that links back to the middle of the chain, thus providing a contradiction.

r1c9 =2= r8c9 =9= r6c9 =4= r6c7 -4- r2c7 -3- r2c5 -2- r2c3 =2= r8c3 -2- r8c9 =2= r1c9 => r1c9=2

Although hobiwan's 5th chain (for instance) appears technically acceptable as an AIC...

My solver would have found this shorter chain first and never encountered the longer chain.

Code: Select all

2= r8c9 =9= r6c9 =4= r6c7 -4- r2c7 -3- r2c5 -2- r2c3 =2= r8c3 -2- r8c9  => r8c9<>2
__________________________________________________________________________________


True of course. Since the chain loops back to the middle of the chain there has to be a shorter loop present. My old chaining code didn't allow loops to the middle of a chain for exactly that reason (it would have found that smaller loop later on anyway). On the other hand it seems to be the only nice loop present for r1c9.

So again my question to the nice guys: Would you consider it a valid nice loop (it follows the propagation rules AFAIKS), or would you prefer to write it as a forcing chain:

Code: Select all

r1c9<>2 r8c9=2 r6c9=9 r6c7=4 r2c7=3 r2c5=2 r8c3=2 r8c9<>2 ~[r8c9]

[ronk]

Would you consider it a valid nice loop (it follows the propagation rules AFAIKS), or would you prefer to write it as a forcing chain:

Code: Select all

r1c9<>2 r8c9=2 r6c9=9 r6c7=4 r2c7=3 r2c5=2 r8c3=2 r8c9<>2 ~[r8c9]

Although both are logically correct, I would use neither. I would make the elimination r8c9<>2 with a nice loop, and let the hidden single take care of r1c9. IOW I view r1c9=2 as a direct result of r8c9<>2.



The strong inference r8c9=2=r1c9 is a "stub" attached to the loop, a stub traversed once in each direction ... seemingly just to make a placement rather than an elimination. I don't think this should be allowed in nice loops.

As to forcing chain notation, whatever that might be: Personally, I dislike ... make that strongly dislike ... forcing chain notation.

[edits: typos corrected, thanks to daj95376; added image]

[hobiwan]

The strong inference r8c9=2=r1c9 is a "stub" attached to the loop, a stub traversed once in each direction ... seemingly just to make a placement rather than an elimination. I don't think this should be allowed in nice loops.

Looks like I should put back some of my old checks into my new code...
Thanks anyway for the answer.

[udosuk]

Your first 3 or 4 moves are all Strong Wings according to this thread.

Code: Select all

 +-----------------------------------------------------+
 |  1    3    6    |  8    4    5    |  27   9    27   |
 |  9    5    27   |  6    23   17   | b34   8   a134  |
 |  8    27   4    |  9    23   17   |  5    13   6    |
 |-----------------+-----------------+-----------------|
 |  4    1    3    |  2    7    9    |  6    5    8    |
 |  2    79   5    |  4    8    6    | c379  137  137  |
 |  6    8    79   |  1    5    3    |  47   2   d479  |
 |-----------------+-----------------+-----------------|
 |  37   6    1    |  5    9    2    |  8    4    37   |
 |  5    4    29   |  37   6    8    |  1    37   29   |
 |  37   29   8    |  37   1    4    |  29   6    5    |
 +-----------------------------------------------------+

4 @ b3 locked @ r2c79
9 @ b6 locked @ r5c7+r6c9
3 @ c7 locked @ r25c7
4 @ c9 locked @ r26c9

r5c7 can't be 3 & 9 simutaneously.
If r5c7<>3 => r2c7=3 => r2c9=4
If r5c7<>9 => r6c9=9 => r2c9=4
Therefore r2c9 must be 4.

Code: Select all

 +-----------------------------------------------------+
 |  5    3    49   |  7    6    2    |  8    1    49   |
 |  89   1   b279  |  3    4    58   |  25   6    79   |
 | a67  c24   68   |  58   9    1    |  25   3   d47   |
 |-----------------+-----------------+-----------------|
 |  2    8    59   |  1    3    59   |  4    7    6    |
 |  67   67   3    |  2    8    4    |  9    5    1    |
 |  4    59   1    |  59   7    6    |  3    8    2    |
 |-----------------+-----------------+-----------------|
 |  3    249  24   |  6    5    7    |  1    49   8    |
 |  89   57   57   |  4    1    89   |  6    2    3    |
 |  1    469  68   |  89   2    3    |  7    49   5    |
 +-----------------------------------------------------+

7 @ b1 locked @ r2c3+r3c1
2 @ b1 locked @ r2c3+r3c2
7 @ r3 locked @ r3c19
4 @ r3 locked @ r3c29

r3c2 can't be 2 & 4 simultaneously.
If r3c2<>2 => r2c3=2 => r3c1=7
If r3c2<>4 => r3c9=4 => r3c1=7
Therefore r3c1 must be 7.

Code: Select all

 +--------------------------------------------------------------------------------+
 |  1      d6789B   579     |  589     2       4589    |  678     457     3       |
 | a2568    4       2357    |  1358    135     358     |  1278    9       1567    |
 |  2589    2389    2359    |  6       13459   7       |  128     125     145     |
 |--------------------------+--------------------------+--------------------------|
 |  259     1239    8       |  123579  13569   2359    |  4       137     1679    |
 |  7       139     13459   |  1359    8       34569   |  1369    13      2       |
 |  249     1239    6       |  12379   1349    239     |  5       8       179     |
 |--------------------------+--------------------------+--------------------------|
 | b2689D  c2789C   279     |  4       3569    1       |  2379    2357    579     |
 |  249     5       1279    |  2389    39      2389    |  12379   6       1479    |
 |  3       1269A   1249    |  259     7       2569    |  129     1245    8       |
 +--------------------------------------------------------------------------------+

6 @ b1 locked @ r1c2+r2c1
8 @ b7 locked @ r7c12
6 @ c1 locked @ r27c1
7 @ c2 locked @ r17c2

r7c2 can't be 7 & 8 simutaneously.
If r7c2<>7 => r1c2=7 => r2c1=6
If r7c2<>8 => r7c1=8 => r2c1=6
Therefore r2c1 must be 6.

7 @ c2 locked @ r17c2
6 @ c2 locked @ r19c2
8 @ b7 locked @ r7c12
6 @ b7 locked @ r7c1+r9c2

r7c2 can't be 7 & 8 simutaneously.
If r7c2<>7 => r1c2=7 => r9c2=6
If r7c2<>8 => r7c1=8 => r9c2=6
Therefore r9c2 must be 6.

As for your last move, I won't call it "Strong Chain" because you did use a weak link in it.

IMHO we should distinguish Strong Wing from other chains because like XY-Wing it has a pivot/pilot cell, 2 wing cells and 1 elimination cell, so it's better structured than any random chain moves.

I also propose abbreviating it as S-Wing but after the W-Wing/Y-Wing confusion I'm not sure I'll touch nomenclature again.