SudoCue Users

To get the ball rolling and to provide a thread for further discussion I am posting some initial thoughts on the quest for new killer methods which we can all contribute to. The need for this has arisen because of the limits we have currently reached when solving the Unsolvables by generally accepted methods.

On the subject of AIC (Alternate Inference Chains).

In a vanilla Sudoku with 17 or upwards givens there are usually some strong links present along with a vast number of weak links. By contrast for a killer in the early stages there are likely to be hardly any strong links to form chains, still less useful ones. The way we proceed at present, is to study the cage sum candidates and manipulate innies and outties to thin out the field.

When we start doing combination, or even permutation analysis, we begin to uncover additional relationships between cell candidates which are not part of the basic Sudoku structure. Some of these relationships can be expressed in the form of weak and strong links. Initially they will mostly be weak links, but slightly different than we are used to, in that they can simultaneously involve a change of cell and of candidate. The analogy here would be with the auxiliary chains that are already sometimes used to build up more complex chains and nets in vanilla Sudoku. As the solution process continues these weak links will either be annihilated or may get promoted to strong links.

By using some of the conclusions we reach from our cage analysis, expressed in the form of weak and strong links have a short hand way of recording intermediate findings. Then by using AIC methods we may be able to consider much more complex inter-cage relationships than be are able to do at present. These will undoubtedly be needed for some of the V3 and V4 level problems.

None of these methods should involve modification of the grid as the links are encapsulated in the formal structure, everyone is quite happy about links existing in vanilla Sudoku.

It may be interesting to look at Jean-Christophes' post "Chains & loops for Killer using AIC" which appears to already contain many of these ideas. (eg. either/or is translated into a strong link notation for assembly into a chain).

I'm sure the process will not be trivial, but hopefully it may be useful.

All the best,

Glyn

Thanks for this Glyn. I had forgotten about JC's post on adapting some methods for Killers. I am sure there is much to be gained from these so that we can avoid 'unacceptable' T&E in puzzles that may otherwise be unsolvable. I look forward to further discussions.

Note to self: Must try and make time to study AICs!

Hi all,

Glyn wrote:To get the ball rolling...

Thanks for the kick-off. Nice to have an informal thread where we can quickly discuss "bits and pieces" without having to invest the time to write up the equivalent of a formal paper on the subject.

Glyn wrote:On the subject of AIC (Alternate Inference Chains).

Just want to stress that this thread should be used for discussion of any advanced solving techniques useful in Killer Sudoku, not just chain-based ones.

Having said that, I indeed want to say something on the subject of:


Alternating Inference Chains

Glyn wrote:When we start doing combination, or even permutation analysis, we begin to uncover additional relationships between cell candidates which are not part of the basic Sudoku structure. Some of these relationships can be expressed in the form of weak and strong links. Initially they will mostly be weak links, but slightly different than we are used to, in that they can simultaneously involve a change of cell and of candidate.

Well said, Glyn. You hit the nail right on the head regarding your use of the word "Some" (which I have highlighted in bold above). AICs, as we've come to know and love (:-)) them from regular Sudoku, are exclusively based on two types of links between pairs on candidate premises:

• candidate premise 1 is true ---> candidate premise 2 is false (weak link)
• candidate premise 1 is false ---> candidate premise 2 is true (strong link)

Whilst this may be fully sufficient in the vanilla case, it is inadequate for Killer Sudoku. In Killer Sudoku (and also - to a lesser extent - in Jigsaw Sudoku), the other two possibilities are also relevant:

• candidate premise 1 is true ---> candidate premise 2 is true
• candidate premise 1 is false ---> candidate premise 2 is false

I refer to both of these as direct links (for reasons that will become apparent from the examples below).

For example, suppose we have an 11(2) and 6(2) cage sharing the same unit (row, column or box). If the 6(2) cage is assumed to be {15} (e.g. as an earlier link in the chain), then it is clear that the the 11(2) cage can contain neither a 5 nor a 6. Either the 5 or the 6 can then be used for an outgoing strong link originating from the 11(2) cage. But let's look at the relationship between the 5 and the 6 in more detail. This is an example of what Glyn refers to additional relationships uncovered by combinational and/or permutational analysis. It is neither a strong link nor a weak link. Rather it is a direct link. That is, if the candidate premise "11(2) contains a 5" is true, then the candidate premise "11(2) contains a 6" is also true. Likewise, if one of these candidate premises is false, the other must also be false.

This begs the question as to how one represents such a direct relationship in AIC (Eureka) notation. One way, which unfortunately does not work in all cases, is to simply omit the direct relationship. For example, if the 6(2) cage is at r3c12 and the 11(2) cage is at r3c78, and we want to use the 6 as an outgoing strong link from 11(2), we can write something like this:
This is what I assume Glyn means when he talks about a link (apparently) involving both a "change of cell and of candidate". I've added the word apparently here because the impression that there is a change of candidate merely arises due to the direct link between the 5 and 6 of the 11(2) cage having been omitted.

To represent direct links explicitly in Eureka notation, I propose the use of the comma operator, which I have already been using for quite a while. In other words, in order to retain the emphasis on the alternating nature of the chain, we effectively group together series of candidate premises with the same Boolean state (true or false) using a comma. In the above example, we would write:
Or (in shortened form, to avoid writing "r3c78" twice):
The more verbose form may be more useful if the two candidates concerned are not in the same cells of the cage. In our example, it may be that the 5 is only present in r3c7, and the 6 is only present in r3c8. If one therefore wanted to be more precise in this case (because, say, there is an outgoing strong link on 6 within column 8), one could write:
Note that the example used above is by no means the only type of direct link. Another example would be a "45 rule" where there is one innie and one outie. In this case, there is a direct relationship between the two cells of the form (where N can also be negative):

outie = innie + N

There is in theory nothing to stop such a direct relationship being used to form an AIC (e.g. incoming link on the innie cell on candidate digit D, outgoing link on outie cell on candidate digit (D+N)).

Yet another example, would be LoL, where it is known that two cells must map to each other, and thus must contain the same digit.

That's all I want to mention about AICs right now. Of course, there are loads of aspects relating to the use of AICs in Killers that I haven't even touched on. The purpose of this post is not to provide a tutorial on AICs in general, but rather to introduce and communicate the new idea of the direct link. I hope that I have succeeded in this goal, and that the post has been informative. BTW, don't be surprised if you can't find anything else on direct links anywhere on the Internet - it is an invention of my own!

A very interesting post Mike, thanks for pointing out that the full family of links is not quite as we know them. 99% of the time we make the assumption we are dealing with either the standard weak or strong links when the other two scenarios are possible. These direct links are usually only identified after a short chain is constructed in a vanilla puzzle but with a killer they may are intrinsic to the problem and may require a distinct notation that is far more concise than trying to skirt round the issue using extra standard links.

Your direct links are specifying a relationship that could be quite general, but that has been found to exist within the grid. I like the comma operator, in some ways it is similar in purpose to the '&' operator used by Myth to accumulate groupings for ALS, UR and the like; but has the advantage of allowing the order of candidate/cell placement to be specified as well.

Glyn wrote:These direct links are usually only identified after a short chain is constructed in a vanilla puzzle but with a killer they may are intrinsic to the problem and may require a distinct notation...

For the last few months, I've been coming round to thinking that it might be better to call these types of links neutral links, since they do not change the true/false polarity of the premise at the end of the chain.

In regular Sudoku, AICs are made up of strong and weak links in strictly alternating order. With Killers, the situation is considerably more complex. As in regular Sudoku, we can't follow a weak link (chain end polarity = false) with another weak link. Similarly, we can't follow a strong link (chain end polarity = true) with another strong link. But we can insert any number of neutral links in the chain, or at either end. The chain still alternates in polarity, but not with every link. To summarize:

• A weak link changes the chain polarity from true to false.
• A strong link changes the chain polarity from false to true.
• A neutral link retains the current chain polarity.

When building up a chain, we can append a weak link if the previous non-neutral link was strong, a strong link if the previous non-neutral link was weak, or a neutral link (always possible).

For example, the following sequence of link types is valid:

strong -> weak -> neutral -> strong -> neutral

Examples to follow.

P.S. Don't forget the golden rule! That is, no link in the chain should depend on side effects (typically, candidate eliminations) of any previous link in the chain. Such side-effect-free chains adhere to the principle of reversibility, which has several benefits, one of which is to serve as a protection mechanism against trial and error (T&E). If this rule is broken, and the chain is not very short, it is typically referred to this on these forums as tryfurcation.

I wrote:Examples to follow.

Here's the first one, namely step 8c in Afmob's A2X walkthrough.

Afmob was wondering whether this step is a Killer XY-Wing.

An XY-Wing, where the three cells A, B and C contain the candidates {xz}, {xy} and {yz}, can be represented by the AIC:
In other words, either cell A contains the candidate z, OR...

...it does not contain candidate z => it contains candidate x (strong link, bivalue cell A)
-> cell B does not contain candidate x (weak link across unit containing cells A and B)
=> cell B contains candidate y (strong link, bivalue cell B)
-> cell C does not contain candidate y (weak link across unit containing cells B and C)
=> cell C contains candidate z (strong link, bivalue cell C)

Thus, (even) if cell A does not contain the candidate z, cell C must contain it. So we can remove candidate z from all common peers of A and C.

Note from the above that an XY-Wing consists of 3 strong links and 2 weak links in the following classical AIC sequence:
A Killer XY-Wing is based on the same principle as an XY-Wing, except at least one of the bivalue cells is replaced by a cage.

Let's now have a look at Afmob's step 8c. Here is the grid state immediately prior to this move:
At this stage, the 10(3) cage at R5C123 can be one of {136/145/235}, and the split 7(2) cage at R5C5+R6C4 is either of [52/61].

The logic used by Afmob was:

Afmob wrote:8c) ! Consider placement of 6 in R5 -> R6C123 <> 1
- i) 6 in 10(3) @ N4 = {136} -> R6C123 <> 1
- ii) 6 in 10(3) @ N5 = {136} -> R6C4 = 1 -> R6C123 <> 1

Using the comma notation for neutral links, this can be expressed in AIC form as:
That is, either cell R5C123 contains a 1, OR...

...it does not contain candidate a 1 -> it also does not contain a 6 (neutral link, combinations 10(3) cage)
=> R5C5 contains a 6 (strong link, R5)
-> R6C4 contains a 1 (neutral link, combinations split 7(2) cage)

Thus, either R5C123 or R6C4 must contain a 1. So we can remove candidate 1 from all common peers of R5C123 and R6C4 (namely R6C123).

Note that, unlike an XY-Wing (see above), only 3 links (instead of 5) are involved here:
So although this step is not (strictly speaking) a Killer XY-Wing, it is actually a considerably simpler move, and in fact one of the simplest Killer chain-based moves possible. The only even simpler chain would consist of 1 strong link and 1 neutral link. Maybe I can find a practical example of that sometime...

I wrote:So although this step is not (strictly speaking) a Killer XY-Wing, it is actually a considerably simpler move

I forgot to mention that JSudoku would refer to this as a Locked Cages move, which I understand that the upcoming version of SudokuSolver will also support.

Here's a move that I used a few times in A84 and its V2.

Pattern definition:

Cage A and cage B are located in a single house. Digit X can only be placed in one of these two cages within that house. Digit Y is a digit which must also be placed in cage A, when X is placed.

Theorem:

If the pattern definition is present, you can eliminate all combinations from cage B which do contain digit Y, but not X.

Proof:

If digit X is located in cage A, it is paired with digit Y.
If digit X is not located in cage B. it must be in A, therefore digit Y must also be in A.

Remarks:

This technique depends on the pairing of digits, so it is useful to check when cage A has size 2.

I haven't seen this technique implemented in any of the computer solvers, but maybe it's already known in the solving community. I cannot think of a suitable name for it, so a little help is appreciated.

It is possible to expand this technique. When the placement of digit X in cage A always forces a placement of digit Y OR Z, cage B cannot contain a combination of Y and Z which does not include X.

Ruud

Ruud wrote:Here's a move that I used a few times in A84 and its V2.

Nice work, Ruud!

I would just like to add:

• A and B do not necessarily need to be contained fully within a single house, provided that no cell outside of the house can contain the digit Y.
• A and B may overlap, provided that no cell within the overlapping region can contain the digit Y.

Ruud wrote:I cannot think of a suitable name for it, so a little help is appreciated.

Although it's not a totally intuitive name, Jean-Christophe has already introduced the name "Locked Cages" for this type of situation here:

Jean-Christophe wrote:Added Locked Cages solver. It will search for some candidate for some house locked in two sum cages and consider the implications...

The term "implications" is fairly vague, and could be taken to also accommodate the interactions you mentioned, as well as the usual case where both cages must contain digit Y if they contain digit X, thus allowing digit Y to be eliminated from all common peers of all candidate positions for Y in both cages.

Note that there's also a third variety, where:

• Cage A must contain the digit Y if it contains digit X, and...
• Cage B must contain the digit Z if it contains digit X

In this case, the cells containing Y and Z can be considered to form a hidden constraint cage with an unknown sum, but known to contain at least one of {YZ}. This hidden constraint cage can then block combinations in other cages within the house that contain both of {YZ}, or even form a killer pair with a bivalue cell containing the candidates {YZ}.