Type 3 Discontinuous Nice Loop

Advanced methods and approaches for solving Sudoku puzzles

Type 3 Discontinuous Nice Loop

Postby EnderGT » Thu Feb 28, 2008 5:57 pm

At least, that's what the solver at PaulsPages SudokuXP calls it... I took the original puzzle:
Code: Select all
 . 8 . | 5 . . | 9 . .
 2 . . | . . 1 | . 6 .
 . . 7 | 4 . . | . 5 1
-------+-------+-------
 4 . . | 2 1 . | . 9 .
 9 . . | . . . | . . 5
 . 7 . | . 4 8 | . . 2
-------+-------+-------
 8 1 . | . . 6 | 5 . .
 . 4 . | 1 . . | . . 7
 . . 2 | . . 4 | . 1 .


down to this state:
Code: Select all
 13    8     134   | 5     6     2     | 9     7     34
 2     359   3459  | 37    79    1     | 348   6     348
 36    369   7     | 4     8     39    | 2     5     1
-------------------+-------------------+------------------
 4     36    368   | 2     1     5     | 7     9     68
 9     2     18    | 6     3     7     | 148   48    5
 156   7     156   | 9     4     8     | 16    3     2
-------------------+-------------------+------------------
 8     1     39    | 37    279   6     | 5     24    349
 356   4     3569  | 1     259   39    | 368   28    7
 7     3569  2     | 8     59    4     | 36    1     369


and then asked the solver for a hint. What it gave me is this:
[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] =4= [R2C7] -4- [R1C9] -3- [R1C1]


My reaction to this was WTF? I don't see the logic that makes R5C3 a 1, or R5C7 a 4. Hopefully, someone here can help me understand this.

I realize this could have gone into the "Help with Particular Puzzles" section, but what I'm really looking for here is an explanation of why this chain works. I've seen examples in other places that have similarly disconnected (to my mind, at least) logic to demonstrate the loop. An example would be this puzzle:
Code: Select all
 2567   567    12     | 9       35678  357    | 4      1237   1278
 24679  4679   8      | 36      1      347    | 5      2379   279
 3      4579   149    | 58      4578   2      | 78     6      1789
----------------------+-----------------------+---------------------
 2456   456    7      | 1       235    9      | 236    8      2456
 2589   589    239    | 4       23578  6      | 237    1257   1257
 24568  1      234    | 2358    23578  357    | 9      2457   24567
----------------------+-----------------------+---------------------
 489    2      49     | 7       456    1      | 68     459    3
 478    3478   5      | 236     9      34     | 1      247    68
 1      3479   6      | 235     2345   8      | 27     24579  24579


for which they declare a loop:
[R1C5]=8=[R1C9]-8-[R8C9]-6-[R7C7]=6=[R4C7]=3=[R4C5]-3-[R1C5] => R1C5<>3


How did they decide that R4C7 was a 3 instead of a 2, much less that the first square should be an 8?

Please help, I'm afraid I'm in over my head here...
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby Pat » Thu Feb 28, 2008 6:15 pm

EnderGT wrote:
Code: Select all
 13    8     134   | 5     6     2     | 9     7     34
 2     359   3459  | 37    79    1     | 348   6     348
 36    369   7     | 4     8     39    | 2     5     1
-------------------+-------------------+------------------
 4     36    368   | 2     1     5     | 7     9     68
 9     2     18    | 6     3     7     | 148   48    5
 156   7     156   | 9     4     8     | 16    3     2
-------------------+-------------------+------------------
 8     1     39    | 37    279   6     | 5     24    349
 356   4     3569  | 1     259   39    | 368   28    7
 7     3569  2     | 8     59    4     | 36    1     369



and then asked the solver for a hint. What it gave me is this:

[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] =4= [R2C7] -4- [R1C9] -3- [R1C1]



I don't see the logic that makes R5C3 a 1, or R5C7 a 4.

Hopefully, someone here can help me understand this.



hey EnderGT,

the notation is indeed odd ( until you get used to it )
    but if you just follow those cells
    you can probably see the logic
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: Type 3 Discontinuous Nice Loop

Postby hobiwan » Thu Feb 28, 2008 6:15 pm

EnderGT wrote:
[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] =4= [R2C7] -4- [R1C9] -3- [R1C1]

The chain is written in an abbreviated form. the complete chain should be:
[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] -4- [r5c7] =4= [R2C7] -4- [R1C9] =3= [r1c9] -3- [R1C1]
(bold from me)
which means, that if [r1c1]<>1 => [r1c1]<>3, so [r1c1] has to be 1 (but you probably knew that already).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: Type 3 Discontinuous Nice Loop

Postby EnderGT » Thu Feb 28, 2008 6:24 pm

hobiwan wrote:
EnderGT wrote:
[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] =4= [R2C7] -4- [R1C9] -3- [R1C1]

The chain is written in an abbreviated form. the complete chain should be:
[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] -4- [r5c7] =4= [R2C7] -4- [R1C9] =3= [r1c9] -3- [R1C1]
(bold from me)
which means, that if [r1c1]<>1 => [r1c1]<>3, so [r1c1] has to be 1 (but you probably knew that already).


I think maybe I didn't ask the question very well.

I think I understand the notation.

What I don't see (maybe it's because I'm sick and medicated) is the logic that makes R5C3 a 1. I mean, there's another candidate 1 in the column... why is R5 the 1 and not R6? And then once R5C3 is a 1, why is the 4 removed from R5C7? I must be missing something incredibly simple here...
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby Pat » Thu Feb 28, 2008 6:27 pm

EnderGT wrote:I think maybe I didn't ask the question very well.

I think I understand the notation.

What I don't see (maybe it's because I'm sick and medicated) is the logic that makes R5C3 a 1. I mean, there's another candidate 1 in the column... why is R5 the 1 and not R6?


the notation does not claim any specific digit in any specific cell
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby EnderGT » Thu Feb 28, 2008 6:30 pm

Pat wrote:
EnderGT wrote:I think maybe I didn't ask the question very well.

I think I understand the notation.

What I don't see (maybe it's because I'm sick and medicated) is the logic that makes R5C3 a 1. I mean, there's another candidate 1 in the column... why is R5 the 1 and not R6?


the notation does not claim any specific digit in any specific cell


Um... ok then maybe I don't understand the notation? I thought that

[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] =4= [R2C7] -4- [R1C9] -3- [R1C1]

the bolded parts above indicate that the assignment of the value in the first cell removes the candidate from the second cell, thus claiming a specific digit in a specific cell. No?
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby daj95376 » Thu Feb 28, 2008 7:03 pm

Basic Nice Loop notation has its peculiarities:

Code: Select all
[RmCn]=x=         means [RmCn] is not x
      =x=[RvCw]   means [RvCw] is     x

[RmCn]-x-         means [RmCn] is     x
      -x-[RvCw]   means [RvCw] is not x

my understanding wrote:Basic chains represent a logical operation where links are serially joined together, and no modifications occur in the grid. (People get around the serial constraint by claiming ALS and other internal structures.)

Networks represent modifications in the grid, and don't have to be serial.

The logic behind the chain is as follows:

If [r1c1] is 1, then [r1c1] is not 3. If [r1c1] is not 1, then [r1c1] is not 3. Either way, you can conclude that [r1c1] is not 3. Unfortunately, the chain notation only indicates the second half of the logic.

Cec: This is an example of the second chain/loop in my notes.
Last edited by daj95376 on Thu Feb 28, 2008 5:37 pm, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby EnderGT » Thu Feb 28, 2008 7:16 pm

daj95376 wrote:Basic Nice Loop notation has its peculiarities:

Code: Select all
[RmCn]=x          means [RmCn] is not x
       x=[RmCn]   means [RmCn] is     x

[RmCn]-x          means [RmCn] is     x
       x-[RmCn]   means [RmCn] is not x

my understanding wrote:Basic chains represent a logical operation where links are serially joined together, and no modifications occur in the grid. (People get around the serial constraint by claiming ALS and other internal structures.)

Networks represent modifications in the grid, and don't have to be serial.

The logic behind the chain is as follows:

If [r1c1] is 1, then [r1c1] is not 3. If [r1c1] is not 1, then [r1c1] is not 3. Either way, you can conclude that [r1c1] is not 3.


So I had it exactly backwards. Instead of "R1C1 is one, therefore R1C3 is not one", it's "R1C1 is not 1, therefore R1C3 is one", and instead of "R1C3 is not one, therefore R5C3 is one, therefore R5C7 is 4", it's "R1C3 is one, so R5C3 is not one, therefore R5C7 is not 4".

The results of this interpretation make a lot more sense, even though I feel that the notation is misleading. Oh well, I guess I'll get used to it.

Thanks for the answers.
EnderGT
 
Posts: 69
Joined: 19 February 2008

loop

Postby Pat » Sun Mar 02, 2008 1:26 pm

EnderGT wrote:
Code: Select all
 13    8     134   | 5     6     2     | 9     7     34
 2     359   3459  | 37    79    1     | 348   6     348
 36    369   7     | 4     8     39    | 2     5     1
-------------------+-------------------+------------------
 4     36    368   | 2     1     5     | 7     9     68
 9     2     18    | 6     3     7     | 148   48    5
 156   7     156   | 9     4     8     | 16    3     2
-------------------+-------------------+------------------
 8     1     39    | 37    279   6     | 5     24    349
 356   4     3569  | 1     259   39    | 368   28    7
 7     3569  2     | 8     59    4     | 36    1     369



and then asked the solver for a hint. What it gave me is this:

[R1C1] =1= [R1C3] -1- [R5C3] =1= [R5C7] =4= [R2C7] -4- [R1C9] -3- [R1C1]



I don't see the logic that makes R5C3 a 1, or R5C7 a 4.

Hopefully, someone here can help me understand this.



sorry about Thursday -- i probably should've stayed out of this, knowing i'd have to leave early.


anyway i'd just like to add that my loop would be slightly different --
    if r1c3=1 then
    the 1 for r5 goes in c7,
    the 4 for c7 goes in r2,
    the 4 for c3 goes in r1, conflict
or you can follow the same loop in the reverse direction --
    if r1c3=1 then
    the 4 for c3 goes in r2,
    the 4 for c7 goes in r5,
    the 1 for r5 goes in c3, conflict
( i like it in words )
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: loop

Postby daj95376 » Sun Mar 02, 2008 2:09 pm

Pat wrote:anyway i'd just like to add that my loop would be slightly different --

if r1c3=1 then
the 1 for r5 goes in c7,
the 4 for c7 goes in r2,
the 4 for c3 goes in r1, conflict

or you can follow the same loop in the reverse direction --

if r1c3=1 then
the 4 for c3 goes in r2,
the 4 for c7 goes in r5,
the 1 for r5 goes in c3, conflict

( i like it in words )

-or- as implication chains

Code: Select all
[r1c3]=1 => [r5c7]=1 => [r2c7]=4 => [r1c3]=4; => [r1c3]<>1
[r1c3]=1 => [r2c3]=4 => [r5c7]=4 => [r5c3]=1; => [r1c3]<>1

Interesting first loop. You chose a unit, [c3], where the values {1,4} occur in three cells, but with only one cell in common. In the common cell, you force the value 1, and then deduce the elimination of 4 in its second cell. This produces a conflict for 4 in [c3]. Interesting!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

re: loop

Postby Pat » Sun Mar 02, 2008 2:41 pm

daj95376 wrote:Interesting first loop. You chose a unit, [c3], where the values {1,4} occur in three cells, but with only one cell in common. In the common cell, you force the value 1, and then deduce the elimination of 4 in its second cell. This produces a conflict for 4 in [c3]. Interesting!


i was merely describing a loop, can't properly claim discovering it -- as i had first read EnderGT's post!
    i like being able to follow the loop in both directions
    -- though each direction is itself sufficient for the exclusion.
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

re: loop

Postby Pat » Tue Mar 11, 2008 3:27 pm

Pat wrote:
    i like being able to follow the loop in both directions
    -- though each direction is itself sufficient for the exclusion

what's the common terminology for this loop ?
    i've just been looking at some definitions and i see that a "forcing chain" must have 2 (or more) implication-streams -- whereas in my loop, each direction (each implication-stream) in itself is sufficient, therefore, this is not a "forcing chain" -- so, what is it called?
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: re: loop

Postby daj95376 » Wed Mar 12, 2008 12:16 am

Pat wrote:i like being able to follow the loop in both directions -- though each direction is itself sufficient for the exclusion

what's the common terminology for this loop ?

Pat, would your loops qualify as contradiction chains/loops? These loops aren't AICs, so they aren't bidirectional. They are read from left-to-right and each stands independent of the other -- as you pointed out.

I've just about given up on using names for chains because it only creates turmoil. Besides, it seems to me that many examples of chains are what Jeff and Sudopedia call networks.

In my notes on chains, your first loop is simply my Type 1 loop, and your second loop is my Type 2 chain.

Code: Select all
[RmCn]-x- ... =y=[RmCn]   (assume x true , show y true           ) -- eliminate x in          [RmCn] (loop)

[RmCn]-x- ... =x=[peer]   (assume x true , show x true  in [peer]) -- eliminate x in          [RmCn]

[RmCn]=x= ... -y-[RmCn]   (assume x false, show y false          ) -- eliminate y in          [RmCn] (loop)

[RmCn]=x= ... -x-[peer]   (assume x false, show x false in [peer]) -- eliminate x in          [peer]

[RmCn]=x= ... =x=[RuCv]   (assume x false, show x true  in [RuCv]) -- eliminate x in peers of [RmCn] and [RuCv]

Forcing Chains            (pray for divine clarification)
...............................................................................................................
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

re: contradiction-chain

Postby Pat » Wed Mar 12, 2008 10:42 am

daj95376 wrote:Pat, would your loops qualify as contradiction-chains?


thanks, daj95376, that should be a good name !
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: re: loop

Postby ronk » Wed Mar 12, 2008 12:04 pm

daj95376 wrote:Pat, would your loops qualify as contradiction chains/loops? These loops aren't AICs, so they aren't bidirectional. They are read from left-to-right and each stands independent of the other -- as you pointed out.

We already have the fundamental terms forcing chains, nice loops and AICs. We certainly don't need another.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques