Nice loops for advanced level players - b/b plot

Advanced methods and approaches for solving Sudoku puzzles

Postby Mike Barker » Thu Mar 23, 2006 3:05 pm

I probably should have said "as written". Would it make sense to update Th. 1 and 5 as follows:
    Theorem 1. If a node between two solid lines belongs to a continuous nice loop and contains only one cell, then the node can only be filled with one of the two digits that label the links; thus other candidates in the cell can be eliminated.
    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 contains only one cell.
As I stated previously there may be more games to play with Th. 1 with a grouped node, ie treat it as a quantum cell, but I haven't thought this all the way through.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Jeff » Thu Mar 23, 2006 3:53 pm

Mike Barker wrote:Would it make sense to update Th. 1 and 5 .....

Sounds right, Mike.:D What do you think, Carcul?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Thu Mar 23, 2006 7:20 pm

Hi Jeff.

I think that doesn't make sense to make those updates:

Mike Barker wrote:Theorem 1. If a node between two solid lines belongs to a continuous nice loop and contains only one cell, then the node can only be filled with one of the two digits that label the links; thus other candidates in the cell can be eliminated.


A node with more than one cell can only be between two solid lines if both solid lines have the same label "x", in which case all others "x" candidates can be eliminated from the unit common to the cells belonging to the node. We can never make eliminations in the cells A, B,... in a grouped strong link of the type [A|B|...]=x=[C]. So I don't think that is needed to state that the node contains only one cell, because if the two strong links have different labels then the node must necessarily have only one cell.

Mike Barker wrote: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 contains only one cell.


Again, this update is not needed because we can only have a node with more than one cell between a strong link and a weak link if the labels of both links are equal: having a node between a solid line and a broken line with different labels implies necessarily that the node have only one cell, otherwise it would make no sense.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Fri Mar 24, 2006 6:24 am

Carcul wrote:A node with more than one cell can only be between two solid lines if both solid lines have the same label "x", in which case all others "x" candidates can be eliminated from the unit common to the cells belonging to the node. We can never make eliminations in the cells A, B,... in a grouped strong link of the type [A|B|...]=x=[C].

Very true. This case is theorem 3 and the loop can be expressed as:

[A|B|C]=x=[........]=x=[A|B|C] => either A=x or B=x or C=x

Carcul wrote:So I don't think that is needed to state that the node contains only one cell, because if the two strong links have different labels then the node must necessarily have only one cell.

In other words, the continuous loop "=[A|B|C]=x=[........]=y=[A|B|C]=" won't happen, therefore there is no need to specify that the node must contain only one cell.

Carcul wrote:.....having a node between a solid line and a broken line with different labels implies necessarily that the node have only one cell, otherwise it would make no sense.

Case 1:
[A|B|C]=x=[........]-y-[A] => no conclusion

Case 2:
[A|B|C]-x-[........]=y=[A] => A<>x, this is equivalent to:
[A]-x-[........]=y=[A] => A<>x

Even though Case 2 could happen, the same elimination will be picked up without the node being grouped. Therefore, there is no need to specify that the node must contain only one cell.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sat Mar 25, 2006 9:49 pm

This is a continuous simple nice loop, thanks to Absolute Beginner who posted it under another thread. I couldn't resist recording it here as it is the longest pure strong inference chain that I have ever seen.

Image

Nice loop notation:
=[r9c5]=2=[r9c8]=8=[r1c8]=2=[r1c7]=5=[r3c7]=8=[r3c4]=9=[r3c6]=3=[r1c6]=6=[r1c4]=4=[r1c5]=1=[r9c5]=
implies r9c5<>8, r1c7<>8, r1c4<>8, r1c5<>8
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby absolute beginner » Wed Mar 29, 2006 6:16 pm

Hi Jeff,
just for the show-effect,
instead of ...=[r1c7]=5=[r3c7]=...
you could even prolonge the chain with
...=[r1c7]=5=[r1c3]=3=[r3c3]=5=[r3c7]=...
but that's just from the chapter
"my chain is longer than your chain" ;-)
absolute beginner
 
Posts: 22
Joined: 26 February 2006

Chain Solution

Postby doduff » Mon May 29, 2006 9:22 pm

I know this is an old post, but I felt like putting in my bit also.

Here is the list of loops that I found to solve the exercise puzzle:

1. [r3c7]-8-[r1c8]=8=[r4c8]-8-[r5c7]=8=[r3c7] => [r1c7]<>8 (Continuous loop)

2. [r7c3]-1-[r7c7]=1=[r9c7]-1-[r2c2]=1=[r6c2]-1-[r6c9]-9-[r5c7]=9=[r1c7]=7=[r3c7]-7-[r3c6]-4-[r3c3]-1-[r7c3] => [r7c3]<>1,

[r7c7]=1, [r9c7]=2, [r9c56]<>2

3. [r3c4]=3=[r5c4]-3-[r4c5]=3=[r4c9]=6=[r4c8]=8=[r4c1]-8-[r5c1]=8=[r5c7]-8-[r3c7]-7-[r3c4] => [r3c4]<>7

4. [r3c4]-4-[r5c4]-3-[r5c9]=3=[r4c9]=6=[r4c8]-6-[r1c8]-8-[r3c7]-7-[r3c6]-4-[r3c4] => [r3c4]<>4

5. [r7c6]=2=[r7c5]-2-[r4c5]-3-[r4c9]-6-[r4c8]-8-[r5c7]=8=[r3c7]=7=[r3c6]-7-[r9c6]-9-[r7c6] => [r7c6]<>9, [r7c6]=2, [r7c5]<>2

6. [r5c5]=2=[r4c5]-2-[r4c1]-8-[r4c8]=8=[r5c7]-8-[r3c7]-7-[r3c6]-4-[r5c6]-5-[r5c5] => [r5c5]<>5, {r5c6]=5, [r1c6]<>5,

[r3c5]<>3, [r3c4]=3, [r5c4]=4

7. [r1c4]-7-[r3c6]=7=[r5c7]=8=[r1c8]-8-[r1c4] => [r1c5]<>8, [r1c6]<>7 (Continuous loop)

8. [r2c9]-9-[r2c5]-5-[r2c1]-4-[r3c3]-1-[r3c5]-8-[r3c7]-7-[r1c7]-9-[r2c9] => [r2c9]<>9

And the puzzle is solved with naked singles after those loops.

I know this is not as efficient as the single loop solution or double loop solution, but it does work.
doduff
 
Posts: 32
Joined: 29 May 2006

Postby Gerra » Fri May 09, 2008 1:47 pm

I think the theorems here - http://forum.enjoysudoku.com/viewtopic.php?t=2143 - could be much simple.
We should just include the links within a cell.
A [2|6] - so bivalue - cell means a strong link.
A [3|5|7] - so polyvalue - cell means weak link.
After that all we have to do is alternating the link types.
So why don't treat the nice loops as AICs?

After this the propagation rules - http://sudopedia.org/wiki/Nice_Loop#Propagation_Rules - can be forgot.
Gerra
 
Posts: 8
Joined: 08 February 2008

Postby Mike Barker » Sat May 10, 2008 1:15 pm

IMO nice loops and AICs are different ways of looking at the same thing. AICs explain why these chains/nets result in an elimination and nice loops explain how to construct them. Starting from the one AIC rule - a valid chain consists of an alternating series of strong and weak links - all of the nice loop rules can be constructed. So for example recognizing that a bivalue cell contains a strong inference between its two candidates (one must be true), its easy to see that continuous links to a bivalue must both be weak with different labels. Nice loop rules simply capture this logical deduction so that this logic doesn't need to be gone through more than once. The differences show up in the notation as well. AIC notation (Eureka! notation) shows all of the inferences, where as nice loop notation only those required to make the logical linking. At this point I'm convinced that either approach is equally valid and useful. It really appears that preference is based mostly on which is learned first.

By the way, a polyvalued cell is a conjugate inference - both a strong inference (at least one must be true) and a weak inference (at most one is true). In constructing multi-inference nice loops I tend to treat them as strong inferences.
Code: Select all
Continuous Nice Loop: r1c3 =2= r2c3 =3= r2c2 -3- r5c2 -8- r13c2 =8= r1c3 => r2c3=23,r6c2<>3,r4c2<>8
Continuous AIC: (2)r1c3 = (2-3)r2c3 = (3)r2c2 - (3=8)r5c2 - (8)r13c2 = (8)r1c3 => r2c3=23,r6c2<>3,r4c2<>8
+-------------------+------------------+---------------+
|   1   568*b   28* |  289      4  58  | 7     3   69  |
|  56   3456* 23-5* |    1    259   7  | 8   269  469  |
|   9    48*b    7  |  238    238   6  | 5    12   14  |
+-------------------+------------------+---------------+
| 568  567-8     1  |  789    689   4  | 2   589    3  |
|   4     38*    9  |    5    138   2  | 6    18    7  |
|   2  567-3   358  | 3789  13689  18  | 4  1589  159  |
+-------------------+------------------+---------------+
|   3      2     6  |    4     15  15  | 9     7    8  |
|   7      9     4  |   28     28   3  | 1    56   56  |
|  58      1    58  |    6      7   9  | 3     4    2  |
+-------------------+------------------+---------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Sat May 10, 2008 4:59 pm

Mike Barker wrote:By the way, a polyvalued cell is a conjugate inference - both a strong inference (at least one must be true) and a weak inference (at most one is true).

Hmm. If all values in a cell are "conjugate", then all like-digits in a unit (sector, house, etc.) are conjugate too.

Then the term conjugate doesn't mean anything special anymore, and I certainly don't like that.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Sat May 10, 2008 6:47 pm

When considered in a multi-inference nice loops all of the occurrences of a digit in a unit do form a conjugate inference - one and only one must be true. On the other hand if there are only two occurrences of a digit in a unit, then these also form a conjugate link.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Sat May 10, 2008 8:28 pm

Mike Barker wrote:When considered in a multi-inference nice loops all of the occurrences of a digit in a unit do form a conjugate inference - one and only one must be true.

Believe it or not, I got the "one and only one must be true" part.:) I'm trying to figure out how -- as for a traditional conjugate pair -- one logic statement, its converse, its inverse, and its contrapositive are all true. If the following is correct ...

statement: if (A or B or C or ... ) then NOT ( ... X or Y or Z)
converse: if NOT ( ... X or Y or Z) then (A or B or C or ... )
inverse: if NOT (A or B or C or ... ) then ( ... X or Y or Z)
contrapositive: if ( ... X or Y or Z) then NOT (A or B or C or ... )

... it suggests that ...

Any pair of non-empty subsets, whose union includes all members of a parent strong inference set, are subsets with a conjugate inference.

If that's what you're saying, I agree. However, to help make the association with strong inference sets, I suggest the term conjugate inference subsets. (In most contexts, sets instead of subsets should be adequate.)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Nice loops for advanced level players - b/b plot

Postby excel_otaku » Fri Jul 29, 2011 2:00 am

Jeff
Thanks for your b/b plot. :D
This is very usefull.
Here is my solution using only nice loops.
No 1 Theorem5 r1c3<>1
[r1c3]=2=[r1c1]-2-[r4c1]-8-[r5c1]=8=[r5c7]-8-[r3c7]-7-[r3c6]-4-[r3c3]-1-[r1c3]
No 2 Theorem5 r1c5<>8
[r1c5]=1=[r3c5]-1-[r3c3]-4-[r3c6]-7-[r9c6]=7=[r9c4]=8=[r9c5]-8-[r1c5]
No 3 Theorem4 r1c5<>9
[r1c5]-9-[r2c5]-5-[r2c1]-4-[r9c1]-9-[r6c1]=9=[r6c9]-9-[r5c7]=9=[r1c7]-9-[r1c5]
No 4 Theorem4 r1c6<>9
[r1c6]-9-[r2c5]-5-[r2c1]-4-[r9c1]-9-[r6c1]=9=[r6c9]-9-[r5c7]=9=[r1c7]-9-[r1c6]
No 5 Theorem5 r1c9<>4
[r1c9]-4-[r2c9]=4=[r2c1]-4-[r9c1]-9-[r6c1]=9=[r6c9]=1=[r5c9]=3=[r4c9]=6=[r1c9]
No 6 Theorem4 r2c1<>4
[r2c1]-4-[r9c1]-9-[r6c1]=9=[r6c9]-9-[r2c9]-4-[r2c1]
No 7 Theorem5 r2c5<>5
[r2c5]-5-[r2c1]-4-[r9c1]-9-[r6c1]=9=[r6c9]-9-[r2c9]=9=[r2c5]
No 8 Theorem5 r2c9<>9
[r2c9]=4=[r2c1]-4-[r9c1]-9-[r6c1]=9=[r6c9]-9-[r2c9]
No 9 Theorem4 r3c4<>4
[r3c4]-4-[r3c6]-7-[r3c7]-8-[r1c8]=8=[r4c8]=6=[r4c9]=3=[r4c5]-3-[r5c4]-4-[r3c4]
No 10 Theorem5 r3c4<>7
[r3c4]-7-[r9c4]=7=[r9c6]-7-[r3c6]-4-[r5c6]=4=[r5c4]=3=[r3c4]
No 11 Theorem5 r3c4<>8
[r3c4]-8-[r3c7]-7-[r3c6]-4-[r5c6]=4=[r5c4]=3=[r3c4]
No 12 Theorem4 r3c5<>3
[r3c5]-3-[r4c5]=3=[r4c9]=6=[r4c8]=8=[r5c7]-8-[r3c7]-7-[r3c6]-4-[r5c6]=4=[r5c4]=3=[r3c4]-3-[r3c5]
No 13 Theorem5 r5c4<>3
[r5c4]=4=[r5c6]-4-[r3c6]-7-[r3c7]-8-[r1c8]=8=[r4c8]=6=[r4c9]=3=[r4c5]-3-[r5c4]
No 14 Theorem4 r5c6<>4
[r5c6]-4-[r5c4]-3-[r4c5]-2-[r4c1]-8-[r5c1]=8=[r5c7]-8-[r3c7]-7-[r3c6]-4-[r5c6]
No 15 Theorem4 r7c3<>1
[r7c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]-8-[r5c7]-9-[r6c9]-1-[r6c2]=1=[r9c2]-1-[r7c3]
No 16 Theorem3 r7c7<>2
[r7c7]=1=[r7c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]-8-[r5c7]-9-[r6c9]-1-[r6c2]=1=[r9c2]-1-[r9c7]=1=[r7c7]
No 17 Theorem5 r9c3<>1
[r9c3]=6=[r9c5]=8=[r9c4]=7=[r9c6]-7-[r3c6]-4-[r3c3]-1-[r9c3]
No 18 Theorem5 r9c5<>2
[r9c5]=8=[r9c4]=7=[r9c6]-7-[r3c6]-4-[r3c3]-1-[r7c3]=1=[r7c7]=2=[r9c7]-2-[r9c5]
No 19 Theorem4 r9c7<>1
[r9c7]-1-[r7c7]=1=[r7c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]-8-[r5c7]-9-[r6c9]-1-[r6c2]=1=[r9c2]-1-[r9c7]
excel_otaku
 
Posts: 2
Joined: 26 July 2011

Re: Chain Solution

Postby excel_otaku » Sat Jul 30, 2011 4:37 am

doduff wrote:I know this is an old post, but I felt like putting in my bit also.

Here is the list of loops that I found to solve the exercise puzzle:

1. [r3c7]-8-[r1c8]=8=[r4c8]-8-[r5c7]=8=[r3c7] => [r1c7]<>8 (Continuous loop)

2. [r7c3]-1-[r7c7]=1=[r9c7]-1-[r2c2]=1=[r6c2]-1-[r6c9]-9-[r5c7]=9=[r1c7]=7=[r3c7]-7-[r3c6]-4-[r3c3]-1-[r7c3] => [r7c3]<>1,

[r7c7]=1, [r9c7]=2, [r9c56]<>2

3. [r3c4]=3=[r5c4]-3-[r4c5]=3=[r4c9]=6=[r4c8]=8=[r4c1]-8-[r5c1]=8=[r5c7]-8-[r3c7]-7-[r3c4] => [r3c4]<>7

4. [r3c4]-4-[r5c4]-3-[r5c9]=3=[r4c9]=6=[r4c8]-6-[r1c8]-8-[r3c7]-7-[r3c6]-4-[r3c4] => [r3c4]<>4

5. [r7c6]=2=[r7c5]-2-[r4c5]-3-[r4c9]-6-[r4c8]-8-[r5c7]=8=[r3c7]=7=[r3c6]-7-[r9c6]-9-[r7c6] => [r7c6]<>9, [r7c6]=2, [r7c5]<>2

6. [r5c5]=2=[r4c5]-2-[r4c1]-8-[r4c8]=8=[r5c7]-8-[r3c7]-7-[r3c6]-4-[r5c6]-5-[r5c5] => [r5c5]<>5, {r5c6]=5, [r1c6]<>5,

[r3c5]<>3, [r3c4]=3, [r5c4]=4

7. [r1c4]-7-[r3c6]=7=[r5c7]=8=[r1c8]-8-[r1c4] => [r1c5]<>8, [r1c6]<>7 (Continuous loop)

8. [r2c9]-9-[r2c5]-5-[r2c1]-4-[r3c3]-1-[r3c5]-8-[r3c7]-7-[r1c7]-9-[r2c9] => [r2c9]<>9

And the puzzle is solved with naked singles after those loops.

I know this is not as efficient as the single loop solution or double loop solution, but it does work.


Hi,doduff
Is chain 2 correct?
"[r9c7]-1-[r2c2]" ??
excel_otaku
 
Posts: 2
Joined: 26 July 2011

Previous

Return to Advanced solving techniques

cron