SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net

Author Message
Glyn
Major Major Major

Joined: 16 Jan 2007
Posts: 92
Location: London

CathyW
Master

Joined: 31 Jan 2007
Posts: 161
Location: Hertfordshire, UK

 Posted: Thu Aug 30, 2007 3:27 pm    Post subject: 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!
mhparker
Grandmaster

Joined: 20 Jan 2007
Posts: 345
Location: Germany

Posted: Fri Aug 31, 2007 10:46 am    Post subject:

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:

 Code: ...=(5)r3c12-(6)r3c78=...

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:

 Code: ...=(5)r3c12-(5)r3c78,(6)r3c78=...

Or (in shortened form, to avoid writing "r3c78" twice):

 Code: ...=(5)r3c12-(5,6)r3c78=...

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:

 Code: ...=(5)r3c12-(5)r3c7,(6)r3c8=...

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!
_________________
Cheers,
Mike
Glyn
Major Major Major

Joined: 16 Jan 2007
Posts: 92
Location: London

 Posted: Fri Aug 31, 2007 6:59 pm    Post subject: 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._________________I have 81 brain cells left, I think.
mhparker
Grandmaster

Joined: 20 Jan 2007
Posts: 345
Location: Germany

Posted: Sun Dec 16, 2007 11:13 am    Post subject:

 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.
_________________
Cheers,
Mike
mhparker
Grandmaster

Joined: 20 Jan 2007
Posts: 345
Location: Germany

Posted: Sun Dec 16, 2007 4:15 pm    Post subject:

 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:

 Code: (z=x)A-(x=y)B-(y=z)C

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:

 Code: strong - weak - strong - weak - strong

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:

 Code: .-----------------------.-----------------------.-----------.-----------------------.-----------------------. | 123456789   123456789 | 1234567     345689    | 123789    | 124567      123456789 | 123456789   12456789  | |           .-----------'-----------.           |           |           .-----------'-----------.           | | 123456789 | 123456789   456789    | 345689    | 123789    | 124567    | 123456789   12456789  | 123456789 | :-----------:           .-----------'-----------:           :-----------'-----------.           :-----------: | 1234567   | 56789     | 1234567     34568     | 789       | 124567      124567    | 56789     | 12345678  | |           '-----------:           .-----------'-----------+-----------.           :-----------'           | | 456789      456789    | 456789    | 12          56        | 3         | 1245679   | 12456789    12456789  | :-----------------------'-----------:           .-----------+-----------+-----------'-----------------------: | 123456      123456      23456     | 7         | 56        | 89        | 123489      123489      3489      | :-----------------------.-----------+-----------+-----------'           :-----------.-----------------------: | 12356789    12356789  | 12356789  | 12        | 4           89        | 6789      | 356789      356789    | |           .-----------:           '-----------+-----------.-----------'           :-----------.           | | 12345678  | 123456789 | 12456789    345689    | 123789    | 4567        12345     | 789       | 12345     | :-----------:           '-----------.-----------:           :-----------.-----------'           :-----------: | 123456789 | 12456789    456789    | 345689    | 123789    | 124567    | 789         789       | 23456     | |           '-----------.-----------'           |           |           '-----------.-----------'           | | 12456789    123456789 | 12345678    345689    | 123789    | 124567      12345     | 23456       23456     | '-----------------------'-----------------------'-----------'-----------------------'-----------------------'

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:

 Code: (1,6)R5C123=(6)R5C5,(1)R6C4

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:

 Code: neutral - strong - neutral

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...
_________________
Cheers,
Mike
mhparker
Grandmaster

Joined: 20 Jan 2007
Posts: 345
Location: Germany

Posted: Sun Dec 16, 2007 6:11 pm    Post subject:

 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.
_________________
Cheers,
Mike
Ruud
Site Owner

Joined: 30 Dec 2005
Posts: 601

 Posted: Sat Jan 05, 2008 12:43 pm    Post subject: 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
mhparker
Grandmaster

Joined: 20 Jan 2007
Posts: 345
Location: Germany

Posted: Sat Jan 05, 2008 10:04 pm    Post subject:

 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}.
_________________
Cheers,
Mike
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum SudoCue - the Website----------------Daily Sudoku Nightmare & ArchiveClueless SpecialsClueless ExplosionsWeekly AssassinsTexas Jigsaw KillersSudoku LiteX-FilesDaily WindokuDaily Jigsaw SudokuSolving Guide & GlossarySamurai ContestGeneral Website Comments Sudoku - the Community----------------Help Me! I'm stuck!Solving Techniques & TipsWebsitesSoftwarePuzzlesPublicationsOff-Topic SudoCue - the Software----------------SupportWishlistCommentsReleases
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