Talking shop for methods of solving Assassins (V2+)
Talking shop for methods of solving Assassins (V2+)
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
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
I have 81 brain cells left, I think.
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!
Note to self: Must try and make time to study AICs!
Hi all,
Having said that, I indeed want to say something on the subject of:
Alternating Inference Chains
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!
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:To get the ball rolling...
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.Glyn wrote:On the subject of AIC (Alternate Inference Chains).
Having said that, I indeed want to say something on the subject of:
Alternating Inference Chains
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: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.
- candidate premise 1 is true ---> candidate premise 2 is false (weak link)
- candidate premise 1 is false ---> candidate premise 2 is true (strong link)
- candidate premise 1 is true ---> candidate premise 2 is true
- candidate premise 1 is false ---> candidate premise 2 is false
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: Select all
...=(5)r3c12-(6)r3c78=...
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: Select all
...=(5)r3c12-(5)r3c78,(6)r3c78=...
Code: Select all
...=(5)r3c12-(5,6)r3c78=...
Code: Select all
...=(5)r3c12-(5)r3c7,(6)r3c8=...
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
Mike
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.
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.
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.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...
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.
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
Mike
Here's the first one, namely step 8c in Afmob's A2X walkthrough.I wrote:Examples to follow.
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: Select all
(z=x)A-(x=y)B-(y=z)C
...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: Select all
strong - weak - strong - weak - strong
Let's now have a look at Afmob's step 8c. Here is the grid state immediately prior to this move:
Code: Select all
.-----------------------.-----------------------.-----------.-----------------------.-----------------------.
| 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 |
'-----------------------'-----------------------'-----------'-----------------------'-----------------------'
The logic used by Afmob was:
Using the comma notation for neutral links, this can be expressed in AIC form as: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
Code: Select all
(1,6)R5C123=(6)R5C5,(1)R6C4
...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: Select all
neutral - strong - neutral
Cheers,
Mike
Mike
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
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
Nice work, Ruud!Ruud wrote:Here's a move that I used a few times in A84 and its V2.
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.
Although it's not a totally intuitive name, Jean-Christophe has already introduced the name "Locked Cages" for this type of situation here:Ruud wrote:I cannot think of a suitable name for it, so a little help is appreciated.
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.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...
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
Cheers,
Mike
Mike