Debunking Discontinuous Nice Loops

Advanced methods and approaches for solving Sudoku puzzles

Debunking Discontinuous Nice Loops

Postby SudokuSwami » Wed Dec 20, 2017 5:22 pm

Debunking Discontinuous Nice Loops / Alternate Perspective

Hello All,

I am new to this forum, and for my first post, I would like to point out that in my humble opinion, what are known as Discontinuous Nice Loops, are mostly a waste of time.

There are better (and easier) ways to look at them.

The Hodoku Solving Guide offers the following link as a third-party tutorial on “Paul’s Pages” for what are known as “Nice Loops.”

https://paulspages.co.uk/sudokuxp/howto ... eloops.htm

Please allow me to refer to the diagrams in this tutorial, which will be much more convenient than trying to include my own diagrams here.

He says that there are three types of Discontinuous Loops; obviously Types 1, 2 & 3.

So, let’s take a look at his diagram for Type 1, where there is a Weak Link on both sides of candidate 1 in Cell R1C2. If you erase those two Weak Links, and instead, envision this chain as an AIC Type I, beginning on candidate 1 in R1C8, and ending on candidate 1 in R3C1, not only do you get to eliminate the candidate 1 in R1C2, but you ALSO get to eliminate the candidate 1 in R3C7 (!). This shows that the AIC Type I perspective can actually be more productive than the Discontinuous Loop perspective. There is really no need to look for the “discontinuity.”

Now let’s take a look at his diagram for Type 3. If you erase the Weak Link between the two candidate 7’s in R2C3 & R1C1, i.e., the final link back to the cell of discontinuity, then you are left with an AIC Type II which begins on candidate 5 in R1C1, and ends on candidate 7 in R2C3. In this case, the start digit cannot be true in the end cell, and the end digit cannot be true in the start cell. Thus, candidate 7 is eliminated from R1C1, which is the same result as the Discontinuous Loop. Again, there is no need to look for the DL.

However, Type 2 is the exception. DL Type 2 has a Strong Link on both sides of the same candidate in the “Cell of Discontinuity.” This is a very good and useful technique, as long as you can get your head around the peculiar concept that “If A is False, then A is True." This simply implies that there are no logical circumstances under which Candidate A can be False; because if you assume it is False, the Chain tells you that it is actually True.

The candidate with the two Strong Links will always be the solution to that Cell.

So, I guess what I am saying, is that in my opinion, Type 2 is a valid strategy, but Types 1 & 3, are unimportant, and only serve to complicate a simple situation.

Okay, there you have it.

Thanks for listening.

SS
Last edited by SudokuSwami on Sun Feb 24, 2019 2:01 am, edited 1 time in total.
SudokuSwami
 
Posts: 1
Joined: 04 November 2017

Re: Debunking Discontinuous Nice Loops

Postby eleven » Wed Dec 20, 2017 8:37 pm

Agreed. You can leave out Nice loops. AIC's do cover them (including loops).

And you don't need AIC's. Normal implication chains starting with a "not" also do the job. E.g. for your type 2 example:
not 8r4c2 => 8r6c2 => 6r6c8 => 2r5c8 => 2r4c5 => 8r4c2. So either 8 is in r4c2 or it is in r4c2, i.e. in any case.

But if you want to communicate with chains here, it's probably better to use AIC's.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: Debunking Discontinuous Nice Loops

Postby SpAce » Wed Dec 20, 2017 9:30 pm

I've been saying the same thing recently. I go one step further, however. You don't really need the Type 2 Discontinuous Loop either, because that's explained by the Hodoku AIC Type 1 also. In that case the two strongly linked ends just happen to be in the same cell and be the same candidate (kind of like a siamese twin), and that's why it burns all other candidates in that cell. That's how Hodoku seems to treat that case actually. So, all you really need is the two Hodoku AIC Types -- as long as you understand all of their special cases, including those covered by Nice Loops.

In practice I do use Paul's Discontinuous Nice Loop Type 2 because proving the verity is the simplest way to see what happens. I also use Continuous Nice Loops (which are the only thing that should be called Nice Loops, as far as I'm concerned). Discontinuous Nice Loops Type 1 and 3 are more or less useless, though they may help understand how eliminating AICs work, and can be used to find them and double-check them. (In practice I think it's easier to find a Discontinuous Nice Loop Type 3 -- which is probably the most common kind anyway -- than seeing the same as an AIC Type 2. It's also somewhat true for the Type 1 but not nearly as much. So in that sense they're not totally useless.)

SudokuSwami wrote:And while I am at it (ha ha), it seems to me that learning the so-called “Propagation Rules” for constructing Loops, is also a ridiculous waste of time, and way more confusing than just looking at the chains as alternating Strong and Weak Links.


Yep. The propagation rules are useless and do more harm than good, imho.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Debunking Discontinuous Nice Loops

Postby SpAce » Thu Dec 21, 2017 12:03 am

In my experience, the most useful piece of information on "Paul's Pages" is about finding productive nice loops, which also applies to the corresponding AICs (because if you find one, you have the other one too). For an inexperienced chain/loop builder this simple advice can be a surprisingly easy way to get started:

"Any square with two or more candidates can act as the start of a Nice Loop. The most commonly-occurring productive loop, however, is the Type 3 discontinuous (a weak and strong link with different values at the discontinuity). These loops typically begin with a strong link from the start square, so look for a square with three or more candidates (to give a better chance of a weak link back in to it), and a conjugate pairing with another square (i.e. the start and second square contain the only two occurrences if the link's candidate in the row, column or box they belong to)."
https://paulspages.co.uk/sudokuxp/howtosolve/niceloops.htm#finding

Finding those common eliminations is pretty easy and intuitive using discontinuous loops. Seeing them through AICs that have different digits at the ends? I'm not so sure about that.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Debunking Discontinuous Nice Loops

Postby pjb » Thu Dec 21, 2017 12:01 pm

I often wonder why we need to take different alternating inference chains and give them names. It would be very tiresome to list all of the names that are used. To my mind there are only 3 types:
1. The starting digit is false and the same digit at the end is true.
a. If the start and end digits don't see each other, then any same digit that sees both ends can be eliminated.
b. If the start and end digits do see each other, then we have a continuous loop with its own set of eliminations.
2. The starting digit is false and the same digit at the end is false, then if the start and end digits see each other, the end digit can be eliminated.

Situation 2 generally covers what we used to call discontinuous nice loops.
I know this is a very simplistic view, but whether there are 3, 4, or more links in the chain, they are all just AICs following the same rules.
Phil
pjb
2014 Supporter
 
Posts: 2554
Joined: 11 September 2011
Location: Sydney, Australia

Re: Debunking Discontinuous Nice Loops

Postby SpAce » Thu Dec 21, 2017 1:03 pm

pjb wrote:I often wonder why we need to take different alternating inference chains and give them names. It would be very tiresome to list all of the names that are used. To my mind there are only 3 types:
1. The starting digit is false and the same digit at the end is true.
a. If the start and end digits don't see each other, then any same digit that sees both ends can be eliminated.
b. If the start and end digits do see each other, then we have a continuous loop with its own set of eliminations.
2. The starting digit is false and the same digit at the end is false, then if the start and end digits see each other, the end digit can be eliminated.

Situation 2 generally covers what we used to call discontinuous nice loops.


What about Discontinuous Type 2 (the placing loop)? I think it's missing but you could add it as a special case of 1. Or the case when the ends have a different digit (Hodoku AIC Type 2 / Discontinuous Type 3)? On the other hand, isn't case 2 already covered by 1.a and thus redundant? Edit: On second thought, I think I was wrong here. Looks like all bases may be covered after all.

I still think the simplest practical set that covers all rules is this: Hodoku AIC Type 1 and 2, and Continuous Nice Loops.
Last edited by SpAce on Fri Dec 22, 2017 5:44 am, edited 1 time in total.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Debunking Discontinuous Nice Loops

Postby David P Bird » Thu Dec 21, 2017 1:56 pm

Over the years the ways we have devised for propelling missiles have evolved, from slings and trebuchets to automatic guns and cannons of various types. However, our military are very proud of their history and have various ways of honouring it with their archaic titles and ceremonies – so too in Sudoku. Just as we need scholars to decipher historic texts, so this will apply to the posts we write now with all our badly chosen terms and alternative names for much the same thing. For example while it might have been fun for a clique of players to devise a series of fancy names for each size of fish, all replacing numbers with names does is to make the subject more difficult for newcomers.

New recruits quickly spot these things but will invariably fail to get the rest of the regiment to fall in step with them, because the old guard won't allow it. However if the new recruits had their way they would just create another set of inconsistencies because, like the 'pioneers', they are unable to anticipate the effects of their suggestions further down the line.

Everyone agrees that A1 is more concise than r1c1 in a notation system, but no one wants to switch because of the effort it would cost them. The chess playing world had the same problem but eventually made the change in the 1960's. But we Sudoku players have no international body to help resolve such issues. We have to allow the language we use to evolve just as happens with most mother tongues. I have recognised this, and over the years have tried to gradually introduce better terms hoping that they would win popularity, but my success rate has been abysmally poor and I have only managed to infuriate some people.

Let's consider the Nice Loops vs AICs issue which is one of the biggest thorns in our side. It is some time since I studied Nice Loops but when I did, I discovered the underlying logic was precisely the same as AICs. Nice Loops had more rules to learn and a less reader-friendly notation system requiring more effort to error check. Furthermore, when it was defined there were only a limited number of patterns in use, but even so, it was awkward trying to insert a pattern Boolean into a Nice Loop notation. This has worsened so now we find players using Nice Loop terminology but pseudo Eureka (AIC) notations. To me that is equivalent to the sergeant major ordering 'shoulder muskets' when his troop is armed with automatic weapons.

At the same time, players have resisted using a standard notation and have spawned off their own. Often this makes it easier to describe the simple circumstances they are handling but incapable of being extended unambiguously to the more complex situations. Of course, this doesn't worry them because they never delve that deep. It is also ironic that when someone introduces a new way of notating something, firstly he spends more time answering queries than he has saved, and secondly, he loses those readers who can't be bothered to work out his intended meaning.

Programmers also have a preoccupation with keeping their notations as short as possible. They take out brackets identifying the digits, any passenger digits in ALS, and any white space. In my view, this makes them reader-hostile, for no good reason. The readers should outnumber the author (unless he is so obtuse that no one bothers) so they should be favoured. The space savings usually amount to nothing when every step has its own line. To verify a notation is sound, the reader must keep shifting focus between the notation and the grid, and all these abbreviations make that more difficult to do. (That'sthepointofhavingspaces.)

I had hoped that I wasn't the only person who was concerned about these issues and how detrimental they were in attracting new members to the forum, but sadly it seems I am.

DPB
.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Re: Debunking Discontinuous Nice Loops

Postby ghfick » Thu Dec 21, 2017 2:11 pm

David and Phil provide clarity here.

Perhaps it should be added that a chain can be bidirectional or unidirectional. David [and others] would say a bidirectional chain is an example of a 'non-assumptive' method. Unidirectional chains are examples of assumptive methods. It may be worth noting as well that chains can have nodes of various sorts of patterns including ALSs, JEs [Junior Exocets], X-Wings...

There are various non-assumptive methods that are not chains. JEs, MSLSs [Multi Sector Locked Sets] and SK Loops are examples [at least I think they are not chains!]

I have a [rather thick] folder of puzzles that have partial solution paths. Most of the time, I prefer to leave a puzzle unsolved rather than use assumptive methods. I do sometimes include paths with interesting assumptive methods though. This 'project' is about detailing the facets of interesting puzzles.

I am now a solid proponent of the Eureka notation for chains. David's writings have convinced me. Phil's solver shows that ALS-XZ and ALS-XY moves can be very nicely written as chains using Eureka.

Gordon
ghfick
 
Posts: 232
Joined: 06 April 2016
Location: Calgary, Alberta, Canada youtube.com/@gordonfick

Re: Debunking Discontinuous Nice Loops

Postby eleven » Thu Dec 21, 2017 6:45 pm

Things don't become more true, if they are repeated 1000 times. There is no logical difference between bidirectional and - what you call - unidirectional chains. Any unidirectional chain can be reformulated as a bidirectional one, as well as any proof by contradiction can be reformulated without showing a contradiction (but it may be harder to read).
Concerning the much-maligned assumptions it is just a lie, that finding bidirectional chains needs less assumptions than finding unidirectional chains. The latter is just the same, but leaving out unnecessary things. You do have to assume a starting link, say (a=b). That's identical to assume, that b is true (or a in the other direction), let's see, what we can get of it. Forgive me the word, but it is hypocrisy to claim, that this is less assumptive, less guessing, cleaner, better or what else.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: Debunking Discontinuous Nice Loops

Postby SpAce » Thu Dec 21, 2017 7:40 pm

eleven wrote:Things don't become more true, if they are repeated 1000 times.


Hear hear.

There is no logical difference between bidirectional and - what you call - unidirectional chains. Any unidirectional chain can be reformulated as a bidirectional one, as well as any proof by contradiction can be reformulated without showing a contradiction (but it may be harder to read).


While I hope you're right, I have to ask something about that claim because I remembered seeing something from a reputable source that seemed to disagree. Now I found the source: http://hodoku.sourceforge.net/en/tech_als.php#ach. It says:

"Some explanations of ALS Chains (often called "ALS-XY-Chains") depend on the reversability of the chain. As a matter of fact, however, some more complicated chains with doubly linked ALS are not reversible."

It also links to this discussion: http://forum.enjoysudoku.com/restricted-common-adjacency-rules-t6642.html with this comment:

"Some of the combinations of RCs produce non reversible chains. As PIsaacson already noted this is irrelevant in case of "normal" ALS chains but it is relevant for Continuous ALS Loops."

I personally have no skills to judge whether that claim is true or not, or whether it's relevant here. Just saying that it seems to contradict what you said, but even then, only in a very specific situation.

Concerning the much-maligned assumptions it is just a lie, that finding bidirectional chains needs less assumptions than finding unidirectional chains. The latter is just the same, but leaving out unnecessary things. You do have to assume a starting link, say (a=b). That's identical to assume, that b is true (or a in the other direction), let's see, what we can get of it. Forgive me the word, but it is hypocrisy to claim, that this is less assumptive, less guessing, cleaner, better or what else.


Agree. While I'm happy to let everyone choose or restrict their solving methods any way they like and for any reasons they like, I don't see a reason why any artificially restricted sets should be universally accepted as the only clean or valid solving techniques. As far as I'm concerned, anything that is logical, repeatable, explainable, guaranteed to produce correct results, and preferably practical and fun to use by a human solver, is a valid technique. Most other rules seem a bit religious to me, but like I said, anyone is free to choose their own religion (as long as they don't push it on others as the only truth).
Last edited by SpAce on Fri Dec 22, 2017 3:24 am, edited 1 time in total.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Debunking Discontinuous Nice Loops

Postby eleven » Thu Dec 21, 2017 8:15 pm

SpAce wrote:"Some explanations of ALS Chains (often called "ALS-XY-Chains") depend on the reversability of the chain. As a matter of fact, however, some more complicated chains with doubly linked ALS are not reversible."

It also links to this discussion: http://forum.enjoysudoku.com/restricted-common-adjacency-rules-t6642.html with this comment:

"Some of the combinations of RCs produce non reversible chains. As PIsaacson already noted this is irrelevant in case of "normal" ALS chains but it is relevant for Continuous ALS Loops."

PIsaacson is a convert of Denis Berthier, as he notes. Denis' nrczt chains are in fact not reversible directly. The reason is, that the next link not only is dependent from the last one, but also former ones (the chains are "remembering" digits).

Concerning the comment on the hodoku site, note arans post.
aran wrote:Hobiwan : there is no such thing as an irreversible chain...(well I can't imagine one)...on the other hand chains that involve grouped nodes of any sort including memory which is the simplest sort, reverse as nets.

That's it. In those cases the reverse chain needs to be split. We know this from the troubles to formulate some AIC's correctly, also if one direction seems to be easy to follow.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: Debunking Discontinuous Nice Loops

Postby ghfick » Thu Dec 21, 2017 8:57 pm

I might agree that some chains might appear unidirectional but have a reverse direction based on different memories. It is not clear to me that the reverse is always possible.

How about Kraken Units? How about Kraken Fish with more than one fin? Are they not unidirectional? If such can be viewed as bidirectional, please correct this view by providing how such reverse routes would work. With these moves, the explicit branching is in play.

Gordon
ghfick
 
Posts: 232
Joined: 06 April 2016
Location: Calgary, Alberta, Canada youtube.com/@gordonfick

Re: Debunking Discontinuous Nice Loops

Postby SpAce » Thu Dec 21, 2017 9:23 pm

eleven wrote:PIsaacson is a convert of Denis Berthier, as he notes. Denis' nrczt chains are in fact not reversible directly. The reason is, that the next link not only is dependent from the last one, but also former ones (the chains are "remembering" digits).


That explains.

Concerning the comment on the hodoku site, note arans post.
aran wrote:Hobiwan : there is no such thing as an irreversible chain...(well I can't imagine one)...on the other hand chains that involve grouped nodes of any sort including memory which is the simplest sort, reverse as nets.

That's it. In those cases the reverse chain needs to be split. We know this from the troubles to formulate some AIC's correctly, also if one direction seems to be easy to follow.


I see. I was thinking along the same lines as hobiwan: "Reversibility: In my very simple minded view on reversibility I try to follow the chain from end to start using the exact same logic just in reverse order." I guess it doesn't have to be that restricted.

Glad we got this covered!
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Debunking Discontinuous Nice Loops

Postby SpAce » Thu Dec 21, 2017 9:29 pm

David, I agree with almost everything you said. A couple of comments:

David P Bird wrote:Everyone agrees that A1 is more concise than r1c1 in a notation system, but no one wants to switch because of the effort it would cost them.


I wouldn't want that change for a couple of other reasons. The biggest one is that the letters require a translation step, especially if certain letters are skipped as has been suggested. Without knowing the letter assignments beforehand, it's no longer immediately clear what rows are being referred to (or if it's a row in the first place). The r1c1 coordinates are immediately readable without any prior knowledge and alphabetical counting. I much prefer it the way it is. If I have to read chains using the A1 notation, I have to see the grid at the same time and it still takes more effort.

Edit: I reconsidered my position a little bit. I guess the translation problems would be transitory, and the A1 system would probably work fine for a 9x9 (or smaller) grid once gotten used to. That may be all that matters to us, yet I always prefer systems that scale (even if the need is not immediately obvious). How would A1 work for 16x16 grids for example? Many of those use letters A-G for numbers 10-16. If the same letters would also mean row numbers 1-7, that would be extremely confusing. On the other hand, r1c1 would work fine. I understand that the relevance of this argument is questionable at best, but anyway.

Programmers also have a preoccupation with keeping their notations as short as possible. They take out brackets identifying the digits, any passenger digits in ALS, and any white space. In my view, this makes them reader-hostile, for no good reason. The readers should outnumber the author (unless he is so obtuse that no one bothers) so they should be favoured. The space savings usually amount to nothing when every step has its own line. To verify a notation is sound, the reader must keep shifting focus between the notation and the grid, and all these abbreviations make that more difficult to do. (That'sthepointofhavingspaces.)


I agree, although I don't know why that would be a programmer issue (even if it is), as it's easy to have your a program to output any kind of notation. It's more understandable to use shortcuts when manually typing chains. I personally aim for the maximum readability, but it's not always clear what is the most readable form because it also depends on the reader (and there seems to be quite a few preferred styles here). Whitespace helps to separate logical groupings but even that can be used too much, as an experienced reader can see the big picture in a concise text much faster. Of the specific things you mentioned I miss the ALS passenger digits most. (Last but not least, I've never had any trouble reading your chains or texts so I wouldn't mind having that as a standard.)
Last edited by SpAce on Fri Dec 22, 2017 3:50 am, edited 1 time in total.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: Debunking Discontinuous Nice Loops

Postby StrmCkr » Thu Dec 21, 2017 10:17 pm

Gordon it depends on how the "krakens" are construed

see this thread

and here
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Next

Return to Advanced solving techniques

cron