A study in Chain Forging: Page 5

Welcome back!

This proof continues on, and on, and on some more. You may need to refer to some previous pages of this proof to understand this page properly:

Two steps detailed on this page attack similar areas of the puzzle. Perhaps the general theme of this page is best described as generalized Almost AIC. In many ways, this is the most difficult page of this proof. Hopefully, I am equal to the task of detailing these two steps. One very important concept is theoretically detailed. It may well be the most important concept!

Appending Chains

The concept of appending chains is a very simple one. Suppose one has a theoretical chain:

A == B -- C == D
- => E is false

Suppose that F -- E. Then:

F == {A == B -- C == D}
- => E is false

Now, there is little value in this observation unless we have neither F for certain, nor {A == B -- C == D} for certain. In other words, if {A==B -- C==D} is an almost AIC, and appending F makes the entire chain valid, we clearly have also proven that E is false.

Perhaps this concept is best illustrated by example. Many of the techniques already illustrated in this proof can be viewed as appending chains. However, the following one is clearly best viewed that way.

Note: Forbidding matrices help derive not only this manner of chain appending, but also many others.

AIC == Single

AIC OR Single

Illustrated above is a very deep, but not very complex chain:

b2=1 ==₁ {a2=9 == c2=9 -- c5=9 == c5=8 -- c1=8 == c1=4 -- b2=4 ==₁ b2=3 -- ab1=3 == d1=3 -- d6=3 == d6=9 -- d9=9 == d9=1 -- d3=1 == b3=1}
- => b2=1 == {a2=9 == b3=1} => b23=1 == a2=9 => a2≠1

Suppose for a moment that cell c1 could still be 1. Then, it should be obvious that a2=1 would still be impossible, as c1=1 -- a2=1. In a similar fashion, if c3=1 were possible then a2=1 would still be impossible. In this way, most complicated AIC can be built from the concept of appending simpler chains. The value in this concept is that one can build theoretical chains of practically unlimited complexity from simple chains of little complexity.

Suppose again for a moment that c1 is limited to 148 rather than 48. One could write the following:

{pair 14 at b2,c1} ==₁ {a2=9 == c2=9 -- c5=9 == c5=8 -- c1=8 ==₁ b2=3 -- ab1=3 == d1=3 -- d6=3 == d6=9 -- d9=9 == d9=1 -- d4=1 == b4=1}
- => {pair 14 at b2,c1} == {a2=9 == b3=1} => a2≠1
  - Note: AALS can often be used in chains in a manner analgous to HAALS

A much simpler logical presentation (and thus easier on the mind) is possible:

c1=1 ==₂ {b2=1 ==₁ {a2=9 == c2=9 -- c5=9 == c5=8 -- c1=8 ==₂ c1=4 -- b2=4 ==₁ b2=3 -- ab1=3 == d1=3 -- d6=3 == d6=9 -- d9=9 == d9=1 -- d3=1 == b3=1}}
- => c1=1 == {b2=1 == {a2=9 == b3=1}} => b23,c1=1 == a2=9 => a2≠1

In a similar fashion, the chain can be further appended! One can, for instance, add 3 to d9. Clearly, d1=3 -- d69=3, thus the important conclusions of the macro chain will not be affected. In this manner, many ALS type configurations can be rewritten as nothing but simple bivalue, bilocation chains that are appended with information that is superfluous to the eliminations.

The Super Cell idea presented on the previous page can also be derived from merely appending theoretical chains. I am almost certain that, in fact, all techniques that do not use Uniqueness of Solution that can be derived from appending simple chains.

The idea of appending chains is simpler than the concept of branching. Start with a theoretical simple chain, see that it can be appended in various ways, derive theoretical complex chains. Knowing what these theoretically complex chains will look like, find them in puzzles. I find this a very simple, straightforward, albeit mathematical approach to unlocking very tough sudoku puzzles.

Enough of this heady? digression. Time for more examples!

A chain snippet leading to a certain elimination

Short chain piece

To the left, the newly created stronger 1's in column a are a certain part of a larger chain. I say this is certain, as all the additional information that this elimination requires was included in the previous step. However, I will present it in a slightly different fashion.

AIC == Chain snippet

AIC OR Single

Two ways to view this graphic will be presented. One is perhaps more typical, the other more intuitive. More typically, one might write:

a78=1 == a4=1 -- a4=4 == b46=4 -- b2=4 ==₁ {b2=1 ==₁ b2=3 -- ab1=3 == d1=3 -- d6=3 == d6=9 -- d9=9 == d9=1}
- => a8=1 == {b2=1 == d9=1} => b9≠1

AIC == Single

AIC OR Single

More intuitively the appended chain representation of the same elimination is:

b2=1 ==₁ {a78=1 == a4=1 -- a4=4 == b46=4 -- b2=4 ==₁ b2=3 -- ab1=3 == d1=3 -- d6=3 == d6=9 -- d9=9 == d9=1}
- => b2=1 == {a78=1 == d9=1} => b9≠1

Lately, I have grown to much prefer the latter presentation. Previously, I would have chosen the former. As time has gone by, I have come to regard appending of simple chains as the clearest way to find complex chains. In fact, since I have changed my thinking towards this concept, many chains that previously were difficult for me to find have become relatively easy. Not quite easy, but relatively easy.

Frustratingly enough, I have always had in my possession the tools to view complex chains this way. Unfortunately, the logic escaped me. A careful analysis of my own writings on topics such as Y Wing Styles practically begs this type of analysis. I can only plead ignorance for not previously, a long time ago, viewing complex AIC in this manner.

Back to the puzzle

After b9 ≠1, two cells finally solve. b9 = 6 %cell and c3 = 6 %grid.

Some locked candidate eliminations

Locked candidates 1,2

Illustrated above are two very easy steps.

b2=1 == b3=1 => c2≠1
a2=2 == c2=2 => i2≠2

Unfortunately, this puzzle is still not trivial!

This concludes the fifth page of this proof. It may feel like time to drink! However, if you are still sober minded, there remains a few more interesting steps that I would like to uncover. Find some of them on page 6 (viewing a strong link as an appendage through the use of a super cell).

3 Comments

Comments


Indicate which comments you would like to be able to see
GeneralJokesOther Sudoku Technique/QuestionRecipes

michael From paris france

Steve : I would like to be sure that I understand you here.
I thought at first you were saying this :
- if X is an Almost AIC, with y as the 'almost' element (ie ~y=>AIC)
- and if AIC=>z
- if F=>~y
- then F=>z.
Then I thought that you were saying this :
- if in an AIC chain which would imply z but for F, and if F=>z, then F is an appendage which can be ignored.
The point then being that through awareness of appendages one could identify them, ignore them and so simplify chains.
However I don't follow the initial presentation which seems to say :
- if chain=>~E
- and if F=>~E
- then ~F=>chain=>~E.
I think it must be implicit that the first step is
- if chain=>~E but for F.

If you could clarify for me, I'd be really grateful.

Also as a complete aside, what is your take on landing upon a contradiction ? I ask because :
I had a look earlier at the extreme sudoku 33 on sudoku.org.uk
At the possibility matrix stage I marked up the strong links in your manner, never having done that before.
This threw up one obvious enough line of attack for an AIC which removed a series of 8s. And in so doing gave an additional strong link in a cell, which then became a natural focus of attention.
Well whilst setting out on an AIC from this cell it became clear that depending on the route a certain cell would have two different values. Thus a contradiction, which completely opened up the puzzle, giving it on your Richter scale a poor ranking.

12/May/07 10:43 AM

Steve From Ohio Supporting Member
Check out my page

Reverse order first:
Happening upon a contradiction in the manner you choose is fantastic. If that happens to me, then I merely need to nail down the root causes of the contradiction, and write it as a chain.
The puzzle mark-up is not only the focus of potential AIC, but instead reveals likely building blocks for almost all possible techniques/ systems of attack one may employ upon the puzzle. This is because one of the building blocks for all such systems of attacks is the set of strong inferences.

I am trying to trave from general to specific above in the blog page.
Starting with a theoretical representation of a bivalue/bilocation AIC, one can easily see how if some extra possibilities existed that some of the conclusions of the AIC would not be effected. This is the root of the theory of appending chains.

The example I use most frequently is the derivation of the xyz wing from the xy wing. Adding the target of eliminations to the vertex of the xy wing preserves the ability to eliminate the target candidate from some of the original target cells. Thus:
{target candidate at vertex} == {XY wing}
is the XYZ wing.

Thus, is this case I am not advocating ignoring any canidates. Instead, I am presenting a system of technique derivation. Thus, some complex branching chains are viewed as not branching chains at all, but rather as merely:
Bichain == single(s).
If the single(s) is/are in certain rather obvious spots, they preserve/modify the strong inference conclusion.
Thus, singles added as extra endpoints to the chain tend to modify the conclusion. However, the conclusion is at least similar.
Singles added in other locations often do not modify the strong inference conclusion at all.

To apply this idea to actual puzzles is not difficult. The examples on the page are examples of the idea in use.

Extensions of the idea: merely replace the appendage {single} with a more complex appendage.

12/May/07 4:53 PM

Steve From Ohio Supporting Member
Check out my page

michael:
I do not specifically note that one can ignore the existence of certain appendages above. Hoever, this is a natural result of the analysis. One needs to know for what type/direction of deductions the appendage can be ignored.

12/May/07 5:09 PM

Please Log in to post a comment.

Not a member? Joining is quick and free. As a member you get heaps of benefits.

Join Now Login