## Alternating Inference Chains

Advanced methods and approaches for solving Sudoku puzzles

### Alternating Inference Chains

Alternating Inference Chains
Until now, most posts in this forum that describe forcing chains and related methods as nodes consisting of cells which are connected by labeled linkages which are related to contents of the cells being linked. There are dozens of methods and types of these chains out there, some of which are brute force methods, and some which satisfy the algorithmic information theory requirements for theoretical methods.

It turns out that all chains found so far which qualify as theoretical can be described as Alternating Inference Chains. XY-Wings, X-Cycles, Bivalue XY-Chains, Bilocation XY-Chains, Mixed XY-Chains, Continuous and Discontinuous Nice Loops, Dual Implication Chains, chains employing Unique Rectangles, XYZ-Wings, even the ALS XZ-Rule deductions are all Alternating Inference Chains (AICs). Furthermore, AIC's are all guaranteed to be pattern-based, theoretical, and not brute force.

Definitions
Candidate, Candidate Premise In the following I am going to keep it simple at the start and just say "candidate" instead of "candidate premise". The simplest "candidate premise" is "candidate n is true in this cell," which is what most people mean when they talk about a candidate. Note that more complicated premises are possible, such as "candidate n is true in one of the cells marked with an A" (typical candidate grouping), or even "candidates i, j, and k are all true in cells A, B, and C", which is handy for a wxyz-wing. Simple AICs use only the simplest candidate premises.

Alternating Inference Chain (AIC) is a chain which starts with an endpoint candidate which has a strong inference on the next candidate, which has a weak inference on the next candidate, which has a strong inference on the next candidate, and so on alternating weak and strong inferences until it ends with a strong inference on the final candidate at the other endpoint. The nodes of an AIC are really just the candidate premises themselves.

In the following inference definitions, A and B are candidates (or candidate premises).

Weak Inference: For two premises, if A and B cannot both be true then there is a weak inference between A and B. To extend to multiple premises, if at most only one of a set of premises can be true, then those premises satisfy the weak inference requirement. Another way of saying this for this is, "One premise being true implies the rest are false."

Strong Inference: For two premises, if A and B cannot both be false, then there is a strong inference between A and B. To extend to multiple premises, if at least one of a set of premises must be true, then those premises taken together satisfy the strong inference requirement. As long as the set of premise choices encompasses all possible choices, then that set can be divided in any fashion, and a strong inference exists between any division of that set. For the two premise case, a strong inference is often represented as A being false implies B is true.

Note that due to the rule of the contrapositive, the weak and strong inferences work in both directions. For example, take the weak inference: A = true implies B = false. From the other direction we would have B = true implies A = false. Since this is just the contrapositive of the weak inference, we know that it is a valid assertion as well. Thus AICs are bidirectional.

The following candidate link definitions aren't really necessary, but they do provide examples of weak and strong inferences.

Link, Weak Link: Any two candidates (same digit) which satisfy the weak inference requirement can be thought of as weakly linked. Sometimes the weak link term is reserved for candidates that have a weak inference, but do not have a strong inference. Examples of this latter case are, any two candidates in a cell containing three or more candidates; and any two candidates that are the same digit sharing a house(s) that contain at least three of that digit. This distinction is not really necessary, but it seems to be historical, so what are you going to do. Simple candidates which are said to "see" each other are at least weakly linked.

Strong Link, Conjugate Link: Historically, this is a link between two candidates, A and B, which satisfies the following relationship. "A = not B". This is really overkill, since that relationship satisfies both the weak inference and the strong inference requirements. Don't be confused by the fact that a strong link can be used for a weak inference--once again, it is terribly hard to buck tradition. Examples of strong links are, the two candidates in a cell that contains only two candidates; and two candidates, which are the same digit and are the only two candidates of that digit in a house. A strong/conjugate link is a wildcard link that can be used for either a strong or a weak inference.

Inverse Link, Converse Link, Strong-Only Link:This is a relatively new type of link that comes up with Almost Unique Rectangles and groupings of candidates. This link satisfies the strong inference requirement, but does not satisfy the weak inference requirement.

Deductions
Quite simply, at least one or the other (possibly both) of the two endpoint candidates (or candidate premises) of an AIC is true. Any deductions that you can make based on that are valid. This tends to produce the best results if the endpoints either share a group, or if the endpoints involve the same candidate. When your chain endpoints satisfy one of those conditions, it is time to check for any deductions.

If the two endpoints candidates are weakly linked, then you have an AIC loop. In this case, you could cut the loop at any weak link and end up with a valid AIC. Thus, for every weak link in the loop, either one or the other of the candidates joined by that weak inference are true, and you can make all appropriate deductions based on that.

That is pretty much all you need.

Examples
In the examples below, an '=' indicates where a strong inference is used, and a '-' indicates where a weak inference is used. The capital letters indicate the cell(s) where the premise holds. Many of these have been taken from Jeff's post on B&B loops.

Code: Select all
` *-----------------------------------------------------------* | 247   5    G28    | 479   4789  1     | 6     379   3789  | | 3     147   6     | 479   45789 2     | 578   179   5789  | | 17   F178   9     | 3    E578   6     | 2    D157   4     | |-------------------+-------------------+-------------------| | 79    6     4     | 5     3     79    | 1     8     2     | | 129   1239  23    | 8     6     4     | 57    3579  359   | | 8     379   5     | 1     2     79    | 4     6     39    | |-------------------+-------------------+-------------------| | 6     248   1     | 479   479   5     | 3     27    78    | | 245   2348 H238   |-6    -47   -38    | 9    C257   1     | |-59   -39   -7     | 2     1    A38    |B58    4     6     | *-----------------------------------------------------------* A8=B8-B5=C5-D5=E5-E8=F8-G8=H8`
Eureka notation:
(8)r9c6 = (8-5)r9c7 = (5)r8c8 - (5)r3c8 = (5-8)r3c5 = (8)r3c2 - (8)r1c3 = (8)r8c3

Either the 8 in A (r9c6) or the 8 in H (r8c3) is true, therefore no 8's can exist in r8c456 or r9c123.

Code: Select all
` *--------------------------------------------------------------------* | 39     2      39     | 6      1      8      | 5      4      7      | | 7     A156    4      | 25     235   -9      |B12     36     8      | | 156    156    8      | 2457   23457 D24     | 9      36    C12     | |----------------------+----------------------+----------------------| | 2689   3      69     | 1      2489   7      | 248    5      2469   | | 1259   1589   1579   | 24     249    6      | 2347   789    2349   | | 2689   4      679    | 3      289    5      | 278    1      269    | |----------------------+----------------------+----------------------| | 139   -189    2      | 4578   457   E14     | 6      789    39     | | 4      1689   1369   | 278    27     12     | 137    789    5      | | 158    7      15     | 9      6      3      | 148    2      14     | *--------------------------------------------------------------------* A1=B1-C1=C2-D2=D4-E4=E1`
Eureka notation
(1)r2c2 = (1)r2c7 - (1=2)r3c9 - (2=4)r3c6 - (4=1)r7c6

Must be either a 1 in A (r2c2) or a 1 in E (r7c6). Therefore there can be no 1 in either r2c6 or r7c2.

Code: Select all
` *--------------------------------------------------------------------* | 247    5      28     | 479    4789   1      | 6      379    3789   | | 3      1478   6      | 479    45789  2      | 578    179    5789   | | 17     178    9      | 3     B5678 -A68     | 2     C157    4      | |----------------------+----------------------+----------------------| | 79     679    4      | 5      3      679    | 1      8      2      | | 129    12369  23     | 8      69     4      | 57     35679  359    | | 8      3679   5      | 1      2      679    | 4      369    39     | |----------------------+----------------------+----------------------| | 6      2489   1      | 479    4789   5      | 3      27     78     | | 245    2348   238    | 6      478    38     | 9     D257    1      | | 59     39     7      | 2      1    -F389    |E58     4      6      | *--------------------------------------------------------------------* A6=B6-B5=C5-D5=E5-E8=F8`
Eureka notation
(6)r3c6 = (6-5)r3c5 = (5)r3c8 - (5)r8c8 = (5-8)r9c7 = (8)r9c6

Stopped AIC at F to check because A and F share a group (column 6). Chain means either cell A (r3c6) is 6, or cell F (r9c6) is 8. In either case, cell A cannot be 8 and cell F cannot be 6.

Code: Select all
` pure bilocation loop: *--------------------------------------------------* | 7    58   1    | 2    3    9    | 6    4    58   | | 6    38   2    | 1    4    5    | 389  89   7    | | 35   4    9    | 8    6    7    | 23   1    25   | |----------------+----------------+----------------| | 4   A123  38   | 369  5   B136  | 289  7    289  | | 9    235  357  | 37   8    34   | 24   6    1    | |E18   6    78   | 79   2    14   | 489  5    3    | |----------------+----------------+----------------| | 35   9    356  | 36   1    8    | 7    2    4    | |D128  13   368  | 4    7   C236  | 5    389  89   | | 28   7    4    | 5    9    23   | 1    38   6    | *--------------------------------------------------* A1=B1-B6=C6-C2=D2-D1=E1 (-A1)`
Eureka notation
(1)r4c2 = (1-6)r4c6 = (6-2)r8c6 = (2-1)r8c1 = (1)r6c1...

Since a weak inference exists between the candidate 1's in cells A and E, the loop is closed, and we know that one of the candidates at either end of each weak inference is true. Therefore, B = 16, C = 26, D = 12, and all 1's in box 4 that are not in A or E can be eliminated.

Code: Select all
` pure bivalue loop: *-----------------------------------------------------------* | 5     6     29    | 7     3     1     |G29    4     8     | | 247   248   17    | 5     9     48    | 6     3     12    | | 349   348  A13    | 48    6     2     | 5     7    H19    | |-------------------+-------------------+-------------------| | 367   9    B37    | 2    C47    5     | 1     8     467   | | 27    25    4     | 68    1     68    | 3     59    579   | | 16    15    8     | 3    D47    9     |E47    2     56    | |-------------------+-------------------+-------------------| | 1234  7     6     | 9     8     34    |F24    15    245   | | 1349  134   5     | 46    2     3467  | 8     19    479   | | 8     24    29    | 1     5     47    | 2479  6     3     | *-----------------------------------------------------------* A1=A3-B3=B7-C7=C4-D4=D7-E7=E4-F4=F2-G2=G9-H9=H1 (-A1)`
Eureka notation
(1=3)r3c3 - (3=7)r4c3 - (7=4)r4c5 - (4=7)r6c5 - (7=4)r6c7 - (4=2)r7c7 - (2=9)r1c7 - (9=1)r3c9...

Again, a weak inference exists between the endpoints of the chain, closing the loop. This means that one of the candidates at either end of each weak inference must be true. Kill, in this case, all 7's in row 4 not in B or C, all 4's in column 7 not in E or F, and all 2's in column 7 not in F or G.

Code: Select all
` mixed loop *--------------------------------------------------------------------* | 1      37     8      | 4      2      9      | 5      37     6      | | 36     45     9      |D58     36     7      |C48     1      2      | |A27     45     26     | 1      36     58     |B3478   9      34     | |----------------------+----------------------+----------------------| | 348    2      135    | 38     9      468    | 16     356    7      | | 347    6      137    | 237    5      24     | 123    8      9      | | 9      378    357    | 2378   1      26     | 236    4      35     | |----------------------+----------------------+----------------------| | 378    378    2367   | 9      4      125    | 367    23567  135    | | 5      9      237    | 6      8      12     | 347    237    134    | |F26     1      4      |E25     7      3      | 9      256    8      | *--------------------------------------------------------------------* A7=B7-B8=C8-D8=D5-E5=E2-F2=A2 (-A7)`
Eureka notation
(7)r3c1 = (7-8)r3c7 = (8)r2c7 - (8=5)r2c4 - (5=2)r9c4 - (2)r9c1 = (2)r3c1...

Here, we have a weak inference between the endpoints of the chain because they both lie in the same cell. Because the loop is closed, we can say A = 27, B = 78, 8's not in C or D can be eliminated from row 2, 5's not in D or E can be eliminated from column 4, and 2's not in F or E can be eliminated from row 9.

Code: Select all
`Carcul's initial AUR example 167   2   B13478| 468   3489 468  | 5     79    168  156  A138  9    | 7     358  2568 | 246   246   1268  567  H478 H478  | 24568 4589 1    | 79    3     268    -----------------+-----------------+-----------------  4     15   126  | 13    7    58   | 1236  2568  9  3     59   16   | 458   2    4589 | 16    58    7  8     1579 127  | 13    6    59   | 123   25    4 -----------------+-----------------+------------------  127   6   C38   | 9     1458 24578| 247   247  D235  1279 G147 G147  | 256  F15   3    | 8     2679 E256  279   38   5    | 2468  48   24678| 24679 1     236  A3=B3-C3=D3-D5=E5-F5=F1-G1=aur=H8`
Eureka notation
(3)r2c2 = (3)r1c3 - (3)r7c3 = (3-5)r7c9 = (5)r8c9 - (5=1)r8c5 - (1=4&7)r8c23 -UR- (4&7=8)r3c23

The almost unique 47 rectangle in r38c23 means that if neither of r8c23 is 1, then one of r3c23 is 8, a strong inference. Chain stopped for examination because A and H are both in box 1. Chain means that either A (r2c2) is 3 or one of the H cells (r3c23) is 8. In either case, A cannot be 8.

Next is a recent Ruud Daily Nightmare
Code: Select all
` ALS example *-----------* |.6.|5..|.1.| |...|3..|..4| |..8|.9.|2..| |---+---+---| |4.7|2..|...| |.5.|.7.|.8.| |...|..9|1.7| |---+---+---| |..3|.4.|6..| |1..|..7|...| |.8.|..5|.2.| *-----------* *--------------------------------------------------------------------* | 2379   6      49     | 5      28     48     | 3789   1      389    | | 259    179    159    | 3      1268   168    | 589    79     4      | | 35     14     8      | 7      9      14     | 2      356    356    | |----------------------+----------------------+----------------------| | 4     A139    7      |-2     -1568  -1368   | 359    3569   3569   | |A69    -5     A169    | 146    7     B36     | 349    8      2      | | 8      23     26     | 46     56     9      | 1      3456   7      | |----------------------+----------------------+----------------------| | 59     79     3      | 18     4      2      | 6      579    18     | | 1      249    24569  | 689    36     7      | 34589  3459   3589   | | 679    8      469    | 169    136    5      | 3479   2      139    | *--------------------------------------------------------------------* A3=A(1&6&9)-B6=B3`
Eureka notation
(3=1&6&9)r4c2,r5c13 - (6=3)r5c6

The cells marked with an A form an ALS where there are N+1 digits in N cells. Either A contains a 3 or A must contain 1 & 6 & 9. The 6 in B sees all of the 6's in A so they are weakly linked. The AIC endpoints tell you that either A or B contains a 3, thus any cell seeing all the 3's in A & B cannot be a 3.

Code: Select all
`LA Times 5-20-06: r.e.s.'s AUR & ALS chain solution *-----------*  |3..|9..|..7|  |..6|1.7|.49|  |...|8..|.5.|  |---+---+---|  |7..|6..|...|  |64.|...|.13|  |...|..2|..4|  |---+---+---|  |.7.|..9|...|  |83.|4.5|6..|  |5..|..1|..2|  *-----------*  Simple Sudoku - all singles then gets stuck here:   *--------------------------------------------------*  | 3    158 -148  | 9    45   6    | 18   2    7    |  | 2    58   6    | 1    35   7    | 38   4    9    |  |A149  19   7    | 8    2    34   | 13   5    6    |  |----------------+----------------+----------------|  | 7    2   C13   | 6    134  34   | 9    8    5    |  | 6    4    5    | 7    9    8    | 2    1    3    |  | 19  B189 C138  | 5    13   2    | 7    6    4    |  |----------------+----------------+----------------|  |-14   7   C14   | 2    6    9    | 5    3    8    |  | 8    3    2    | 4    7    5    | 6    9    1    |  | 5    6    9    | 3    8    1    | 4    7    2    |  *--------------------------------------------------*  A4=aur=B8-C8=C(1&3&4)`
Eureka notation
(4=1&9)r3c12 -UR- (1&9=8)r6c12 - (8=1&3&4)r467c3

Cells, such as r1c3 & r7c1 which see both the 4 in A and the 4 in C cannot be a 4. The AUR (19) is in r36c12, and the ALS is in the cells marked with C must either contain an 8 or will contain the 1&3&4 locked set.

Hopefully this very simple set of rules will help, both newcomers and those confused by all of the various methods out there, to make chain deductions as easily as the pros.

[Edits - made notation more compact, and added new example. Augmented definition of weak and strong inferences. Added alternate notations. Further augmented weak and strong inferences so that it becomes useful for nets as well as chains. Fixed comments on first ALS example. Replaced my goofy notation with Eureka notation]
Last edited by Myth Jellies on Wed Jun 20, 2007 2:53 am, edited 4 times in total.
Myth Jellies

Posts: 593
Joined: 19 September 2005

It turns out that the premises do not have to be strictly about candidates. For example, the Molecular Method uses AICs with both candidate and coloring premises.
Myth Jellies

Posts: 593
Joined: 19 September 2005

### Re: Alternating Inference Chains

Clear and instructive explanation, Myth!
Ocean

Posts: 442
Joined: 29 August 2005

As stated, the candidate premises can get pretty wild.
Code: Select all
` *----------------------------------------------------------------------* | 1      245    23589  |  78     489    4789   |  35     6      2489   | | 489    7      2489   |  6      3      5      |  28     1      2489   | | 34589  45     6      |  1      489    2      |  357    357    489    | |----------------------+-----------------------+-----------------------| | 2     F156    135    |  35    E569   E69     | -4     -8     -7      | | 34568  456    3458   |  2358   7     D468    |  236    9      1      | |-3468  -9     -7      |CD238   CD2468  1      |AB236   B23     5      | |----------------------+-----------------------+-----------------------| | 567    1256   125    |  4      258    3      |  9      257    268    | | 567    3      25     |  9      1      78     |  2578   4      268    | | 49     8      49     |  257    256    67     |  1      257    3      | *----------------------------------------------------------------------*Here is an example of some convoluted premises.6=(2&3)-(2or3)=(4&6&8)-6=6A   B     C       D    E F`

This AIC tells you that any cell which sees both the A and F cells, cannot be a 6. Once you start seeing almost locked sets, these are really not too difficult to construct.

Explaining the premises in more detail:
(A has 6) = (B has 2 & 3) - (C has 2 or 3) = (D has 4, 6, & 8) - (E has 6) = (F has 6)
Implies either A or F is 6
Myth Jellies

Posts: 593
Joined: 19 September 2005

MJ,

I like your presentation of AIC a great deal. Taking candidate digits as the nodes in forcing chains (and nets) -- for which "alternating weak and semi-strong links" is the natural logic-construct -- is a method I've been using for quite a while. My interests have not been much oriented to satisfying anyone's idea of "practical solving methods", though.

To see what I mean, please see <this old posting> , and note that it closes with a description of forcing chains as the sort of objects that Nick70 (<here>) called "double implication chains", except using "semi-strong" implication links instead of strong ones -- "semi-strong" being the word I prefer for what you're calling "strong only"/"inverse"/"converse" links.

If a and b are candidate digits (or better, "candidate premises", as you say), and 'aT' abbreviates "a is True", etc., then the link-types of interest are
Code: Select all
`Type            Implication  Conditions                     Suggested Notation-------------   -----------  ---------------------------    ------------------"weak"          aT => bF     at most one of a,b is True     a---b"semi-strong"   aF => bT     at least one of a,b is True    a-*-b"strong"        aF <=> bT    exactly one of a,b is True     a===b`

Thus a strong link is both semi-strong and weak, but NOT every semi-strong link is weak (and a weak link might be neither of the other two). When links are restricted to weak and strong, there is no reason to use the adjective "weak" at all, since there are just links, some of which are strong. The same is obviously not true, though, when semi-strong links are introduced. (The "suggested notation" is both a crude ascii description of how the link might be graphed, and to a lesser extent how it might be written as text.)

This picture shows the well-known logic patterns for digit-to-digit chains ...

For a couple of recent postings recapping some of this, please see
http://www.sudoku.org.uk/cgi-bin/discus/show.cgi?tpc=29&post=4705#POST4705
http://www.sudoku.org.uk/cgi-bin/discus/show.cgi?tpc=29&post=4728#POST4728
(both are in the thread "Digit-to-Digit Chains" on that forum).

(MJ -- I trust that, after reading my old posting from last September, you will not be offended by the fact that when I started that recent thread, I made no attempt to cite sources -- such as Nick70's, mine, or your postings on this type of chain, which imo has been part of the "common-knowledge pool" for a long while. We may have some difference of opinion, though, concerning what it means for a solving method to be formulated in terms of digit-pattern contructs rather than logic-constructs.)
Last edited by r.e.s. on Thu Apr 05, 2007 5:59 pm, edited 1 time in total.
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote:...(MJ -- I trust that, after reading my old posting from last September, you will not be offended by the fact that when I started that recent thread, I made no attempt to cite sources -- such as Nick70's, mine, or your postings on this type of chain, which imo has been part of the "common-knowledge pool" for a long while.

I think you said it best when you stated, "I suspect that few people who've studied digit-to-digit forcing chains in much detail have not discovered this fact for themselves." There was a heavy trend in this forum toward the complexity of cell based nodes. After being rebuffed in the "official" post on forcing chains, I wanted to present what I thought was a simpler way of looking at chains in a similar "official" manner.
r.e.s. wrote:We may have some difference of opinion, though, concerning what it means for a solving method to be formulated in terms of digit-pattern contructs rather than logic-constructs.)

That would not surprise me . I'm guessing that your digit-pattern contructs correlates to my theoretical methods, and your logic-constructs correlates to my brute-force methods. For more info on theoretical vs brute-force, check out the Algorithmic Information Theory links at the bottom of this post and draw your own conclusions as to whether or how they might relate to sudoku methods.
r.e.s. wrote:For a couple of recent postings recapping some of this, please see ...

Looks like Mike's site is becoming interesting again. I may have to check it out more often. It was pretty much dead for so long...
Myth Jellies

Posts: 593
Joined: 19 September 2005

Myth Jellies wrote:... I wanted to present what I thought was a simpler way of looking at chains in a similar "official" manner.

The emphasis on taking cells as the nodes in a graph with labelled edges owes a lot to <Eppstein's paper>, which naturally inspired a lot of people to emulate its style. For example ...

Scott H, last August, on "labelled forcing chains":
("a method of labelling edges that helps to construct and recognize forcing chains")
http://forum.enjoysudoku.com/viewtopic.php?p=7478#p7478

Jeff, a couple of months ago:
("Eppstein's gadgets has been extended to b/b plot and nice loops with mixed bilocation and bivalue deductions")
http://forum.enjoysudoku.com/viewtopic.php?p=24410#p24410

Not being a graph theorist myself, I can only speculate that expressing everything in terms of edge-labels might be necessary for certain formal proofs. But it's unnecessary when stating the kinds of results we're talking about, e.g. those in Nick70's posting (which was prior to Eppstein's paper). The choice between using cells as nodes in a graph with labelled edges vs digits as nodes in a graph with unlabelled edges reminds me a bit of the "top-down" vs "bottom-up" issue in programming.

I enjoyed your posting on "complexity versus useful logical theory". The whole subject of formally quantifying "information" and "complexity" is fascinating, and the connection between those two ideas has stimulated a flood of discussion (not to mention controversy) on various newsgroups. (Googling will no doubt give a deluge of links.)
r.e.s.

Posts: 337
Joined: 31 August 2005

Added new combined AUR & ALS example to original post and also rewrote the chain shorthand notation there in a simpler single-line style.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Added some alternate notation to the initial post examples for when you don't want to have a grid picture with cell labels, such as when you have a lot of steps in a puzzle solution.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Upon studying your notes on AIC, it is obvious to me that what I have been calling "forbidding chains", and what is called here AIC are precisely the same idea. I have done some work in trying to deal with one inherent problem with these types of chains:

The problem is that it is not immediately obvious how one would write the AIC for a triple (be it naked or hidden) or a swordfish.

Because some techniques require weak links to see more than one strong link at a time, and because AIC does not graph these relationships well, the representation of ideas like these is problematic. I am not satisfied with any of the manners that I use to overcome this presentation problem. I am curious if you have any input.
Steve K

Posts: 98
Joined: 18 January 2007

Steve K wrote:The problem is that it is not immediately obvious how one would write the AIC for a triple (be it naked or hidden) or a swordfish.
...I am not satisfied with any of the manners that I use to overcome this presentation problem. I am curious if you have any input.

A triple by itself is usually of little interest. Most often I see it as a potential entity in an AIC as part of an ALS (N+1 digits in N cells). Then I represent it with &'s like in the following...

(1&2&3=4)r1c12,r3c1 - (4=2)r1c8 - (2=1&3&4)r1c12,r3c1

This AIC would tell you that r1c12 & r3c1 contains either the triple 123 or the triple 134, eliminating all other 1's and 3's in the first box. In addition, since those two triples exclude each other, we have an AIC loop, and can eliminate all the 2's and 4's in row 1 that are not in r1c128.

I represent a swordfish, or any other similar constraint structure as a fish group or constraint group. Thus...

(1)r267/c149 = (1)r13c1

...indicates a finned swordfish where either the r267c149 swordfish in ones is true or the fin (r13c1) contains a one. Either way you can eliminate the 1's in r2c23.

When all else fails, such as with the spoke pattern, I resort to a two-dimensional diagram that indicates all of the candidate-to-candidate linkages.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Thanks Myth!
I have little interest in triples, etc. either. The crux of the problem, as I see it is this:

AIC are really nothing more than a language choice, since all sudoku techniques are nothing more than repeated applications of the rules. A good language choice should pull in some elements of part of the existing knowledge base, as we do not want to reinvent the wheel too often. AIC, since they allow the introduction of Boolean Logic, seem to be a fairly good choice.

Nevertheless, a litmus test for a good language choice could be that it represent efficiently, in its base form, elementary ideas. Triples are an elementary idea not easily represented by AIC in its base form. My question was precisely:
Does anyone have a good base form for representing something like a triple? Why do I care? I think AIC are an excellent language choice, and I use them extensively. But, they can be an times clumsy.

BTW:
Strong link could be alternately described as:
A == B is A OR B
Weak link could be alternately described as:
A -- B is (~A) OR (~B)

The symmetry of using this equivalent definition somehow fits better for me. Also, it eliminates the clumsiness of A implies B.

Guess this is why I call them forbidding chains, rather than AIC, as I use no inference, only OR and not.

So for me, the components of the chain are:
Boolean variables, OR, not.
Steve K

Posts: 98
Joined: 18 January 2007

Steve K wrote:BTW:
Strong link could be alternately described as:
A == B is A OR B
Weak link could be alternately described as:
A -- B is (~A) OR (~B)

Do you mean by OR, the exclusive or, XOR?
re'born

Posts: 551
Joined: 31 May 2007

OR, as in UNION. Otherwise, the symmetry of the chains is broken:

A==B -- C ==D, which means:

A == B.
B -- C.
C == D.

and allows one to conclude: A==D.

In the special case of additonally having A--D, one can further conclude:
B==C.

The misconception that it should be XOR is common, and, for the purposes of AIC (Equivalent to forbidding chains), a glaring error.

Finally, it is true that in Sudoku, a native strong link is always also weak. That really has no bearing on the conclusions of the chain. The chain writer is free to use which one of those two relationships fits the proof.
Steve K

Posts: 98
Joined: 18 January 2007

Implication may be clumsy, and alternating inferences may be more symmetrical. However, there are a few good words to put in for inferences.

Allowing that the general pattern for chaining is (where Q is to be taken generally as "some conclusion") :

((A implies Q) and (~A implies Q))

The art of chaining is the art of getting from A to Q for both states of A.

Now, you can indeed infer that (~B implies A) when (A or B), and you can indeed conclude that (B implies D) when ((~B or ~C) and (C or D)). And thus that, under ((A or B) and (~B or ~C) and (C or D)), if you can further establish that ((A implies Q) and (D implies Q)), then Q must be so, seing as it is implied by both B and ~B.

But, just like (A xor B), the "conjugate link", is not the only way of getting at (A or B), there are more ways of getting at (B implies D) than just the ((~B or ~C) and (C or D)) pattern.

Not to mention that... well, ok, why don't I just go ahead and mention it : if you're into programming sudoku solvers, you'll find that keeping track of what implies what, is easier than a keeping track of a bunch of strong and weak links.

Even more so when you remember that (A or B) can be rewritten as (~A implies B). And that when ((A implies B) and (B implies C)), then (A implies C). And that when (A implies B), then (~B implies ~A).

Would that qualify as "represent[ing] efficiently, in its base form, elementary ideas" ?
AW

Posts: 27
Joined: 31 January 2007

Next