The New Sudoku Players' Forum

[rubylips]

Bob,

You might like to consider what I call extended links, e.g. from your candidate grid for Puzzle 5 (promoted to Puzzle 6 as I type):

r5c5=5 => (r5c4 and r6c4) <>5 => r2c4=5
Moreover, r2c4=5 => r5c5=5 by the reverse argument.

I write this link r5c5=5=r2c4. Extended links sometimes significantly shorten solutions. They're only a little help in the current puzzle but we have:

Code: Select all

Consider the chains r2c4=9=r8c6=2=r5c5, r2c4=5=r5c5 and r2c4=8=r5c5.
Whichever of the 3 candidate values fills the cell r5c5, the cell r2c4 cannot contain the value 9.
- The move r2c4:=9 has been eliminated.
The value 9 in Box 8 must lie in Column 4.
- The move r8c6:=9 has been eliminated.


[Bob Hanson]

Hmm. I'm missing something. What does:

r2c4=9=r8c6=2=r5c5

say? But I see where it is headed.

Don't get me wrong -- I'm perfectly delighted with the "nice loop" idea -- but
what distinguishes this business from trial and error -- randomly picking a
cell, setting the value, and seeing what comes of it? Certainly that will solve
any Sudoku....

[bennys]

same as rubylips using ALS

Code: Select all

A={R1C5,R3C5,R5C5}
B={R1C6,R2C6,R3C6}
C={R4C6,R5C6}

R2C4=9=>B locked on 146 (remove 4 from A) =>C locked on 27 (remove 2 from A)

[r.e.s.]

You might like to consider what I call extended links, e.g. from your candidate grid for Puzzle 5 (promoted to Puzzle 6 as I type):

r5c5=5 => (r5c4 and r6c4) <>5 => r2c4=5
Moreover, r2c4=5 => r5c5=5 by the reverse argument.

I write this link r5c5=5=r2c4. Extended links sometimes significantly shorten solutions. They're only a little help in the current puzzle but we have:

Code: Select all

Consider the chains r2c4=9=r8c6=2=r5c5, r2c4=5=r5c5 and r2c4=8=r5c5.
Whichever of the 3 candidate values fills the cell r5c5, the cell r2c4 cannot contain the value 9.
- The move r2c4:=9 has been eliminated.
The value 9 in Box 8 must lie in Column 4.
- The move r8c6:=9 has been eliminated.


What I'm about to add is nothing conceptually new, but I'd like to show what I think is the easiest method for a person to recognize this type of link at a glance.

In each of the pictures below, two different groups of cells (yellow, red) are seen to share the same complement of cells (green) which would extend either group to form a complete unit (row/col/box). Therefore RED set of digits = YELLOW set of digits, so any candidate appearing exactly once in both red & yellow sets must be either "true" in both sets or "false" in both sets.

The picture for r2c4=5=r5c5 (i.e., r2c4=5 <=> r5c5=5) is


the picture for r2c4=9=r8c6 is


and the picture for r8c6=2=r5c5 is


Edit: Improved wording.

[Lardarse]

So now we have another use for the "law of leftovers"...

[ronk]

Code: Select all

Consider the chains r2c4=9=r8c6=2=r5c5, r2c4=5=r5c5 and r2c4=8=r5c5.
Whichever of the 3 candidate values fills the cell r5c5, the cell r2c4 cannot contain the value 9.
- The move r2c4:=9 has been eliminated.

rubylips, when your word description implies ...

If r5c5=2 then ... r2c4<>9 or
If r5c5=5 then ... r2c4<>9 or
If r5c8=8 then ... r2c4<>9

... then why, oh why, don't your chains read left-to-right instead of right-to-left?

r2c4=9=r8c6=2=r5c5
.......
Don't get me wrong -- I'm perfectly delighted with the "nice loop" idea

Notwithstanding the quotes, I think Jeff would object to using the "nice loop" term here.

What I'm about to add is nothing conceptually new, but I'd like to show what I think is the easiest method for a person to recognize this type of link at a glance.

Very nice post.

[rubylips]

r.e.s.,

Thanks for your post. What you describe is precisely what I do in the source code.

why, oh why, don't your chains read left-to-right instead of right-to-left?

I'll make this code change my Christmas present to you.

[ronk]

I'll make this code change my Christmas present to you.

Thank you in advance. Hopefully others will appreciate the change too.

BTW, in case I forgot to earlier, thanks also for getting rid of the '|' in your candidate illustrations.



On topic: I've yet to figure out my first "nice loop" in exercise #6.

[Pep]

Exercise #5

I'll be interested to see how people do this one.

Do you mean Exercise 6? If so, then I can get a quite a way fuirther, but still not complete it, by following weak links on intersections between units, rather than single cells. From your partial position, my program finds a few more eliminating chains, an example of which is:

Code: Select all

Elide 2 from r8c2 because to fix it forces a chain of inferences via 2@{r8c2} - (r8) - (!2)@{r8c9} - (c9) - 2@{r5c9,r4c9} - (b6) - (!2)@{r6c8} - (r6) - 2@{r6c2,r6c1} - (b4) - (!2)@{r5c3,r4c3} - (c3) - 2@{r9c3,r7c3} to a clash in b7.

I get stuck at the following position:

Code: Select all

+-------------------+-------------------+-------------------+
 | 7     16    45    | 2     8     16    | 3     45    9     |
 | 19    3     45    | 45    7     19    | 2     8     6     |
 | 269   29    8     | 3     45    69    | 14    7     15    |
 +-------------------+-------------------+-------------------+
 | 3     2678  267   | 17    9     4     | 5     26    128   |
 | 689   4     679   | 157   25    27    | 169   3     18    |
 | 29    5     1     | 8     6     3     | 49    249   7     |
 +-------------------+-------------------+-------------------+
 | 1689  189   269   | 49    24    5     | 7     1269  3     |
 | 4     679   3     | 69    1     27    | 8     59    25    |
 | 5     12679 2679  | 679   3     8     | 69    1269  4     |
 +-------------------+-------------------+-------------------+


I have yet to implement my equivalent of ALS, but I intend to do so when I find the time in January.

[Bob Hanson]

thanks for this thread. I just realized the extension to "strong chains"
that will bring all this into Medusa.

r.e.s.: Those colorations are precisely what I realized myself this morning.
Of course! Why didn't I think of that.....

Stay tuned....

[rubylips]

Pep,

Your candidate grid allows an elegant Two-Sector Disjoint Subsets elimination:

Code: Select all

The cells r2c1 and r3c1 contain 1 value from {2,9} and 1 value from {1,6}.
The values 2 and 9 occupy 2 of the cells r2c1, r3c1 and r6c1 in some order.
The values 1 and 6 occupy 2 of the cells r2c1, r3c1 and r1c2 in some order.
- The moves r5c1:=9, r7c1:=9 and r3c2:=6 have been eliminated.


(You've already eliminated r3c2:=6). Then I think the next chain combination is best (ronk, please turn your monitor upside-down):

Code: Select all

Consider the chains r5c7=1=r3c9-<1|2>-r8c9-2-r8c6~7~r8c2, r5c7=9=r6c1-<2|1>-r2c1-1-r1c2~6~r8c2 and r5c7=9=r6c1=9=r3c2~9~r8c2.
Whichever of the 3 candidate values fills the cell r8c2, the cell r5c7 cannot contain the value 9.
- The move r5c7:=9 has been eliminated.
The cell r5c3 is the only candidate for the value 9 in Row 5.


The Almost Locked Sets used here are trivial. As described before, '=' represents an extended link.

[r.e.s.]

So now we have another use for the "law of leftovers"...

Exactly. It's probably worth mentioning that <the law of leftovers> is much more useful in the "jigsaw" (irregular boxes) type of sudoku.

[Lardarse]

But it also has other uses, particularly djape's "Butterfly" puzzles.

[Carcul]

Your candidate grid allows an elegant Two-Sector Disjoint Subsets elimination:

Code: Select all

The cells r2c1 and r3c1 contain 1 value from {2,9} and 1 value from {1,6}.
The values 2 and 9 occupy 2 of the cells r2c1, r3c1 and r6c1 in some order.
The values 1 and 6 occupy 2 of the cells r2c1, r3c1 and r1c2 in some order.
- The moves r5c1:=9, r7c1:=9 and r3c2:=6 have been eliminated.

This is a very nice example of a "Sue De Coq". But it would be nicer if these three eliminations could be expressed by some loops.

Good work Rubylips.

Regards, Carcul

[Jeff]

This is a very nice example of a "Sue De Coq". But it would be nicer if these three eliminations could be expressed by some loops.

Code: Select all

 +-------------------+-------------------+-------------------+
 | 7    *16    45    | 2     8     16    | 3     45    9     |
 |*19    3     45    | 45    7     19    | 2     8     6     |
 |*269   29    8     | 3     45    69    | 14    7     15    |
 +-------------------+-------------------+-------------------+
 | 3     2678  267   | 17    9     4     | 5     26    128   |
 |-689   4     679   | 157   25    27    | 169   3     18    |
 |*29    5     1     | 8     6     3     | 49    249   7     |
 +-------------------+-------------------+-------------------+
 |-1689  189   269   | 49    24    5     | 7     1269  3     |
 | 4     679   3     | 69    1     27    | 8     59    25    |
 | 5     12679 2679  | 679   3     8     | 69    1269  4     |
 +-------------------+-------------------+-------------------+

This Sue De Coq can be expressed as a continuous multiple nice loop:

-[r6c1]-9-[r3c1][r2c1]-1-[r1c2]-6-[r3c1]-2-[r6c1]-
implies r5c1<>9 and r7c1<>9 (Note: With continuous nice loops, eliminations are to be made outside the loops)

Alternatively, these eliminations can be expressed as a continuous triple implication chain:

Trivalue tripod at r3c1:
-[r3c1]-2-[r6c1]-9-[r3c1]-
-[r3c1]-2-[r6c1]-9-[r2c1]-1-[r1c2]-6-[r3c1]-
-[r3c1]-6-[r2c1]-1-[r2c1]-9-[r3c1]-
All imply r5c1<>9 and r7c1<>9 (Note: With continuous nice loops, eliminations are to be made outside the loops)

Alternatively, these eliminations can be expressed as discontinuous triple chains:

Trivalue tripod at r3c1:
[r5c1]-9-[r6c1]-2-[r3c1]-9-[r5c1]
[r5c1]-9-[r2c1]-1-[r1c2]-6-[r3c1]-9-[r5c1]
[r5c1]-9-[r6c1]-2-[r3c1]-6-[r1c2]-1-[r2c1]-9-[r5c1]
All imply r5c1<>9

Trivalue tripod at r3c1:
[r7c1]-9-[r6c1]-2-[r3c1]-9-[r7c1]
[r7c1]-9-[r2c1]-1-[r1c2]-6-[r3c1]-9-[r7c1]
[r7c1]-9-[r6c1]-2-[r3c1]-6-[r1c2]-1-[r2c1]-9-[r7c1]
All imply r7c1<>9