Sudoku Players' Forum (clone)

I've read some threads about nice loops and I dont really get the real idea of the principles that is involved in it.Can someone please give me a simple illustration?? How and when u say it's nice loop?

Kent wrote:I've read some threads about nice loops and I dont really get the real idea of the principles that is involved in it.Can someone please give me a simple illustration?? How and when u say it's nice loop?

Although debatable, IMO your request for help belongs on the help forum.

Ron

I want to give you a start (though i am not really authorized, because i am no nice loop expert, but this might be an advantage in this case). Lets have a look at tso's response to your NeedHelp!!!! post:

Code: Select all

 *-----------------------------------------------------------*
 | 389   389   138   | 2     145   45    | 6     58    7     |
 | 7     2     18    | 6     15    3     | 9     4     58    |
 | 5     6     4     | 8     7     9     | 3     2     1     |
 |-------------------+-------------------+-------------------|
 | 2     39    6     | 3459  458   7     | 1     38    348   |
 | 349   1     5     | 349   48    6     | 2     7     348   |
 | 348   7     38    | 34    2     1     | 5     6     9     |
 |-------------------+-------------------+-------------------|
 | 38    38    2     | 45    9     45    | 7     1     6     |
 | 6     5     7     | 1     3     8     | 4     9     2     |
 | 1     4     9     | 7     6     2     | 8     35    35    |
 *-----------------------------------------------------------*


The simplest form of a nice loop starts with a candidate in one cell, goes to the next cell stating that there has to be another candidate then and so on, until it comes back to the starting cell with a different candidate. That means, you can eliminate the original candidate. tso's sample gives you a lot of nice loops, e.g.:
[Edit - thanks to Kent]
[r1c3]-8-[r6c3]-3-[r6c4]-4-[r7c4]-5-[r7c6]-4-[r1c6]-5-[r2c5]-1-[r2c3]-8-[r1c3]
You can read it like this:
if r1c3=8 then r6c3<>8 but =3, then r6c4<>3, but 4 ....then r2c3=8, then r1c3<>8

Now the more complicated second loop (we do it here without elimination from the first one):
[r4c8]=8=[r1c8]-8-[r1c123]=8=[r2c3]-8-[r6c3]-3-[r6c4](-4-[r4c4])-4-[r7c4]-5-[r4c2|r4c4]-3-[r4c8]
This means: if r4c8<>8 (must be 3 then), then r1c8=8 and none of r1c1,r1c2,r1c3 = 8, therefore r2c3=8, r6c3=3, r6c4=4 and r7c4=5.
But then for r4c4 only remain candidates 39 and we have a 39-pair in r4c2 and r4c4, so one of the cells must contain 3 and r4c8 must be 8, a contradiction.
You will need the A=x=B notation, when you use conjugated pairs (if cell A is not x then B must be x).
Note that in this case the step that led to the pair, needed both steps before (to eliminate 4 and 5).This is called a loop with multiple inference.
If you look at Carculs response in your thread, you can see, that it is also possible, that you do not go back to the starting cell (discontinous loop), but e.g. eliminate all candidates of a cell on the way. Also you can use (almost) triples, x-wings, URs and others on your way.

I don't know if you've seen the collection of topics on Nice Loops. Jeff just provided an update which you can see here. He has been helping me with nice loops. Lets see if I've learned enough to be dangerous or helpful...

Many eliminations in Sudoku are based on identification of patterns, such as an X-wing or an XY-wing, which consist of nodes (cells or groups of cells) and links (relationships between these nodes). Patterns which consist of nodes with only two links per node are double implication loops. These "nice" loops are composed of Grouped Strong Links (GSLs), described here and here and Almost Locked Sets (ALSs) with one extra candidate, described here and here. In the simplest case GSLs consist of conjugate pairs (units with only two instances of a candidate - a strong link); while ALSs consist of bivalued cells (cells with only two candidates). A nice loop which consists only of GSLs with a single candidate are referred to as a grouped X-cycle such as a finned X-wing or a grouped Turbot Fish. Examples of nice loops which consist only of ALSs are XY-wings and XYZ-wings. Combination loops also exist.

Nice loops can be constructed using the rules given here. The process involves identification of GSLs and ALSs which can be linked together as follows:

1) Draw solid lines with +ve labels to connect nodes of a GSL.
2) Draw broken lines with -ve labels to connect:
----- a) ALSs sharing the same candidate
----- b) an ALS to a node of a GSL sharing the same candidate or vice versa
----- c) disjoint GSLs sharing the same candidate (true even if a solid line could be drawn).
3) To link from one GSL to another GSL with a common node (solid line to a solid line), the labels must be different and the common node must be a single cell.
4) To link from one ALS to another ALS (broken line to broken line), the labels must be different. (typical xy-chain propagation)
5) To link from a node of a GSL to an ALS (solid line to broken line) or vice versa, the labels must be same but opposite in signs.
6) To link from one node of a GSL to a node of a second disjoint GSL (solid line to broken line to solid line), the labels of the GSLs must be the same and the label of the broken line is opposite in sign. (typical x-cycle propagation)

If a loop (the start node equals the end node) can be formed based on these rules, a continuous nice loop is formed and eliminations can be performed using Theorems 1 and 2:

Theorem 1. If a node between two solid lines belongs to a continuous nice loop and is a single cell, then the node can only be filled with one of the two digits that label the links; thus other candidates in the node can be eliminated.
Theorem 2. If a broken line between two nodes belongs to a continuous nice loop, then the digit labeling it must be placed at one of the 2 nodes; thus this digit can be eliminated from any other cells that sees both nodes. In addition, if a node where two broken lines meet belongs to a continuous nice loop, then any digit which is part of the node and not labeling one of the lines must belong to the node; thus these digit(s), if any, can be eliminated from any other cells that see the node.

If during the identification of a loop, the start and end nodes share a unit, but a link can not be made between them, pseudo links (possibly two) are created between them. These are broken lines with a label equal to minus the positive label if coming from a GSL or a negative label not equal to the one already linking the ALS if coming from an ALS. This is a discontinuous nice loop and Theorem 5 can be used to perform eliminations in the start and end nodes based on the label of the link going to the node:

Theorem 5. At the discontinuity of a nice loop where a solid line and a broken line meet, the digit that labels the broken line can be eliminated from the node between the links if that node is a single cell.

If during the identification of a loop, the start and end nodes don't share a unit, but pseudo links with the same label can be constructed between each node and other cell(s), then by Theorem 4 eliminations can be performed at these cells based the label of the links going to the cell:

Theorem 4. At the discontinuity of a nice loop where two broken lines with the same labels meet, the digit that labels the links can be eliminated from the node between the links.

This is also a discontinuous nice loop. With these rules all(?) grouped X-cycles, XY-cycles (seems like a good name for nice loops composed of ALSs with one extra candidate), as well as other GSL-cycles and combination cycles can be identified and eliminations performed. Hope this helps. Refer to the collection of solving techniques to get the straight story. This is my interpretation and, if history holds, contains at least one error.

ravel

But then for r3c4 only remain candidates 39

r3c4 is an 8.Why do you mention it's 39.I dont get it

then r6c3<>1, but 3 ....then r2c3=8, then r1c3<>8

r6c3 has only 3 and 8 as cendidates.There's no candidate 1.I don't get it.is it an error or too hard for me.

Hi Kent,

please excuse my sloppy post.

The first chain should start with:
[r1c3]-8-[r6c3]-3- (if r1c3=8 then r6c3<>8 but 3)
instead of
[r1c3]-8-[r2c3]-1-[r6c3]-3-

".. for r3c4 only remain candidates 39 .." is a typo, it should read r4c4

Thanks for pointing that out, i will correct it.

Mike Barker wrote:This is my interpretation and, if history holds, contains at least one error.

Well done Mike, That's spot on. How is your programming of nice loops?

Hi Kent,

I think you should study x-cycles and xy-chains first, as each of their nodes only contains one cell. Pay attention with strong and weak inferences as you follow the loop around in accordance with the nice loop propagation rules. Do concentrate on discontinuous loop and then continuous nice loops. Then, ask specific questions where possible.

Good luck

Jeff

Pay attention with strong and weak inferences as you follow the loop around in accordance with the nice loop propagation rules. Do concentrate on discontinuous loop and then continuous nice loops. Then, ask specific questions where possible

Thanks for the advice.I already know about x-wing and xy-wing.But when i tried on some puzzles, they can't be solved by it.Does that mean I have to know all the advanced strategies before I attempt a hard puzzle.After X-wing and XY-wing what do u recommend next? Really need some advice

whats a difference between a loop and forced chain?? Does a force chain form a loop?
Whats the difference between a discontinuous loop and nice loop?

Kent wrote:.I already know about x-wing and xy-wing.But when i tried on some puzzles, they can't be solved by it.Does that mean I have to know all the advanced strategies before I attempt a hard puzzle.After X-wing and XY-wing what do u recommend next? Really need some advice

There are so many techniques after x-wing and xy-wing. For example: swordfish, single-digit colouring, x-cycle, xy-chain, xyz-wing, turbot fish, almost locked set xz rule, etc. Amongst which, x-cycle and xy-chain are subsets of nice loops.

Kent wrote:whats a difference between a loop and forced chain?? Does a force chain form a loop?
Whats the difference between a discontinuous loop and nice loop?

Nice loops and forcing chains are closely related. A nice loop can be a forcing chain, a forcing net or a SIN. Each forcing chain does form a nice loop. For example, each simple nice loop is a double implication forcing chain.

A nice loop can be continuous or discontinuous:

Continuous Loop
A nice loop with inferences that obey the nice loop propagation rules continuously in a cyclic manner, eg x-wing.

Discontinuous Loop
A nice loop with inferences that obey the nice loop propagation rules except at a discontinuity where the deduction is made, eg. xy-wing.

Jeff

Pay attention with strong and weak inferences

What do you mean by strong and weak inferences?? I heard people saying it before inthe forum but I can't get it

Kent wrote:What do you mean by strong and weak inferences?? I heard people saying it before inthe forum but I can't get it

Kent, These terms and many more related to forcing chains and nice loops are described here.

Kent wrote:I already know about x-wing and xy-wing.But when i tried on some puzzles, they can't be solved by it.Does that mean I have to know all the advanced strategies before I attempt a hard puzzle.After X-wing and XY-wing what do u recommend next? Really need some advice

Nearly all the birds in my area are pigeons and seagulls. I've learned to identify two dozen other birds -- that doesn't change the fact that most of the birds I see are pigeons and seagulls. I can look for a cockatoo al day long ... unless I go to the zoo, I'm not gonna find one.

You don't need advice. You just need to keep learning. Sudoku isn't the hardest thing in the world -- but you can't expect to learn everything in half an hour either. I would wager that if you read *every* thing that has been posted in the advanced strategies forum and worked through all the examples, even though you woudn't understand it all -- I certainly don't -- by the time you were done, you'd be giving advice instead of asking.