The New Sudoku Players' Forum

[tso]

This is a very hard puzzle:

Code: Select all

. . . | . 1 . | . . 2
8 4 . | . . . | . . .
3 . . | . . 9 | 4 . 7
------+-------+------
. 8 . | . . 7 | . . 9
. 1 6 | . . . | 7 2 .
9 . . | 1 . . | . 8 .
------+-------+------
6 . 4 | 2 . . | . . 3
. . . | . . . | . 7 4
5 . . | . 9 . | . . .


Forcing chains -- whether bilocation, bivalue or mixed -- will not be enough to solve this. Nishio will not help.

Advanced tactics including mixed forcing chains and uniqueness rectangles dead end here:

Code: Select all

 7     56    59    | 3456  1     3456  | 8     39    2 
 8     4     29    | 3567  23567 356   | 56    39    1 
 3     256   1     | 8     256   9     | 4     56    7 
-------------------+-------------------+---------------
 2     8     3     | 56    56    7     | 1     4     9 
 4     1     6     | 9     38    38    | 7     2     5 
 9     57    57    | 1     4     2     | 3     8     6 
-------------------+-------------------+---------------
 6     79    4     | 2     78    18    | 59    15    3 
 1     29    8     | 356   356   56    | 29    7     4 
 5     3     27    | 47    9     14    | 26    16    8 


What non-computer methods do you personally use for puzzles like these?

[maria45]

Hello tso,

well, starting from the point given, I found after about 2 minutes a simple forcing chain (notation as in my other posts):

a3=5 or a3=9, b3=2, k3=7, k4=4, k6=1, k8=6, c8=5, c2=6 > c2!=5

This removes of course only the 5 from r3c2, but a bit of similar chains do the rest of the job for me, in all cases I tried so far...

Kind regards, Maria

[vidarino]

There's also a nice loop there;

R2C3=2=R3C2-2-R8C2=2=R9C3=7=R7C2-7-R7C5=7=R2C5=2=R2C3

which sets R2C3=2, and the rest solves with singles only.

[CathyW]

I couldn't solve it, but managed a few more eliminations:
Looking at bivalue cells, you can see an x-cycle of 5s at r1c2,3 and r6c2,3 which allows elimination of 5 at r2c2 albeit by a different method to Maria.

Then you have locked 5s in row 1, or an x-wing (as above) to eliminate 5s of row 1, box 2.

xy chain allows elimination of 6 at r3c5.

But I can't see anything else so the puzzle remains unsolved! I'd have to resort to trying a candidate from one of the bivalue cells and see where it led - maybe to solution, if not back track and try the other one!

Code: Select all

 
{7}     {56}    {59}    {346}   {1}     {346}   {8}     {39}    {2}     
{8}     {4}     {29}    {3567}  {23567} {356}   {56}    {39}    {1}     
{3}     {26}    {1}     {8}     {25}    {9}     {4}     {56}    {7}     
{2}     {8}     {3}     {56}    {56}    {7}     {1}     {4}     {9}     
{4}     {1}     {6}     {9}     {38}    {38}    {7}     {2}     {5}     
{9}     {57}    {57}    {1}     {4}     {2}     {3}     {8}     {6}     
{6}     {79}    {4}     {2}     {78}    {18}    {59}    {15}    {3}     
{1}     {29}    {8}     {356}   {356}   {56}    {29}    {7}     {4}     
{5}     {3}     {27}    {47}    {9}     {14}    {26}    {16}    {8}     


I'll have to read up on 'nice loops' - I can understand how xy-chains permit eliminations but hadn't realised the loops could actually set a particular cell.

[vidarino]

I'll have to read up on 'nice loops' - I can understand how xy-chains permit eliminations but hadn't realised the loops could actually set a particular cell.

If a discontinuous nice loop begins and ends with strong links for the same candidate, the candidate can be fixed at the discontinuity.

You can choose to eliminate from the nodes that are adjacent to the discontinuity instead, of course, but since the links are strong, that leaves only one occurance of the candidate in the links' units.

Vidar

[tso]

Sorry about that everybody, but I screwed up on the original puzzle posted, making my original question misplaced.

There are actually plenty of valid forcing chains and/or nice loops that solve the puzzle, some of them annoyingly obvious in retrospect. I've found some that were only 5 links long, for example:

If r2c5=7 -> r2c3=2
If r2c5<>7 -> r2c4=7 -> r9c4<>7 -> r9c3=7 -> r2c3=2
Therefore, r2c3=2

Written as a nice loop:

r2c3=2=r9c3=7=r9c4=7=r2c4=7=r2c5=2=r2c3, therefore, r2c3=2

Slight variation, same result:
r2c3=2=r9c3=7=r8c2=7=r7c5=7=r2c5=2=r2c3, therefore, r2c3=2

(Vidarino -- did I write these nice loops correctly? The deduction I make from them is valid?)

[Jeff]

r2c3=2=r9c3=7=r9c4=7=r2c4=7=r2c5=2=r2c3, therefore, r2c3=2

...did I write these nice loops correctly?

Hi Tso, The nice loop notation should be:

r2c3=2=r9c3=7=r9c4-7-r2c4=7=r2c5=2=r2c3, therefore, r2c3=2

where r9c4-7-r2c4 indicates the weak inference.

[tso]

r2c3=2=r9c3=7=r9c4=7=r2c4=7=r2c5=2=r2c3, therefore, r2c3=2

...did I write these nice loops correctly?

Hi Tso, The nice loop notation should be:

r2c3=2=r9c3=7=r9c4-7-r2c4=7=r2c5=2=r2c3, therefore, r2c3=2

where r9c4-7-r2c4 indicates the weak inference.

How is the link between r9c4 and r2c4 weak? The two cells are the only two in that column that can contain a 7.

Code: Select all

 
 *--------------------------------------------------------------------*
 | 7      56     59     | 3456   1      3456   | 8      39     2      |
 | 8      4      29     | 356[7] 23567  356    | 56     39     1      |
 | 3      256    1      | 8      256    9      | 4      56     7      |
 |----------------------+----------------------+----------------------|
 | 2      8      3      | 56     56     7      | 1      4      9      |
 | 4      1      6      | 9      38     38     | 7      2      5      |
 | 9      57     57     | 1      4      2      | 3      8      6      |
 |----------------------+----------------------+----------------------|
 | 6      79     4      | 2      78     18     | 59     15     3      |
 | 1      29     8      | 356    356    56     | 29     7      4      |
 | 5      3      27     | 4[7]   9      14     | 26     16     8      |
 *--------------------------------------------------------------------*


[Jeff]

How is the link between r9c4 and r2c4 weak? The two cells are the only two in that column that can contain a 7.

The link between r9c4 and r2c4 is no doubt a strong link which means it can be expressed as a strong inference or a weak inference. To propagate from r9c4 to r2c4, the weak inference has been used.

[r2c3]=2=[r9c3]=7=[r9c4]-7-[r2c4]=7=[r2c5]=2=[r2c3], therefore, r2c3=2

The link inferences of this nice loop can be verified from the implication streams.

If r2c5=7 -> r2c5<>2 -> r2c3=2
If r2c5<>7 -> r2c4=7 -> r9c4<>7 -> r9c3=7 -> r9c3<>2 -> r2c3=2

strong inference: (r2c5=7 -> r2c5<>2) -> r2c3=2
strong inference: r2c5<>7 -> r2c4=7
weak inference: r2c4=7 -> r9c4<>7
strong inference: r9c4<>7 -> r9c3=7
strong inference: (r9c3=7 -> r9c3<>2) -> r2c3=2

where
Strong inference => if X false, then Y true
Weak inference => if X true, then Y false

[tso]

Jeff,

Apparantly I still haven't fully grasped the nice loop notation -- or even it's purpose.

Is it used merely to describe a deduction already found -- or to in fact help find one?

When looking for a loop, I'm not propagating one way or the other, just trying to close the loop. If I label edges, I might do so before even finding a loop, or after finding a loop but without regard to propagation direction. In this case, I filtered for 7s and found that r9c3-r9c4-r2c4-r2c5 formed three consecutive pairs of conjugates cells and labeld each pair =7= accordingly. I looked in the one cell that that is colinear (co-groupier?) with both ends to see if there was something to close the loop -- and there was -- two more pairs of conjugate cells.

Am I wrong to consider a "C1=x=C2" link to mean "C1=x if and only if C2<>x"? Will I either make some unsupported deductions or miss some valid deductions if I do?

That was the great thing about pure xy-type chains -- you can just label the edges between all the bivalue cells without any thought to direction, then look for a closed loop. Am I jumping to conclusions that these types of nice loops work this way as well?

Which existing page(s) or thread(s) best explains the use of nice loop notation and all it's nuances?

[Jeff]

Is it used merely to describe a deduction already found -- or to in fact help find one?

A nice loop notation is an accurate record of a forcing chain type deduction already found, with a correct inference for each link indicated. This means that, from a nice loop notation, the implication streams can be derived accurately.

When looking for a loop, I'm not propagating one way or the other, just trying to close the loop. If I label edges, I might do so before even finding a loop, or after finding a loop but without regard to propagation direction.

That's correct.

In this case, I filtered for 7s and found that r9c3-r9c4-r2c4-r2c5 formed three consecutive pairs of conjugates cells and labeld each pair =7= accordingly.

The notation =7= is a strong inference strictly means if the previous node is not 7, then the following node must be 7; only strong link can have a strong inference.

The notation -7- is a weak inference strictly means if the previous node is 7, then the following node must not be 7; both strong link and weak link can have a weak inference.

For the chain to propagate correctly (logically), the 3 strong 7-links must NOT be interpreted as:

strong-strong-strong inferences
weak-weak-weak inferences
strong-strong-weak inferences
strong-weak-weak inferences
weak-weak-strong inferences
weak-strong-strong inferences

The 3 strong 7-links must be interpreted either as “strong-weak-strong inferences” or “weak-strong-weak inferences” in accordance with a set of nice loop propagation rules that enforces the correct inference mode for each link.

I looked in the one cell that that is colinear (co-groupier?) with both ends to see if there was something to close the loop -- and there was -- two more pairs of conjugate cells.

That's correct, but again the nice loop propagation rules must be followed to ensure legal inferences.

Am I wrong to consider a "C1=x=C2" link to mean "C1=x if and only if C2<>x"? Will I either make some unsupported deductions or miss some valid deductions if I do?

A "C1=x=C2" link could means:

"if C1=x, then C2<>x" ....weak inference
"if C1<>x, then C2=x" ....strong inference
"if C2=x, then C1<>x" ....weak inference
"if C2<>x, then C1=x" ....strong inference

If you don't follow the nice loop propagation rules to select the approporiate inferences to take place, you will either make some unsupported deductions or miss some valid deductions.

That was the great thing about pure xy-type chains -- you can just label the edges between all the bivalue cells without any thought to direction, then look for a closed loop. Am I jumping to conclusions that these types of nice loops work this way as well?

This can be done to xy-chain because all links in an xy-chain only require weak inferences. Notice that when there is a strong link, you still only use the weak inference of that strong link. This is similar to the middle link of the 3 strong 7-links discussed above.

Which existing page(s) or thread(s) best explains the use of nice loop notation and all it's nuances?

The nice loop propagation rules are described in bilocation/bivalue plot & nice loops: description.

[aeb]

Which existing page(s) or thread(s) best explains the use of nice loop notation and all it's nuances?

This is not an answer to that question, but you might look at http://homepages.cwi.nl/~aeb/games/sudoku/solving20.html
I wrote most of my stuff before discovering this forum, so all notation and terminology is different, although I recently added some stuff found here or answering questions posed here. My basic forcing chain is a chain of links of the type (i,j)d > (i',j')d' "if position (i,j) is d, then position (i',j') is d'". Instead of d one can have !d "not d". Here people use ricj instead of (i,j). Such chains describe proofs for claims about digits, in terms of claims about links. When the conclusion needs more than just the last link, for example the last three links, I write >>> instead of >. Now given such a chain one might ask for the reason why the individual links are true. Clearly the common reasons are: (i) being adjacent, "seeing each other", "weak link" - this proves (i,j)d > (i',j')!d, and (ii) being a pair (conjugate pair, strong pair) for a digit d - this proves (i,j)!d > (i',j')d, and (iii) (i,j)d > (i',j')e in case (i',j') is bivalue de. And then there is the trivial: if the digit is d then it is not something else: (i,j)d > (i,j)!e. Adjacency is so obvious that no further notation is needed. Being a pair for the digit d can be annotated as =d=, but usually this added information is redundant. If the entire chain is for a single digit, alternating d and !d, and only (i),(ii) are used, then it suffices to mention d separately and write the chain as P=Q-R=S with positions P=(i,j) only. In a first approximation this notation is equivalent to the one used here. Maybe Jeff can tell what kinds of things his notation represents and this does not, or how his notation represents the situation where two or three previous links are all needed.

[Jeff]

Maybe Jeff can tell what kinds of things his notation represents and this does not, or how his notation represents the situation where two or three previous links are all needed.

Hi Aeb, thank you for sharing your thought.

Honestly, I can't answer you question as I am only familiar with the notations related to B/B plot and nice loops. Perhaps you could provide an example, then I can show you exactly how the propagation/deduction can be expressed by the nice loop notation.

[aeb]

Perhaps you could provide an example, then I can show you exactly how the propagation/deduction can be expressed by the nice loop notation.

On http://homepages.cwi.nl/~aeb/games/sudoku/solving19.html
I show the use of a forcing chain that is (6,2)2 > (5,1)8 > (5,6)3 >> (5,9)4 >>> (5,7)2 > (4,8)7 > (6,8)5 > (6,9)1 > (6,3)7 > (8,3)3 > (8,2)2 > (6,2)3
in my notation. Here (5,1)8 > (5,6)3 >> (5,9)4 >>> (5,7)2 means that the first claim implies the second, the first two imply the third, the first three imply the fourth.

[Jeff]

I show the use of a forcing chain that is (6,2)2 > (5,1)8 > (5,6)3 >> (5,9)4 >>> (5,7)2 > (4,8)7 > (6,8)5 > (6,9)1 > (6,3)7 > (8,3)3 > (8,2)2 > (6,2)3
in my notation. Here (5,1)8 > (5,6)3 >> (5,9)4 >>> (5,7)2 means that the first claim implies the second, the first two imply the third, the first three imply the fourth.

This is referred to as a forcing net as there are nodes in the implication stream making multiple inferences.

With the segment: (5,1)8 > (5,6)3 >> (5,9)4 >>> (5,7)2, if I understand correctly, the nice loop notation is:

[r5c1](-8-[r5c79])-8-[r5c6](-3-[r5c7])-3-[r5c9]-4-[r5c7]-2-

where
[r5c1](-8-[r5c79])-8-[r5c6] means nodes [r5c1] and [r5c6] are consecutive and inferences from the first node are also made to [r5c79]

Your notation doesn't show whether the inference between nodes are strong or weak. However, the kind of progression suggests that they are usually weak inferences.