almost-locked sets: generalization and strong chains

Advanced methods and approaches for solving Sudoku puzzles

almost-locked sets: generalization and strong chains

Postby Bob Hanson » Wed Dec 07, 2005 6:43 pm

OK, this posting shows that what I've been calling "strong chains" are
simply subsets of almost-locked sets. As a result, all 3D Medusa business
is subsumed under a generalized almost-locked set concept.

The two sorts of components comprising strong chains are 2-valued cells
such as {12} or {47}, and "conjugate pairs" -- exactly two possible
placements ("marks") for a certain candidate in a certain row, column, or
block. I sometime write 2-values cells like this:
Code: Select all
  1
   2

or this:
Code: Select all
  1
   \
    2

and I write conjugate pairs like this:
Code: Select all
 -1------1-

or this:
Code: Select all
  |
  1
  |
  |
  1
  |

OK, so the way these work is that a candidate can be "weakly linked" to them -- the "buddy" of one of the chain nodes. I write that like this:
Code: Select all
  |
  1........1*
  |
  |
  1
  |

So here, if the 1* is TRUE, then the top chain 1 is FALSE. And if the top chain 1 is TRUE, then the 1* is FALSE. That's a weak link.

I'll call these numbers -- the marks we pencil in -- "nodes."

OK, first thing, these are all just almost-locked sets. Obviously the Y-cycle 2-valued cells are; it may not be as obvious regarding conjugate pairs, but there the trick is to number the columns or rows -- say, "1 only in rows 3 and 5" amounts to {35} in almost-locked set notation.

Now, the weak link definition I gave yesterday applies here as well:

Node A is weakly linked to node B if they are "buddies" -- "in the same house" -- in the same row, column, or block. For single nodes, "Node A is weakly linked to node B" implies "Node B is weakly linked to node A."

A node A of candidate k is weakly linked to an almost-locked set if it is weakly linked to ALL of the nodes of that set.

An almost-locked set A is weakly linked to another almost-locked set B if ALL of the candidate k nodes of A are weakly linked to ALL of the candidate k nodes of B.

Notice that the concept of weak link is still reflexive. (Is that the right word?) A weakly linked to B implies B weakly linked to A.

Now, here's the kicker. We can write an almost-locked set like a branching chain:

{58 18}

is
Code: Select all
     1
     |
    / \
   5   8

and {58 18 186}

is
Code: Select all
     1
     |
  5--+--6
     |
     8

What's interesting to me (at least) is that these can now be plugged right
into the same sort of analysis I was doing with chains.

Here's an XY-wing in terms of simple Y-cycles:
Code: Select all
 2
 .3....3
 .      4
 .      .
 .      .
 2      .
  4.....*

* can't be 4.

And here it is in terms of almost-locked sets, where the left two
Y-cycle cells are combined into the almost-locked set A
where A={23 24}. B={34}, the mutual weak link is via 3.
Code: Select all
       3....3
      /      4
  2--A       .
      \      .
       4.....*

Same conclusion! (You can't have two weak links to the same
almost-locked set, because that would set too many nodes FALSE.)

Here's an XYZ-Wing:

Code: Select all
        3
        .\
        . 4
        . .
        . .
================
        . .
        . *
        . .
2......2. .
 \      3 .
  \      \.
   4......4


A 4 at * can be eliminated because, based on Y-cycles,
a 4 there would force both the 24 to be 2 and the 34
to be 3, and no 4 for the 234 cell. But that would
leave nothing for the 234 cell.

In almost-locked sets, we have:

Code: Select all
       3....3
      /      4
  2--A       .
      \      .
       4.....*

again. The same code!

So, basically what is going on is we are inserting this
fork-like structure into our standard picture of chains.

This, of course, could be extended to any number of
almost-locked sets interacting weakly with any number
of strong chains. Because strong chains are, in fact, just
sets of almost-locked sets!

Whereas for a chain we have:
Code: Select all
   X........a--A


where X is a candidate that is going to force a false and A true,
for almost-locked sets we have the same, but with a twist:

Code: Select all
           A
          /   
   Z..a--
          \   
           A


BOTH candidates A and B go true, thus allowing continued logical
implications along BOTH forks, provided there is weak linking from those
candidates to others.

The implication is clear: There are many, many applications of this
almost-locked sets idea, and, as I will propose NEXT, this in fact is probably all one needs to solve Sudoku, if you want to do it that way.
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Return to Advanced solving techniques