SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Almost Locked Candidates

 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips
View previous topic :: View next topic  
Author Message
Ron Moore
Addict
Addict


Joined: 13 Aug 2006
Posts: 72
Location: New Mexico

PostPosted: Tue Mar 20, 2007 12:47 am    Post subject: Almost Locked Candidates Reply with quote

Ruud mentioned the Almost Locked Candidates (ALC) technique in another post to this forum, but I couldn't quite figure out exactly what was meant from the discussion, so I consulted the Sudopedia and found that there was a page on the ALC technique (here). Below, I've only given the first three rows of the first example from that page. The assumptions are that the "/"cells contain neither X nor Y, and r1c4 and r2c1 are bivalued cells containing X and Y.

Code:

/  does not contain X or Y
.  may optionally contain X or Y or both

.-------------------.------------.----------.
| .     .     .     | XY  /   /  | /  /  /  |
| XY    *-XY  *-XY  | .   .   .  | .  .  .  |
| *-XY  *-XY  *-XY  | .   .   .  | .  .  .  |
.-------------------.------------.----------.

The argument seems to be that since r1c4 and r2c1 are Almost Locked Sets (ALS's) containing the exact same set of digits (X and Y), and since the slashed cells do not contain either X or Y, then an X or Y must end up somewhere in r1c123 so that the eliminations of X and Y shown in box 1 can be made.

These assumptions can be loosened quite a bit. The fact that r1c4 is an ALS in this example is unfortunate, as that fact diverts attention from the key point. It is important that r2c1 be an ALS to make this work. What's important about r1c4 is that it's a weak ALS which contains both X and Y. Readers not familiar with the "weak ALS" term or concept don't really need to understand it to follow most of this post, but here's a quick synopsis. I'm using Myth Jellies' term for the concept as he explained it in this thread and in more detail here. A set of N cells with N-1 digits locked into those cells is a weak ALS. The complementary set of unsolved cells in the house is always an ALS. In this case, r1c4 is the simplest form of a weak ALS, a single cell containing 0 locked digits. (The next step up would be a pair of cells containing 1 locked digit, which we normally call a conjugate pair for that digit).

Myth Jellies was kind enough to respond to my first significant post to this forum with some words of encouragement and a gentle suggestion that I begin using some formal notation and begin expressing my reasoning in terms of Alternating Inference Chains (AIC's) whenever possible. It took me a while to get started with that, but once I did, it was amazing how things started "clicking" for me. That was good advice.

So let's see if we can write an AIC which expresses what's going on here. The assumption that the slashed cells do not contain either X or Y means that we have some strong positional links:
Code:

   (X)r1c123 = (X)r1c4  and  (Y)r1c123 = (Y)r1c4

Actually X (or Y) might not exist as a candidate in all cells of r1c123, in which case a smaller node could be used, but that really makes no difference as the above assertions still hold true.

We can use these links in an AIC as follows:
Code:

   (X)r1c123 = (X-Y)r1c4 = (Y)r1c123 - (Y=X)r2c1

This is an AIC which begins and ends with a link of strong inference, so at least one of the starting or ending candidate premises must be true. In plain language, this just means that an X must lie in one of r1c123, or in r2c1. Thus, any cell which sees all of these cells must see an X and so cannot itself contain X. From this the eliminations of X in the starred cells in the diagram follow. Although the internal link between X and Y in r1c4 is a strong conjugate link in the diagrammed position, we are using this as a link of weak inference in the chain. The chain would still be valid if r1c4 contained other candidates, but in that case it wouldn't be an ALS. The chain does use the fact that the internal link in r2c1 between X and Y is a strong link, but this would still hold true if r2c1 were replaced by any ALS containing X and Y, disjoint from r1c123, in the box. (Actually there's a fine point here that I should mention. If X and Y appeared as candidates in only r1c12, for example, then the ALS could possibly contain r1c3. The Sudopedia presentation suggests that the ALS in the box must be disjoint from the line/box intersection. It only needs to be disjoint from the cells in the line/box intersection which contain X or Y.)

Now, we can argue that since everything is symmetrical with respect to X and Y in the chain, we can interchange X and Y in it to produce an AIC from which the eliminations of Y in the starred cells in the diagram follow.

However, alert readers will have already noticed that the above chain can be continued:
Code:

   (X)r1c123 = (X-Y)r1c4 = (Y)r1c123 - (Y=X)r2c1 - (X)r1c123

Now the chain has looped back to its starting point to form a closed cycle, in such a way that the alternation of links of strong and weak inference is continuously maintained around the cycle, so we have an AIC ring, or maybe some would say a continuous nice loop. Whatever you call it, we conclude that all links of weak inference in the cycle are actually strong conjugate links as well. From this, we immediately deduce the aformentioned eliminations of X and Y, but there is a bonus. Since the cycle shows that the internal link between X and Y in r1c4 is in fact a strong conjugate link, if there were any other candidates in r1c4, they could be eliminated.

Now, I previously commented that the above loop would still hold true if r2c1 were replaced by any ALS in box 1 containing X and Y (but disjoint from the cells in the line/box intersection containing X or Y) since there is a strong internal link between any two digits in an ALS. So next we might want to consider how we can generalize the role of r1c4. What's important, of course, is that there be a weak link between X and Y in some set. So in what type of sets can we say that such a weak link exists? Well, it just so happens that the weak ALS fits the bill, which makes Myth Jellies' name for the concept imminently sensible (no surprise there, of course). It is sufficient to assume that X and Y exist as candidates in the weak ALS, but that they are not among those digits which are locked in the set. (Actually, to be strictly precise, again we must also assume that the weak ALS is disjoint from the cells in the line/box intersection containing X or Y.) Since the weak ALS has room for exactly one non-locked digit, there must then be a weak link between X and Y in the weak ALS (they cannot both be present in it).

So to generalize the conditions which are sufficient for an ALC type elimination, one step forward might be something like this:

Suppose C is a set containing some or all of the cells lying in the intersection of a line and a box, D is a Weak ALS disjoint from C lying in one of those houses (call it house CD), and E is an ALS disjoint from C lying in the other house (call it house CE), and that there are two digits u, v such that
    both u and v are candidates in each of sets C, D, and E
      AND
    all u and v candidates in house CD lie in set C or D.
Then ...

Note that the assumptions that u and v exist in C, and that C and D are disjoint, means that u and v are not locked in D. I could continue with the conclusions to be drawn, and could give some examples, and will do so if anyone requests. (I won't promise to be timely about it, necessarily. If anyone feels they can and wants to continue with this, please feel free to do so. Just reply back here with your intent to do so.) I'm wondering if it's really worth the effort, though. Again I will say that if one is familiar with using AIC's with ALS's (and now weak ALS's might be occasionally helpful, too), then you've got many of the solution techniques covered, even if you don't know them by name. If we try to give a name to every class of position according to the particular arrangement of sets and links within it, we're going to generate a lot of terms, and since the same technique is often independently discovered by different individuals, there will be aliases for the same technique or concept. That's my problem when I try to study other forums.

I will comment that if the best possible use of the ALC technique is to be made in the general case, then the ALC conclusions must make mention of other digits besides u and v.

I will also add that I have convinced myself that any position which satisfies the above constraints for ALC eliminations also contains "2 ALS's with 2 restricted common digits" (as I discussed in my long-winded spiel in this thread). I will leave the proof of that as an exercise for the reader. (Hint: consider the set of unsolved cells complementary to D in house CD.) If any readers are wondering why I chose C, D, E and u,v as names for the key sets and digits here, I was just trying to avoid any possible confusion between the two posts.

So if you understand the ideas I presented in that spiel, you don't absolutely have to use the ideas behind ALC eliminations (and conversely). However, sometimes the alternate approach will involve smaller sets and will be easier to spot.
Back to top
View user's profile Send private message
Myth Jellies
Hooked
Hooked


Joined: 04 Apr 2006
Posts: 42

PostPosted: Tue Mar 20, 2007 4:02 pm    Post subject: Reply with quote

Nice deduction and presentation of the connection between the two concepts.
Back to top
View user's profile Send private message
Ron Moore
Addict
Addict


Joined: 13 Aug 2006
Posts: 72
Location: New Mexico

PostPosted: Wed Mar 21, 2007 3:46 pm    Post subject: Further Thoughts on ALC Reply with quote

[edit made for minor editorial correction in one example]

Well, I take it all back. Almost Locked Candidates is worthy of mention in its own right.

Of course, my first post in this thread does not address the position in the second example on the Sudopedia page, of which the first three rows are shown below. Just a note on the notation I'm using: I'm placing all of the eliminated digits after the "-" sign. When you see something something strange like XYZ-+ in a cell, I'm just trying to say that if the cell has surplus candidates beyond those explicitly listed, those can be eliminated. The eliminations of the surplus candidates in r1c4 and r1c5 are not shown in the Sudopedia example. Perhaps you can see this already, but if not, later on you'll understand.

Code:
  /  does not contain X, Y,or Z

.---------------------.-----------------.----------.
| .      .      .     | XYZ-+  XYZ-+  / | /  /  /  |
| XYZ    XYZ    *-XYZ | .      .      . | .  .  .  |
| *-XYZ  *-XYZ  *-XYZ | .      .      . | .  .  .  |
.---------------------.-----------------.----------.

I couldn't really come up with anything using AIC's to generalize the ideas in my first post to cover positions like this, or with even larger sets. But suddenly a thought struck me that there was a fairly simple way of viewing the situation. Although the general statement of this idea is a bit cumbersome, in practice it's often easy to apply since most of the sets involved become trivial. All we are trying to do is come up with some conditions in which one of the digits in the principal ALS (r2c12 in the above position) must be forced into the line/box intersection.

The basic principle which we use for identifying ordinary hidden n-tuples (hidden singles, pairs, triples ...) goes something like this: If n is some integer >=1, and if there is a set of n cells in some house, and a set of n digits such that for every digit d in that set, d appears as a candidate in only those n cells, then we have a hidden n-tuple and conclude that each of those n cells is forced to contain one of those n digits. We further conclude that any surplus candidates in any of the n cells may be eliminated.

Let's generalize the idea of "n cells" to "n nodes", where a node is a group of one or more cells in a house. As I'm using "node" here, the cells of a node do not necessarily have to lie within the same box, if we are speaking about nodes lying within a line, or within the same line if we are speaking of nodes lying within a box.

If there is a set of n nodes (n >= 2)in some house, with no two nodes sharing a common cell, and a set of n digits, such that for each digit d in that set, d appears as a candidate in only the cells of those n nodes, and furthermore, if it can be shown by hook or crook that each node can contain only one of the n digits, then each node must contain one of the n digits (in some unspecified position within the node).

For example, if a node consists of a single cell, then clearly it can contain only one of our n digits. (In practice, this will be the case for most of our nodes). More generally, if a node is a weak ALS, and none of our n subject digits are among its locked digits, then the weak ALS can hold only one of those n digits. So if all of our n nodes satisfy this constraint, then from each node its surplus candidates can be removed. In this context, for a weak ALS, a surplus digit is one which is neither one of its locked digits nor one of our n subject digits. This idea can be used on its own, independently of ALC positions, but I'm not sure -- the structure may always reduce to some hidden m-tuple anyway.

Now when we go to the ALC position, we add another node (the one in the line/box intersection) with a different reason why it can contain only one of our n digits -- because there is an ALS disjoint from the node which contains all n digits, and our node sees all cells of the ALS. (I suppose in principle there could be yet another node in a different line/box intersection which sees another ALS with all of our n digits, but at this point I've ignored this possibility in the following statement.)

As a first cut, I would propose something like the following as the statement of generalized ALC. It needs some more thought as I believe some of the requirements may be loosened.

*******************************************************

Suppose C is a set of some or all of the cells in the intersection of a line and a box, and suppose there is a set S of n digits (n >= 2) such that:

In one of the houses (the line or the box), there is an ALS which is disjoint from set C, and which contains every digit in S (and possibly other digits)
    AND
In the other house, there is a set of n pairwise disjoint nodes, with one of those nodes being the set C, such that for each digit d in S, all candidates for d lie within the cells of the n nodes; and, that with the exception of C, each node is a weak ALS whose set of locked digits is disjoint from S, and whose cells are disjoint from the line/box intersection.

Then:

In the house containing the ALS, each of the digits of the ALS can be eliminated from any cell which is neither in set C nor the ALS.
    AND
In the other house, from each node, with the exception of node C, any digit which is neither in the set S, nor one of the locked digits for that node (which is a weak ALS, remember), can be removed.

*******************************************************

As a practical tool, I expect this will be useful primarily when n = 2, or when n-1 or n-2 of the n nodes are single cells.

Some examples follow.

Code:

/ does not contain X or Y

.-------------------.--------------.----------.
| .     .     .     | XY-+  /   /  | /  /  /  |
| XY    *-XY  *-XY  | .     .   .  | .  .  .  |
| *-XY  *-XY  *-XY  | .     .   .  | .  .  .  |
.-------------------.--------------.----------.

n = 2, S = {X,Y}, C = r1c123 (or perhaps just those cells which contain X or Y)
In box 1, ALS = r2c1 with digits {X, Y} -- contains all digits of S
In row 1, node 1 = C, node 2 = r1c4

Code:

  /  does not contain X, Y,or Z

.---------------------.-------------.-------------.
| .      .      .     | XYZ-+  /  / | /  XYZ-+  / |
| XYZ    XYZ    *-XYZ | .      .  . | .  .      . |
| *-XYZ  *-XYZ  *-XYZ | .      .  . | .  .      . |
.---------------------.-------------.-------------.


n = 3, S = {X,Y,Z}, C = r1c123 (or perhaps just those cells which contain X, Y, or Z)
In box 1, ALS = r2c12 with digits {X,Y,Z} -- contains all digits of S
In row 1, node 1 = C, node 2 = r1c4, node 3 = r1c8

I'm sure you're getting the idea by now. If there happens to be an ALS with the n digits of S in the line (assuming the principal ALS is in the box), then we can take each of its n-1 cells as a node, along with C. If there are surplus candidates as above, we might consider the two cells r1c4 and r1c8 as containing a hidden ALS.

Here's an example with a less trivial weak ALS involved -- a conjugate pair. This is from one of Para's examples which I've mentioned elsewhere. (By the way, I'm not saying this is the best way to view this position. In practice I would never see things this way, but rather strictly with the ALS's in this position. So this is all after the fact for me. I even sometimes miss some of the easier ALC positions which Para seems to have a knack for finding. But he did raise the question as to whether this could be viewed from the ALC standpoint, and in fact it can.)

Code:

.------------------.------------------.-------------------.
| 128   28    5    | 147   347   1237 | 78    6      9    |
| 7     3     4    | 8     6     9    | 12    25     125  |
| 6     9     128  | 157   57    127  | 78    4      3    |
:------------------+------------------+-------------------:
| 238   4     2378 | 6     137   5    | 12    9      1278 |
| 5     78    3789 | 2     1379  4    | 6    B378    178  |
| 239   1     6    | 79    8     37   | 5    B37-2   4    |
:------------------+------------------+-------------------:
| 389   5     3789 | 479   2     6    | 49    1     A78   |
| 4     6     12789| 1579  579   178  | 3    C2578   25-78|
| 1289  278   12789| 3     457   178  | 49   C2578   6    |
'------------------'------------------'-------------------'


We can take:

n = 2, S = {7,8}, C = r89c8
in box 9, ALS = set A (r7c9) with digits {7,8} -- contains all digits of S
in column 8, node 1 = C, node 2 = B (r56c8), a weak ALS with 2 cells, 1 locked digit (3), locked digit disjoint from S
in column 8, all 7 and 8 candidates appear in node 1 or 2 (set C or B)

So ALC tells us that we can eliminate 7 and 8 in those cells of box 9 which are neither in A nor C, and that we can eliminate from set B any candidate which is neither in S (7 or 8) nor one of B's locked digits (3), so the 2 in r6c8 can be removed.

Now in all examples so far, the principal ALS has been in the box. For exercise you might want to see if you can work things out with the principal ALS as r2c8 in column 8, S = {2,5}, etc. It's actually easier that way.


Last edited by Ron Moore on Wed Mar 21, 2007 8:55 pm; edited 1 time in total
Back to top
View user's profile Send private message
SirDave
Rookie
Rookie


Joined: 03 Jan 2007
Posts: 6

PostPosted: Wed Mar 21, 2007 7:37 pm    Post subject: Reply with quote

Ron, these are terrific posts on ALSes, both here and in the 'Curious New Move' thread. Your interest in them is mirroring mine. I really think that ALSes have been neglected and along with Myth's AICs, both of which are ripe for just this sort of attention.

The only other in-depth discussions of ALSes was the original 'Almost Locked Sets For Now' in the Player's forum and then a flurry of activity on the subject over a few weeks last year by Anne Morelot in the U.K. forum (been wondering what happened to her- maybe Myth knows).

In any event, speaking of Anne, here is an example she posted of 'doubly-locked ALSes' (under Step 4 of her second post), a form of ALS you mentioned in the other thread (it shows eliminations consistent with all 3 conclusions you listed in the other thread):
http://www.sudoku.org.uk/discus/messages/29/1703.html?1156708750


Last edited by SirDave on Sat Mar 24, 2007 1:01 am; edited 1 time in total
Back to top
View user's profile Send private message
Myth Jellies
Hooked
Hooked


Joined: 04 Apr 2006
Posts: 42

PostPosted: Thu Mar 22, 2007 8:03 am    Post subject: Re: Further Thoughts on ALC Reply with quote

Ron Moore wrote:
Code:
  /  does not contain X, Y,or Z

.---------------------.-----------------.----------.
| .      .      .     | XYZ-+  XYZ-+  / | /  /  /  |
| XYZ    XYZ    *-XYZ | .      .      . | .  .  .  |
| *-XYZ  *-XYZ  *-XYZ | .      .      . | .  .  .  |
.---------------------.-----------------.----------.

I couldn't really come up with anything using AIC's to generalize the ideas in my first post to cover positions like this


An equivalent AIC would look something like

(Z=X&Y)r2c12 - (XorY)r1c123 = (X&Y-Z)r1c45 = (Z)r1c123 => AIC loop => r1c45 = XYZ and r1c123,r2c12 = Z

and a similar AIC loop exists starting with X and Y. (Perhaps there is a hub and rim in there somewhere.)

One can extrapolate this by adding an extra digits/cells to the ALS (outside of the row) and an equivalent number of extra cells in the row (outside of the box) exclusively containing the ALS digits. Obviously, one can also move the ALS out to the row (or a column) and put the exclusive cells in the box.

It would also work with an ALS in a column and the exclusive cells in a row, but then the exclusive cells actually form a hidden locked set, which when added to the ALS makes the ALS a naked locked set without any advanced logic. Thus this type of AIC or ALC requires a box-line or other multi-celled intersection.

At any rate, it all holds together whether you look at it from an AIC or ALC perspective. Choose whatever makes it easiest for yourself.
Back to top
View user's profile Send private message
Myth Jellies
Hooked
Hooked


Joined: 04 Apr 2006
Posts: 42

PostPosted: Fri Mar 23, 2007 4:21 am    Post subject: Reply with quote

Code:

You might find this interesting

 '/' does not contain X, Y,or Z
.---------------------.-----------------.----------.
| .      .      .     | XYZ*   XYZ*   / | /  /  /  |
| XYZ    XYZ    .     | .      .      . | .  .  .  |
| .      .      .     | .      .      . | .  .  .  |
.---------------------.-----------------.----------.

The ALC net loop above has the form

 (XorY)r1c123 ===================== (X&Y)r1c45
  |                                   |
(X&Y=X&Z=Y&Z)r2c12 - (YorZ)r1c123 = (Y&Z)r1c45
      |                               |
     (XorZ)r1c123 ================= (X&Z)r1c45

They are not exactly alike, but it is interesting
to note that the ALC looks like a simple expansion
of the similar simple triple spoke pattern shown below
.---------------------.-----------------.----------.
| .      .      .     | XYZ*   /      / | /  /  /  |
| XYZ    .      .     | .      .      . | .  .  .  |
| .      .      .     | .      .      . | .  .  .  |
.---------------------.-----------------.----------.

(X)r1c123 ======================= (X)hub_r1c4
 |                                 |
(X = Y = Z)AALS_rim - (Z)r1c123 = (Z)hub_r1c4
     |                             |
    (Y)r1c123 =================== (Y)hub_r1c4

The triple-spoke can also expand as follows...

.---------------------.-----------------.----------.
| .      .      .     | XYZ*   /      / | /  /  /  |
| WXYZ   .      .     | .      .      . | .  .  .  |
| WXYZ   .      .     | .      .      . | .  .  .  |
.---------------------.-----------------.----------.

     +--------------------------------------------------+
     |     +----------------------------+               |
     |     |                            |               |
  *(W&Z=XorY)AALS_rim     ----(Y)hub = (Y)r1c123 ----+  |
     |  |                /     |                     |  |
     | (X)r1c123 ===== (X)hub  |                 (ZorY=X&W)AALS_rim*
     |  |                \     |                  |     |
  *(W&Y=XorZ)AALS_rim     ----(Z)hub = (Z)r1c123 -+     |
     |     |                            |               |
     |     +----------------------------+               |
     +--------------------------------------------------+
The AALS rim here is r23c1.  Note that this three-spoked net has
endpoints (in rim) that all exclude each other

Thus r1c4 = XYZ
     r23c1 contains W
     r23c23 <> XYZ

Click for more on Multi-Spoke patterns
Back to top
View user's profile Send private message
Ron Moore
Addict
Addict


Joined: 13 Aug 2006
Posts: 72
Location: New Mexico

PostPosted: Fri Mar 23, 2007 8:34 pm    Post subject: Reply with quote

[edited to strengthen the basic principle]

Sir Dave and Myth,

Thanks for your comments and insight.

I did spend some time looking at Anne's thread, and all in all I was quite impressed. As Sir Dave noted, the initial posts in this thread occurred in a short burst, and I have to think she had more than one of these solved before she began posting. Her diagrams are very nice and just preparing them must have a been an effort in itself. Her work on # 5000 is most impressive. I did find one puzzle, # 49970, in which there are (at least) 3 XY chains in the initial position she shows. In keeping with her aim of limiting solutions to ALS arguments when possible, I suppose they could be viewed as ALS XZ or ALS XY wing positions, but for me it would be more natural to think of them as XY chains. I found that two of these, along with a naked triple, were sufficient to solve that puzzle.

More impressive are the more theoretical comments later in that thread. It would take me a while to absorb all that's there. So all in all it was an humbling experience. Of course, I can say the same after reading some of Myth's posts, including his responses in this thread. Very Happy I haven't tried to absorb his most recent.

I've given some more thought to generalizing the ALC idea, and it seems to be getting further and further away from the practical. So maybe just a few (more general) sample positions in the Sudopedia would be enough for the vast majority of puzzles.

From a theoretical standpoint, I think I am closing in on the idea, and I can express it more cleanly if I make a few simple definitions. You guys are familiar with several forums in the Sudoku world, so let me know if there is a more standard (or simply better) terminology. (Or if I'm trying to reinvent someone's wheel with all of this).

Definitions:
    1. If A is any set of cells, then D(A) will denote the set of all its candidate digits.

    2. If S is a set of digits, and A is a set of cells:

      If A can contain at most k of the digits of S, then let's say that A is (S,k) limited.

      If A must contain at least k of the digits of S, then let's say that A is (S,k) obligated.

      Of course, if A is (S, k) limited and (S, k) obligated, then it contains exactly k digits of S, and conversely.

    3. I'll use the term "degrees of freedom" as used on the Sudoku Players Forum thread on ALS rules which Sir Dave mentioned. If a set A is an Almost Almost ... Almost Locked Set, or A...ALS, whose candidate count exceeds its cell count by k, then A will be said to have k degrees of freedom.

    4. Similarly, if a set A is a Weak Weak ... Weak ALS, or W...W ALS, whose cell count exceeds its locked candidate count by k, then A will be said to have k degrees of freedom.

Examples:
    1. Trivially, if A consists of a single cell, then A is (S,1) limited for any set of digits S.

    2. Again trivially, if A contains m cells, then A is (D(A),m) obligated.

    3. As discussed in the "Curious New Move" thread, if A and B are two disjoint ALS's sharing two restricted common digits, say w and x, then A is both ({w,x},1) limited and ({w,x},1) obligated, and so is B.

    4. If A is an ALS, and B is any set of cells which sees A (meaning that each cell of B sees every cell of A), then B is (D(A),1) limited.

    5. More generally, if A is an A..ALS with k degrees of freedom, and B is any set of cells which sees A, then B is (D(A),k) limited.

    6. If A is a Weak ALS, and S is the set of candidate digits in the complementary ALS (i.e., precisely those digits which are not locked in A), then A must contain exactly 1 element of S (A is is both (S,1) limited and (S,1) obligated).

    7. More generally, if A is a W...W ALS with k degrees of freedom, and S is the set of digits in the complementary A...ALS (i.e., S contains precisely those digits not locked in A), then A must contain exactly k elements of S.

Then with these definitions we have the following principle (maybe some twist on the pidgeonhole principle, I don't remember):

Principle:

Suppose that S is a set of n digits, and that in some house, there are m nodes (not necessarily disjoint) C1, C2, ..., Cm (where m <= n), such that all occurrences of the digits in S are confined to the cells of those m nodes. If it is known that for each node Ci (1 <= i <= m), Ci is (S,ki) limited, where k1 + k2 + ... + km = n, then each Ci is also (S,ki) obligated, that is, Ci contains exactly ki elements of S. Furthermore, any digit of S can be eliminated from any cell common to two different nodes.

It may be possible to draw some conclusions from the fact that Ci must contain exactly ki elements of S, depending on the reason why it is known to be (S,ki) limited.

Suppose Ci was determined to be (S,ki) limited because it sees some set A which is an A..ALS with ki degrees of freedom, and A contains all digits of S (and possibly more). The principle tells us that Ci is also (S,ki) obligated. Thus Ci must contain ki candidates from S, so Ci will combine with A to form a locked set containing all digits of D(A). Thus, each digit in A may be eliminated from other cells in the house (that house which contains both Ci and A) which lie outside of both A and Ci.

Suppose Ci was determined to be (S,ki) limited because Ci is a W...W ALS with ki degrees of freedom, and whose locked digits are disjoint from S. The principle tells us that Ci is also (S,ki) obligated. So Ci must contain its set of locked digits and (exactly) ki digits from S. There is no room in Ci for any digit outside of its set of locked digits and outside of S, so any such surplus candidates can be removed from Ci.

Remark: Following the notion of "duality" which is discussed in Anne's thread, (and also in Bob Hanson's posts in the Sudoku Players Forum thread, I believe), it may be possible to apply the above principle to other sets, such as rows and columns for a single digit.
Back to top
View user's profile Send private message
SirDave
Rookie
Rookie


Joined: 03 Jan 2007
Posts: 6

PostPosted: Sat Mar 24, 2007 9:22 pm    Post subject: Reply with quote

An ALC example of an 'Elegant Contradiction'

I'm not a big fan of using contradictions, but if ever there was an example of an 'elegant contradiction', this is it. While checking out various ALSes in this 'diabolical', the following practically fell in my lap. The contradiction is so obvious, that I gave in and accepted it Very Happy :



Set A (light blue): r2c1, r3c1, r5c1 (4589)
Set B (green): r2c4, r3c4, r6c4 (4589)
Set C (pink): r6c2 (48)
x=8

Set C shares a restricted common, 8, with both Set A and B. If Set C, r6c2, is 8 then both r7c1 and r7c4 (brown cells) will equal 8 which is an impossible situation. Therefore r6c2 must equal 4 which solves the puzzle.

FWIW: There are, of course, a number of other ALSes in this puzzle.
Back to top
View user's profile Send private message
Para
Yokozuna
Yokozuna


Joined: 08 Nov 2006
Posts: 384
Location: The Netherlands

PostPosted: Sun Mar 25, 2007 12:16 am    Post subject: Reply with quote

Hi SirDave

This example is a sashimi x-wing/skyscraper on 8's. It's kinda obscured because of the ALS's, but when you check only the 8's you can make the same elimination. I don't know if you tend to use sashimi x-wing/skyscraper but it is an easier way to view this elimination.

greetings

Para
Back to top
View user's profile Send private message
SirDave
Rookie
Rookie


Joined: 03 Jan 2007
Posts: 6

PostPosted: Sun Mar 25, 2007 2:04 am    Post subject: Reply with quote

Para wrote:
Hi SirDave

This example is a sashimi x-wing/skyscraper on 8's. It's kinda obscured because of the ALS's, but when you check only the 8's you can make the same elimination. I don't know if you tend to use sashimi x-wing/skyscraper but it is an easier way to view this elimination.

greetings

Para


Thanks Para. Lately, I'm wholesale into all things ALS, so it's like when you have a hammer: everything looks like a nail. Ordinarily, I would have much preferred a solution such as yours, but I wasn't looking any further than ALSes when I came across the contradiction above and since it looked so pretty, I left it at that. What's particularly upsetting is in the recent past, I was into 'all things turbofish, skyscrapers etc.', but couldn't find hardly any of them in the puzzles I was trying and yet here is an absolutely beautiful one that you found in the puzzle above! Rolling Eyes

Anyway, it's such a good example of a skyscraper, I thought I'd highlight it, nice & pretty:



For those unfamiliar with skyscrapers, they are Havard's very clever description of a type of turbot fish aka sashimi x-wings (or variety thereof). I actually find his description & explanation easier to follow than the others.

In the above puzzle, the skyscraper (green) is row-based on 8s (it's lying on its left side). Either, r5c1 or r7c2 must be TRUE for 8, therefore any 8-containing cells 'seeing' both r5c1 and r7c2 can be eliminated. In this case, that means the 8s in the brown cells: r6c2 and r7c1 can be eliminated.
Back to top
View user's profile Send private message
rcbroughton
Expert
Expert


Joined: 15 Nov 2006
Posts: 143
Location: London

PostPosted: Sun Mar 25, 2007 9:17 am    Post subject: Reply with quote

Slightly off-topic, but in that position, isn't there a much more direct implication loop to set r5c1=8 based on conjugates pairs - X-chain or Simple Colouring?

r5c1<>8 -> r7c1=8 -> r8c2<>8 -> r8c5=8 -> r7c4<>8 -> r6c4=8 -> r6c2<>8 -> r5c1=8

deduction is therefore that r5c1 must be 8

Rgds
Back to top
View user's profile Send private message
SirDave
Rookie
Rookie


Joined: 03 Jan 2007
Posts: 6

PostPosted: Sun Mar 25, 2007 2:49 pm    Post subject: Reply with quote

rcbroughton wrote:
Slightly off-topic, but in that position, isn't there a much more direct implication loop to set r5c1=8 based on conjugates pairs - X-chain or Simple Colouring?

r5c1<>8 -> r7c1=8 -> r8c2<>8 -> r8c5=8 -> r7c4<>8 -> r6c4=8 -> r6c2<>8 -> r5c1=8

deduction is therefore that r5c1 must be 8


Nice alternative, but I wouldn't say more direct. IMO, Skyscrapers are nice patterns that stand out (well, at least to guys like Para- I missed it Sad ) and they are based on conjugate pairs. Plus, in this case, it solved 2 cells.

But 'nuff said, this is Ron's ALC thread- sorry Ron!
Back to top
View user's profile Send private message
rcbroughton
Expert
Expert


Joined: 15 Nov 2006
Posts: 143
Location: London

PostPosted: Sun Mar 25, 2007 4:19 pm    Post subject: Reply with quote

SirDave wrote:
Nice alternative, but I wouldn't say more direct.


Just meant by "direct" that it actually sets the digit at r5c1 in this step as opposed to the following step.

Just goes to show that there are always a number of ways to skin a cat. And, like you said, if you have a hammer . . .

Rgds
Richard
Back to top
View user's profile Send private message
Para
Yokozuna
Yokozuna


Joined: 08 Nov 2006
Posts: 384
Location: The Netherlands

PostPosted: Sun Mar 25, 2007 5:33 pm    Post subject: Reply with quote

Quote:

Anyway, it's such a good example of a skyscraper, I thought I'd highlight it, nice & pretty:



Actually i was talking about the skyscraper R57C1/R67C4 because you used those cells in your ALS deduction but this will do the same Wink

greetings

Para
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group