Nice Loops for beginner

Advanced methods and approaches for solving Sudoku puzzles

Nice Loops for beginner

Postby Kent » Wed Mar 15, 2006 6:38 am

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
 
Posts: 98
Joined: 28 February 2006

Re: Nice Loops for beginner

Postby ronk » Wed Mar 15, 2006 12:35 pm

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
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Wed Mar 15, 2006 2:22 pm

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.
Last edited by ravel on Thu Mar 16, 2006 9:51 am, edited 2 times in total.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Mike Barker » Thu Mar 16, 2006 12:15 am

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.
Last edited by Mike Barker on Wed Dec 19, 2007 9:57 pm, edited 5 times in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Kent » Thu Mar 16, 2006 9:53 am

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.
Kent
 
Posts: 98
Joined: 28 February 2006

Postby ravel » Thu Mar 16, 2006 10:47 am

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.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Jeff » Thu Mar 16, 2006 1:04 pm

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

Well done Mike, That's spot on.:D How is your programming of nice loops?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Mar 16, 2006 1:19 pm

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
 
Posts: 708
Joined: 01 August 2005

Postby Kent » Fri Mar 17, 2006 3:42 pm

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
Kent
 
Posts: 98
Joined: 28 February 2006

Postby Kent » Fri Mar 17, 2006 3:54 pm

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
 
Posts: 98
Joined: 28 February 2006

Postby Jeff » Fri Mar 17, 2006 4:17 pm

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.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Mar 17, 2006 4:34 pm

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
 
Posts: 708
Joined: 01 August 2005

Postby Kent » Fri Mar 17, 2006 5:55 pm

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
 
Posts: 98
Joined: 28 February 2006

Postby Jeff » Fri Mar 17, 2006 6:18 pm

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.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Fri Mar 17, 2006 7:05 pm

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.
tso
 
Posts: 798
Joined: 22 June 2005


Return to Advanced solving techniques

cron