Nice Loop Question (again)

Advanced methods and approaches for solving Sudoku puzzles

Postby hobiwan » Sun Feb 22, 2009 6:09 am

Nice Loops prove to be trickier than i thought:(

Here is a puzzle I used as test case for Grouped Continuous Nice Loops:
Code: Select all
3.2....1....97.............5...8.6....15...7..8..4....9....1.27.1.4.......5..79..

After singles my solver used the following:
Code: Select all
.---------------------.------------------------------.-------------------------.
| 3     45-679  2     | *68      *56      45-68      | 4578    1       45-689  |
| 1     456     468   |  9        7       2345-68    | 23458   34568   234568  |
| 4678  45679   46789 |  23-6-8   1       2345-68    | 234578  345689  2345689 |
:---------------------+------------------------------+-------------------------:
| 5     23479   3479  |  1        8       239        | 6       349     2349    |
| 246   23469   1     |  5        2369    2369       | 2348    7       23489   |
| 26    8       369   |  7        4       2369       | 1       359     2359    |
:---------------------+------------------------------+-------------------------:
| 9     346     3468  | *368     *356     1          | 3458    2       7       |
| 2678  1       3678  |  4       *23569  *-2-35-68-9 | 358     3568    3568    |
| 2468  2346    5     | *2368     236     7          | 9       3468    1       |
'---------------------'------------------------------'-------------------------'

Grouped Continuous Nice Loop r8c6 =5= r78c5 -5- r1c5 -6- r1c4 -8- r79c4 =8= r8c6 => r8c6<>2369, r1c269,r23c6,r3c4<>6, r3c4<>8

After a small rewrite of my chaining code I got a slightly shorter version instead which is missing some of the eliminations:
Code: Select all
.--------------------.----------------------------.-------------------------.
| 3     45679  2     | A68    A56      4568       | 4578    1       45689   |
| 1     456    468   |  9      7       234568     | 23458   34568   234568  |
| 4678  45679  46789 |  2368   1       234568     | 234578  345689  2345689 |
:--------------------+----------------------------+-------------------------:
| 5     23479  3479  |  1      8       239        | 6       349     2349    |
| 246   23469  1     |  5      2369    2369       | 2348    7       23489   |
| 26    8      369   |  7      4       2369       | 1       359     2359    |
:--------------------+----------------------------+-------------------------:
| 9     346    3468  | *368   *356     1          | 3458    2       7       |
| 2678  1      3678  |  4     *23569  *-2-35-68-9 | 358     3568    3568    |
| 2468  2346   5     | *2368   236     7          | 9       3468    1       |
'--------------------'----------------------------'-------------------------'

Grouped Continuous Nice Loop 8= r8c6 =5= r78c5 -5- ALS:r1c45 -8- r79c4 =8= r8c6 =5 => r8c6<>2369

What I am not really clear about is how to handle ALS nodes in CNLs. the weak link ALS:r1c45 -8- r79c4 should probably eliminated 8 from r1c4, but what about candidate 6?

Is there a general rule regarding ALS? The example looks like "eliminate all candidates the resulting locked set would eliminate" but is that generally true?
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Sun Feb 22, 2009 7:24 am

hobiwan wrote:Grouped Continuous Nice Loop 8= r8c6 =5= r78c5 -5- ALS:r1c45 -8- r79c4 =8= r8c6 =5 => r8c6<>2369

What I am not really clear about is how to handle ALS nodes in CNLs. the weak link ALS:r1c45 -8- r79c4 should probably eliminated 8 from r1c4, but what about candidate 6?

Is there a general rule regarding ALS? The example looks like "eliminate all candidates the resulting locked set would eliminate" but is that generally true?

Yes, that's true. For a continuous loop ...

Starting with the candidate values of the now locked set, subtract the restricted common digit (RCD) values. If any candidate values remain, eliminate any like-valued-candidate that can see all cells of the ALS.

If you wish to also further break-down candidate location within the ALS, the last sentence can be modified to ...

If any candidate values remain, eliminate any like-valued-candidate that can see all the ALS candidates of that value.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby hobiwan » Sun Feb 22, 2009 9:11 pm

ronk, thanks for the answer!

ronk wrote:If you wish to also further break-down candidate location within the ALS, the last sentence can be modified to ...

If any candidate values remain, eliminate any like-valued-candidate that can see all the ALS candidates of that value.

When using the above excluding the RCs seems to be superfluous. An ALS node in a CNL would then simply eliminate any like-valued-candidate that is not part of the chain and can see all the ALS candidates of that value.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby aran » Mon Feb 23, 2009 12:31 am

hobiwan wrote:ronk, thanks for the answer!

ronk wrote:If you wish to also further break-down candidate location within the ALS, the last sentence can be modified to ...

If any candidate values remain, eliminate any like-valued-candidate that can see all the ALS candidates of that value.

When using the above excluding the RCs seems to be superfluous. An ALS node in a CNL would then simply eliminate any like-valued-candidate that is not part of the chain and can see all the ALS candidates of that value.


Further to that :
I would have to say that your example illustrates IMHO a certain weakness in NL notation.
To explain
1. the irrefutable logic in continuous nice loops is that the weak links are conjugate.
2. the concision of NL notation as your second example shows can make locating these weak links difficult : for example in this excerpt from your chain : r78c5 -5- ALS:r1c45 -8- r79c4 =8
the weak links are "concised" away and have to be restored mentally : in fact they are : 5r78c5/5r1c5, 6r1c5/6r1c4 and 8r1c4/8r79c4. Not at all transparent IMO. Indeed one could speculate this may well be why your solver missed the resulting eliminations in its second version.
3. regardless of whether there is a CNL, if merely advancing the chain in the event of a "not ALS" (another NL speciality) requires a rule like the one given in an earlier post, then one does have to wonder.

No such problems are encountered in Eureka notation.
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Mon Feb 23, 2009 12:52 am

The less concise ...

r8c6 =5= r78c5 -5- ALS:(r1c5 =5|6|8= r1c4) -8- r79c4 =8= r8c6, continuous loop

... but using bivalues makes more sense:

r8c6 =5= r78c5 -5- r1c5 -6- r1c4 -8- r79c4 =8= r8c6, continuous loop
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby DonM » Mon Feb 23, 2009 2:35 am

aran wrote:No such problems are encountered in Eureka notation.


I agree. I started with NL notation and converted to Eureka notation because IMO it clearly mirrors the underlying logic. Even now when I notate a chain in both formats, I find that the NL version, at least for me, doesn't always clearly 'describe' what's going on. Not to mention that because of the fact that nice loops don't tend to show what's going on within a cell, you have to make sure you follow all the NL rules or the chain will be invalid. With the Eureka/AIC notation, the only real rule is to keep the inferences alternating which is pretty easy to do and much less error-prone. Just my view though.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby hobiwan » Mon Feb 23, 2009 2:50 am

Thanks for all your help!

PS: Could we please let this thread be an AIC-NL notation argument free zone?
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby aran » Mon Feb 23, 2009 3:51 am

hobiwan wrote:Thanks for all your help!

PS: Could we please let this thread be an AIC-NL notation argument free zone?

These aren't idle arguments as you might appear to suggest...in this context, the difference is relevant : even your solver was bamboozled by NL.
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Mon Feb 23, 2009 7:01 am

hobiwan wrote:
ronk wrote:If you wish to also further break-down candidate location within the ALS, the last sentence can be modified to ...

If any candidate values remain, eliminate any like-valued-candidate that can see all the ALS candidates of that value.

When using the above excluding the RCs seems to be superfluous. An ALS node in a CNL would then simply eliminate any like-valued-candidate that is not part of the chain and can see all the ALS candidates of that value.

Doing that precludes the possibility of cannibalistic chains, so I'd recommend using "subtraction of RCDs". Also, I don't believe there is a need to "break down" the location of non-RCDs within the ALS cells. A follow-on locked candidate technique should pick up the same additional eliminations, if any.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby hobiwan » Mon Feb 23, 2009 5:28 pm

aran wrote:These aren't idle arguments as you might appear to suggest...in this context, the difference is relevant : even your solver was bamboozled by NL.

No it wasnt. The notation has nothing to do with the internal representation of a chain in my solver. In fact I use the exact same data structure for any type of chain, its only converted to a notation to be printed.

BTW the question itself had nothing to do with notation too. I simply tried to figure out which implications would be caused by an ALS node in a CNL/AIC loop (when implementing ALS in chains I skipped that and later forgot about it). Suggesting that the notation would have an influence on that would be the same as saying that printing a variable in hex instead of decimal would change the value of the variable itself.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby hobiwan » Mon Feb 23, 2009 5:30 pm

ronk wrote:Doing that precludes the possibility of cannibalistic chains, so I'd recommend using "subtraction of RCDs". Also, I don't believe there is a need to "break down" the location of non-RCDs within the ALS cells. A follow-on locked candidate technique should pick up the same additional eliminations, if any.

Plus my version was outright wrong (it would have eliminated 8 from r1c679):(
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Previous

Return to Advanced solving techniques