Question on Nice Loops

Advanced methods and approaches for solving Sudoku puzzles

Question on Nice Loops

Postby susume » Mon Aug 04, 2008 2:18 am

I have seen it written that a strong link can be used as a weak link in a nice loop. Am I right in believing this is only true if the ends of the strong link are in the same unit? If I prove a strong link on some digit between cells that can't see each other, don't I also have to prove a weak link there before I use it as a weak link?

And is there a standard notation for strong links that can't be used as weak links?

Thanks for any light you can shed.
Susume
susume
 
Posts: 19
Joined: 03 August 2008

Postby Luke » Mon Aug 04, 2008 3:52 am

PaulsPages has a super clear explanation of strong and weak inferences and nice loop notation, IMO. Click here.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby Pat » Mon Aug 04, 2008 7:41 am

susume wrote:I have seen it written that a strong link can be used as a weak link in a nice loop.

Am I right in believing this is only true if the ends of the strong link are in the same unit?

If I prove a strong link on some digit between cells that can't see each other,
don't I also have to prove a weak link there before I use it as a weak link?



wherever you need at least a "weak link",
surely you can use a "strong link"
    ( a "strong link" is stronger than a "weak link" )
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby susume » Tue Aug 05, 2008 6:14 pm

Thanks, Luke, that's where I learned the most about nice loops. It only deals with links whose endpoints are in the same row, column, or box. Jeff Loeb's definition of nice loops even specifies that the endpoints be in the same unit.

You can prove and then use links whose endpoints are not in one unit, i.e. they can't see each other. I was asking confirmation that the ability to use a strong link as a weak one does not apply in these cases - I found confirmation here.

Pat, it is not as simple as being "stronger" - "at least one must be true" is stronger than "no more than one can be true", but does not necessarily imply it. Inside a unit the rule of sudoku assures no more than one placement of a digit is true, but going across units there is no guarantee.

Thanks for your responses.
susume
susume
 
Posts: 19
Joined: 03 August 2008

Postby Pat » Wed Aug 06, 2008 8:25 am

susume wrote:Thanks, Luke, that's where I learned the most about nice loops.
It only deals with links whose endpoints are in the same row, column, or box.
Jeff Loeb's definition of nice loops even specifies that the endpoints be in the same unit.


exactly! Jeff (2006) defines a "link" only within a unit; and the "strong link" is stronger than the "weak link" -- "has a strong inference as well as a weak inference" -- precisely because the definition already included the requirement of being within a unit -- which i'm sure you understood even before posting your question.


susume wrote:You can prove and then use links whose endpoints are not in one unit, i.e. they can't see each other. I was asking confirmation that the ability to use a strong link as a weak one does not apply in these cases - I found confirmation here.


so you're trying to re-use the term "link" for something else -- "links whose endpoints are not in one unit, i.e. they can't see each other" -- and then you're surprised (?) that they are not "links", that they cannot be used the way "links" are used.


susume wrote:Pat, it is not as simple as being "stronger" - "at least one must be true" is stronger than "no more than one can be true", but does not necessarily imply it.


none of those 2 is stronger than the other --
    x OR y
    NOT (x AND y)
here the first is stronger than the 2nd (implies the 2nd) --
    x XOR y
    NOT (x AND y)
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby Jean-Christophe » Wed Aug 06, 2008 6:50 pm

Pat wrote:exactly! Jeff (2006) defines a "link" only within a unit; and the "strong link" is stronger than the "weak link" -- "has a strong inference as well as a weak inference" -- precisely because the definition already included the requirement of being within a unit -- which i'm sure you understood even before posting your question.


This is correct only for the simple strong links, but grouped strong links are not always weak links. See AIC by Myth Jellies and Grouped nice loop by Jeff.
This empty rectangle as a simple example:
Code: Select all
+-------+-------+-------+
| 1 1 1 | . 1 . | . . . |
| / / 1 | . / . | . . . |
| / / 1 | . / . | . . . |
+-------+-------+-------+
| . . . | . / . | . . . |
| . .-1 | . 1 . | . . . |
| . . . | . / . | . . . |
+-------+-------+-------+
| . . . | . / . | . . . |
| . . . | . / . | . . . |
| . . . | . / . | . . . |
+-------+-------+-------+
[r5c3]-1-[r123c3]=1=[r1c123]-1-[r1c5]=1=[r5c5]-1-[r5c3] => r5c3<>1

[r123c3]=1=[r1c123] forms a grouped strong link within the same unit (B1):
[r123c3]<>1 => [r1c123]=1; [r1c123]<>1 => [r123c3]=1

But this is NOT a weak link:
[r123c3]=1 => [r1c123]<>1 IS WRONG since they share r1c3, both premices may be true when r1c3=1

This is what Myth Jellies calls Inverse Link, Converse Link, Strong-Only Link.

This similar pattern drives you nowhere. Since r1c3 can be 1, there is NO weak link between [r123c3] and [r1c123]
+-------+-------+-------+
| 1 1 1 | / 1 / | / / / |
| / / 1 | . . . | . . . |
| / / 1 | . . . | . . . |
+-------+-------+-------+
| . . / | . . . | . . . |
| . . 1 | . ? . | . . . |
| . . / | . . . | . . . |
+-------+-------+-------+
| . . / | . . . | . . . |
| . . / | . . . | . . . |
| . . / | . . . | . . . |
+-------+-------+-------+
[r5c5]-1-[r5c3]=1=[r123c3]=1=[r1c123]=1=[r1c5]-1-[r5c5] => nothing

For this pattern to work, r1c3 cannot be 1:
+-------+-------+-------+
| 1 1 / | / 1 / | / / / |
| . . 1 | . . . | . . . |
| . . 1 | . . . | . . . |
+-------+-------+-------+
| . . / | . . . | . . . |
| . . 1 | .-1 . | . . . |
| . . / | . . . | . . . |
+-------+-------+-------+
| . . / | . . . | . . . |
| . . / | . . . | . . . |
| . . / | . . . | . . . |
+-------+-------+-------+
[r5c5]-1-[r5c3]=1=[r23c3]-1-[r1c12]=1=[r1c5]-1-[r5c5] => r5c5<>1

This could be called Grouped Two String Kite


Pat wrote:
susume wrote:You can prove and then use links whose endpoints are not in one unit, i.e. they can't see each other. I was asking confirmation that the ability to use a strong link as a weak one does not apply in these cases - I found confirmation here.

so you're trying to re-use the term "link" for something else -- "links whose endpoints are not in one unit, i.e. they can't see each other" -- and then you're surprised (?) that they are not "links", that they cannot be used the way "links" are used.

Yes they can. This is exactly the same case as the empty rectangle above. There is strong inference between the two endpoints, but NO weak inference (IOW both endpoints may be true). Nevertheless, this strong chain can itself be weakly linked to another strong link (or chain).
Jean-Christophe
 
Posts: 149
Joined: 22 January 2006

Postby ronk » Wed Aug 06, 2008 9:39 pm

The terms strong inference and weak inference were coined by Jeff precisely because the term strong link meant different things to different people. Personally, I've avoided the term strong link ever since.

The term link is used by almost everyone for two candidates that directly see each other. IOW the candidates share a unit.

Steve K (Kurzhals) is one of several that use the term derived strong (or weak) inference between candidates that indirectly see each other. I'm following his lead in this.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Glyn » Wed Aug 06, 2008 10:30 pm

It's always good to see this subject reprised. I believe JC's interest stemmed from his initial exploration into chains in the context of Killer Sudoku. The subject of what to call these derived inferences was discussed briefly in Ruud's forum as a means of approaching some of the 'Unsolvable' Assassins.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby Pat » Thu Aug 07, 2008 1:09 pm

Jean-Christophe wrote:
Pat wrote:
susume wrote:Jeff Loeb's definition of nice loops even specifies that the endpoints be in the same unit.


exactly! Jeff (2006) defines a "link" only within a unit; and the "strong link" is stronger than the "weak link" -- "has a strong inference as well as a weak inference"


This is correct only for the simple strong links, but grouped strong links are not always weak links


sorry!! i was quoting from Jeff's definitions in "Forcing chains: Terminology and Definition" -- i should've stopped to think a little---
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby Pat » Thu Aug 07, 2008 1:11 pm

    i had spoken of "links" because that was the original question --
    many thanks to ronk for the warning about the "link" terminology!!

    looking at the "inference" terminology,
    none of these 2 is stronger than the other (none of them implies the other) --
    • x OR y -- "strong inference"
    • NOT (x AND y) -- "weak inference"
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby DonM » Thu Aug 07, 2008 3:07 pm

Susume: Jeff Loeb's definition of nice loops even specifies that the endpoints be in the same unit.

Point of order here: The Sudoku pioneer, Jeff, of nice loops (and other) fame is not Jeff Loeb!
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby susume » Thu Aug 07, 2008 10:30 pm

My bad in mis-attributing -- have not been around here long and get easily muddled with names. I should have double checked.

Pat, I somehow assumed OR was called stronger than NAND in the sudoku context because there are many more eliminations in sudoku than placements, so finding "at least one true" seems like more information to me than finding "zero to one true." Now if you think me an idiot it will at least be for an accurate reason.

Thanks all for your helpful replies. Now I need to go learn more about group nice loops and AIC.... Will try to quit using that nefarious term link....
susume
 
Posts: 19
Joined: 03 August 2008


Return to Advanced solving techniques