The New Sudoku Players' Forum

[Bob Hanson]

Sudoku Assistant, http://www.stolaf.edu/people/hansonr/sudoku
is now programmed to find simple almost-locked sets. In this configuration:

Code: Select all

   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |     4 |    89 |  3789 ||     2 |     1 |    58 ||    35 |     6 |    79
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |    19 |    16 |   369 ||    39 |     7 |    45 ||  1345 |     8 |     2
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |  1789 |     5 |     2 ||    39 |     6 |    48 ||   134 |    13 |    79
===========================||=======================||=======================
r4 |     5 |    28 |     1 ||     6 |    38 |     9 ||     7 |    23 |     4
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |     6 |     7 |    48 ||    14 |    38 |     2 ||    13 |     9 |     5
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |     3 |    29 |    49 ||    14 |     5 |     7 ||     8 |    12 |     6
===========================||=======================||=======================
r7 |  1789 |    16 |  6789 ||    78 |     4 |    16 ||     2 |     5 |     3
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |    17 |     3 |   567 ||    57 |     2 |    16 ||     9 |     4 |     8
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |     2 |     4 |    58 ||    58 |     9 |     3 ||     6 |     7 |     1
-----------------------------------------------------------------------------


It found this one:

Code: Select all

   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |     4 |    89 |  3789 ||     2 |     1 |    58 ||    35 |     6 |    79
               A x    z                         A        A
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |    19 |    16 |   369 ||    39 |     7 |    45 ||    45 |     8 |     2
       B x     B      B  x
===========================||=======================||=======================
A={89 58 35}
B={19 16 369}
x=9 (weak link)
z=3 (common, can be eliminated)


           8
(r1c3)     |    {89 58 35}
    3...3--A--5
     .     |
      3    9
      |   .
  1---B--9
      |    {19 16 369}
      6



But here's another that is already doubly weakly linked

Code: Select all

   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |     4 |    89 |  3789 ||     2 |     1 |    58 ||    35 |     6 |    79
               Bxx      **
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |    19 |    16 |   369 ||    39 |     7 |    45 ||    45 |     8 |     2
       A x               *
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |   789 |     5 |     2 ||    39 |     6 |    48 ||   134 |    13 |    79
      A xx
===========================||=======================||=======================
r4 |     5 |    28 |     1 ||     6 |    38 |     9 ||     7 |    23 |     4
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |     6 |     7 |    48 ||    14 |    38 |     2 ||    13 |     9 |     5
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |     3 |    29 |    49 ||    14 |     5 |     7 ||     8 |    12 |     6
===========================||=======================||=======================
r7 |   789 |    16 |   789 ||    78 |     4 |    16 ||     2 |     5 |     3
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |    17 |     3 |   567 ||    57 |     2 |    16 ||     9 |     4 |     8
       A
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |     2 |     4 |    58 ||    58 |     9 |     3 ||     6 |     7 |     1
-----------------------------------------------------------------------------


[/quote]

In chain notation, the situation is:

Code: Select all

        .8
       .  \
      8    9
      |   .
  1---+--9
      |
      7


Since the two chains are mutually weakly linked, together they are
essentially "locked" on 8 and 9, and they act just like a naked 89 89
pair -- all other 8s an 9s weakly linked to both A and B can be eliminated.

I should note that only one case in the top95 puzzles was solved just
with "standard methods"+"almost-locked sets" (in this direction, at least,
I don't know yet about X-cycles).

That's #14:

http://www.stolaf.edu/people/hansonr/sudoku?LOAD=top95.14

Here's what it found in snapshot #29:

A={26 23}
B={79 39 679}
x=3 (weak link)
z=6 (can be eliminated)

[ronk]

Code: Select all

A={89 58 35}
B={19 16 369}
x=9 (weak link)
z=3 (common, can be eliminated)

           8
(r1c3)     +    {89 58 35}
    3---3++A++5
     \     +
      3    9
      +   /
  1+++B++9
      +    {19 16 369}
      6




Aside 1: The dots are hard to see, so I substituted other characters (plus, minus, and "slanted minuses") to see what it looks like.

Nice way to look at it Almost Locked Sets. For this example: Because of the weak link, both Almost Disjoint Sets (ADS) cannot contain a 9 and then -- because of either "ADS link" or both -- at least one ADS must contain a 3, eliminating 3s in any cells that are weakly linked to those 3s. That's reminiscent of one of the coloring rules.

AFAIK all of the examples by bennys have been restricted to almost locked sets with a special property, i.e, exactly two digits appear in the set exactly once. Your example does not rely on that restriction.

Aside 2: I'm already getting tired of the verbosity of "Almost Locked Set", "Conditional Disjoint Subset", and probably a few others already forgotten ... so I thought it's time ... time for an acronym, that is. AFAIK bennys originated the almost locked set approach, so in his honor, ALS would be an obvious choice, but ALS is the very commonly known acronym for Lou Gehrig's disease ... so that would be a bad choice IMO.

rubylips coded the Almost Locked Set appproach early, either independently or in conjunction with bennys' work, and is using the term Conditional Disjoint Subsets. Aaargh, that's eight syllables compared to bennys' four ... and four of those are in "conditional" ... so "conditional" is out. And "subset"? Gee, everything is a subset of something, and "sub" only has meaning in a localized context, so "sub" is out. That leaves "Almost Disjoint Set", five syllables, and hopefully ADS isn't another disease.

[Bob Hanson]

It's the nature of distributed thinking that multiple terms will arise for the same thing. Chemistry is CERTAINLY like that. Drives some people crazy; I just accept it. Personally, though, I just hate acronyms. Maybe it's because in my line of work there are so many, I'm just sick of them. Or, maybe because it adds one more level of jargon that "students of Sudoku" have to learn. So I'll stick with almost-locked sets. But ALS or CDS or ADS might all work.

Notation -- I've found this simple typographic notation works well for me. I agree the periods are hard to see, but I sort of like that -- they are supposed to be "weak". But I see your point.

The multiple weak link idea has several other implications as well, I think.

I guess I'm a bit disappointed that after adding these to Sudoku Assistant there wasn't any significant improvement in the top95 set. But I still have to add this in the single-candidate "plane" (thinking 3D here). Has anyone done that already?

I really like the way it explains the XYZ-Wing. Previously I had only conceptualized XYZ-Wings in terms of raw trial and error. Now I need to change http://www.stolaf.edu/people/hansonr/sudoku/explain.htm !

[bennys]

Bob Hanson wrote:

I guess I'm a bit disappointed

I think it is expected.
If in any argument more then two units are involved we will not be able to solve it that way.Thats the reason that I added the sets xy wing rule that takes us to 3 units.

[rubylips]

I should note that only one case in the top95 puzzles was solved just with "standard methods"+"almost-locked sets"

I don't agree with this - I found the pattern in several puzzles, such as #4.

Code: Select all

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

    4      8    7 |   3    12   12 |  56   9  56
   59    359   39 |   6    48   48 |   2   7   1
    1      2    6 |  57     9   57 |   3   8   4
------------------+----------------+------------
    7     34    5 |  89   348  489 |   1   6   2
   69  13469  349 |   2  1346   57 |   8  34  57
   28   1346   28 |  57  1346   14 |  57  34   9
------------------+----------------+------------
   58     45    1 |  48     7    6 |   9   2   3
    3     67   89 |   1    28  289 |   4   5  67
  269   4679  249 |  49     5    3 |  67   1   8

Consider the cell r7c1.
When it contains the value 5, the values 6 and 9 in Column 1 must occupy the cells r2c1 and r5c1 in some order.
When it contains the value 8, the value 9 in Box 7 must occupy the cell r8c3.
Whichever value it contains, the cells r8c1 and r9c1 cannot contain the value 9.
- The move r9c1:=9 has been eliminated.
Consider the cell r8c3.
When it contains the value 9, the values 3 and 4 in Column 3 must occupy the cells r2c3 and r5c3 in some order.
When it contains the value 8, the values 4 and 5 in Box 7 must occupy the cells r7c1 and r7c2 in some order.
Whichever value it contains, the cells r7c3 and r9c3 cannot contain the value 4.
- The move r9c3:=4 has been eliminated.
The cell r5c3 is the only candidate for the value 4 in Column 3.


(Of course, the first observation isn't necessary in order to solve the puzzle). Perhaps your solver applies its methods in a different order to mine.

You are right to highlight the 17-cell puzzle #14, which contains examples of several interesting patterns.

Code: Select all

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

      3      5     6 |    18    7    18 |  2    9    4
     29     79   279 |    36    4    36 |  8    5    1
      8      4     1 |     9    5     2 |  7    3    6
---------------------+------------------+-------------
     26      1    23 |     4   36     5 |  9   78   78
      7     39     4 |   138  139  1389 |  6    2    5
    569    689   589 |     2   69     7 |  4    1    3
---------------------+------------------+-------------
    169      2  3789 |  1367  139  1369 |  5    4  789
  14569    679   579 |   167    8  1469 |  3   67    2
    469  36789  3789 |     5    2  3469 |  1  678  789

Consider the cell r5c2.
When it contains the value 9, the values 6 and 7 in Column 2 must occupy the cells r2c2 and r8c2 in some order.
When it contains the value 3, the values 2 and 6 in Box 4 must occupy the cells r4c1 and r4c3 in some order.
Whichever value it contains, the cells r4c2 and r6c2 cannot contain the value 6.
- The move r6c2:=6 has been eliminated.
The value 6 in Box 7 must lie in Column 2.
- The moves r7c1:=6, r8c1:=6 and r9c1:=6 have been eliminated.
The value 6 in Box 8 must lie in Row 7.
- The moves r8c4:=6, r8c6:=6 and r9c6:=6 have been eliminated.


Here, the Condistional Disjoint Subsets pattern has helped, but to sufficiently to make the next move. However, a short chain with an Extended Disjoint Subset Link does the trick.

Code: Select all

     3      5     6 |    18    7    18 |  2    9    4
    29     79   279 |    36    4    36 |  8    5    1
     8      4     1 |     9    5     2 |  7    3    6
--------------------+------------------+-------------
    26      1    23 |     4   36     5 |  9   78   78
     7     39     4 |   138  139  1389 |  6    2    5
   569     89   589 |     2   69     7 |  4    1    3
--------------------+------------------+-------------
    19      2  3789 |  1367  139  1369 |  5    4  789
  1459    679   579 |    17    8   149 |  3   67    2
    49  36789  3789 |     5    2   349 |  1  678  789

Consider the chain r7c5~1~r7c1=<9|1>=r8c4.
When the cell r7c5 contains the value 1, so does the cell r8c4 - a contradiction.
Therefore, the cell r7c5 cannot contain the value 1.
- The move r7c5:=1 has been eliminated.
The cell r5c5 is the only candidate for the value 1 in Column 5.


When r7c1 contains a 9, the almost-locked set {r8c2,r8c3,r8c4,r8c8} locks, which forces r8c4 to take a 1. The link allows 1 to be removed as a candidate from r7c4, r7c6 and r8c1. The cell r7c5 has been chosen first as it allows a move to be made directly afterwards. Further application of the link allows progress to the following position, where a two-sector disjoint subsets pattern solves the puzzle.

Code: Select all

Consider the chain r9c2~9~r5c2-9-r5c6-9-r6c5-9-r7c5~9~r7c9-9-r9c9.
When the cell r9c2 contains the value 9, so does the cell r9c9 - a contradiction.
Therefore, the cell r9c2 cannot contain the value 9.
- The move r9c2:=9 has been eliminated.
Consider the chain r8c1-1-r7c1=<9|1>=r8c4.
When the cell r8c1 contains the value 1, so does the cell r8c4 - a contradiction.
Therefore, the cell r8c1 cannot contain the value 1.
- The move r8c1:=1 has been eliminated.
The cell r7c1 is the only candidate for the value 1 in Column 1.

     3     5     6 |   18   7   18 |  2    9    4
    29    79   279 |   36   4   36 |  8    5    1
     8     4     1 |    9   5    2 |  7    3    6
-------------------+---------------+-------------
    26     1    23 |    4  36    5 |  9   78   78
     7    39     4 |   38   1  389 |  6    2    5
   569    89   589 |    2  69    7 |  4    1    3
-------------------+---------------+-------------
     1     2  3789 |  367  39  369 |  5    4  789
   459   679   579 |   17   8  149 |  3   67    2
    49  3678  3789 |    5   2  349 |  1  678  789

The cells r8c1, r8c2 and r8c3 contain the value 5, 1 value from {6,7} and 1 value from {4,9}.
The values 5, 6 and 7 occupy 3 of the cells r8c1, r8c2, r8c3 and r8c8 in some order.
The values 4, 5 and 9 occupy 3 of the cells r8c1, r8c2, r8c3 and r9c1 in some order.
- The moves r8c4:=7, r7c3:=9 and r9c3:=9 have been eliminated.
The value 1 is the only candidate for the cell r8c4.


Throughtout, patterns have been sought in the order:
- Two-Sector Disjoint Subsets
- Conditional Disjoint Subsets
- Many-Valued Chains

It isn't ever necessary to use Two-Sector or Conditional Disjoint Subsets because they're just special examples of Chains patterns that are easier for humans to spot.

[ronk]

However, a short chain with an Extended Disjoint Subset Link does the trick.

Code: Select all

     3      5     6 |    18    7    18 |  2    9    4
    29     79   279 |    36    4    36 |  8    5    1
     8      4     1 |     9    5     2 |  7    3    6
--------------------+------------------+-------------
    26      1    23 |     4   36     5 |  9   78   78
     7     39     4 |   138  139  1389 |  6    2    5
   569     89   589 |     2   69     7 |  4    1    3
--------------------+------------------+-------------
    19      2  3789 |  1367  139  1369 |  5    4  789
  1459    679   579 |    17    8   149 |  3   67    2
    49  36789  3789 |     5    2   349 |  1  678  789

Consider the chain r7c5~1~r7c1=<9|1>=r8c4.
When the cell r7c5 contains the value 1, so does the cell r8c4 - a contradiction.
Therefore, the cell r7c5 cannot contain the value 1.
- The move r7c5:=1 has been eliminated.
The cell r5c5 is the only candidate for the value 1 in Column 5.


When r7c1 contains a 9, the almost-locked set {r8c2,r8c3,r8c4,r8c8} locks, which forces r8c4 to take a 1. The link allows 1 to be removed as a candidate from r7c4, r7c6 and r8c1. The cell r7c5 has been chosen first as it allows a move to be made directly afterwards. Further application of the link allows progress to the following position, where a two-sector disjoint subsets pattern solves the puzzle.

An alternate view ...

Code: Select all

 *--------------------------------------------------------------------*
 | 3      5      6      | 18     7      18     | 2      9      4      |
 | 29     79     279    | 36     4      36     | 8      5      1      |
 | 8      4      1      | 9      5      2      | 7      3      6      |
 |----------------------+----------------------+----------------------|
 | 26     1      23     | 4      36     5      | 9      78     78     |
 | 7      39     4      | 138    139    1389   | 6      2      5      |
 | 569    89     589    | 2      69     7      | 4      1      3      |
 |----------------------+----------------------+----------------------|
 |@19     2      3789   | 1367   139    1369   | 5      4      789    |
 | 1459  !679   !579    |!17     8      149    | 3     !67     2      |
 | 49     36789  3789   | 5      2      349    | 1      678    789    |
 *--------------------------------------------------------------------*

 ! A = {r8c2,r8c3,r8c4,r8c8} = {15679}
 @ B = {r7c1} = {19}
   x = 9
   z = 1

Therefore, excluding sets A and B, candidate 1 may be eliminated from the intersection of box 7 and row 8, i.e., r8c1.


Is an Extended Disjoint Subset Link really required to apply bennys' Almost Locked Set xz rule?

[Bob Hanson]

OK, I see what I did. I used the wrong list to compare. Here are the data I
get comparing the almost-locked sets idea, all with top95. Three puzzles
were solved using almost-locked sets that otherwise would have involved
3D Medusa with weak links. This makes sense, because technically
almost-locked sets are an extension of weakly linked chains. In one case,
#14, the implementation of almost-locked sets allowed the puzzle to be
solved without hypothesis and proof.

Code: Select all

top95#   without ALS   with ALS
-------------------------------
 4         M            A
14        WMP           AWM
74         M            A
76         M            A


A: Almost-locked sets
M: 3D Medusa
W: grid analysis (X-Wings, Swordfish, etc.)
P: hypothesis and (dis)proof

There are many other examples of the use of almost-locked sets in the
top95 set. But except for these four, the implementation of almost-locked sets doesn't remove the need to use other "more complicated" methods.

references:

http://www.stolaf.edu/people/hansonr/sudoku?LOAD=top95.4
http://www.stolaf.edu/people/hansonr/sudoku?LOAD=top95.14
http://www.stolaf.edu/people/hansonr/sudoku?LOAD=top95.74
http://www.stolaf.edu/people/hansonr/sudoku?LOAD=top95.76

and

http://www.stolaf.edu/people/hansonr/sudoku?LOAD=top95

I implemented the X-equivalent of almost-locked sets and found no
improvement whatsoever. There's probably not much to be gained by
that extension.

If I get the chance, I'd like to implement almost-locked sets as a full extension of chains. This might be a bit tricky, but I'll be interested in
how it goes. My guess is that that is what will be really powerful, because
it will open up the entire X-cycle/Y-cycle/3D-Medusa business to include
this sort of link.

I think it is expected.
If in any argument more then two units are involved we will not be able to solve it that way.Thats the reason that I added the sets xy wing rule that takes us to 3 units.

I'll look that one over and see what that's all about. I suspect it would be
the sort of thing that would be included in a full mix of strong chain/
almost-locked sets treatment (which would incorporate any number of
weakly linked units.