The New Sudoku Players' Forum

by **Myth Jellies** » Sat Apr 15, 2006 6:23 am

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]

by **Myth Jellies** » Sat Apr 15, 2006 9:05 pm

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.

by **Ocean** » Sat Apr 15, 2006 9:20 pm

Clear and instructive explanation, Myth!

by **Myth Jellies** » Thu Apr 20, 2006 5:21 am

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=6 A 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

by **r.e.s.** » Mon May 22, 2006 7:37 am

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 ...

[2007/04/05: Updated link address.]

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.)

by **Myth Jellies** » Tue May 23, 2006 7:40 am

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...

by **r.e.s.** » Tue May 23, 2006 6:05 pm

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.)

by **Myth Jellies** » Tue May 30, 2006 7:59 am

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

by **Myth Jellies** » Sun Jul 09, 2006 5:32 am

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.

by **Steve K** » Fri Jan 26, 2007 7:57 pm

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.

by **Myth Jellies** » Sat Jan 27, 2007 2:14 am

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.

by **Steve K** » Sun Jan 28, 2007 3:12 am

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.

by **re'born** » Sun Jan 28, 2007 2:34 pm

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?

by **Steve K** » Sun Jan 28, 2007 7:20 pm

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.

by AW » Sat Feb 03, 2007 8:05 am

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" ?

The New Sudoku Players' Forum

Alternating Inference Chains

Alternating Inference Chains

Re: Alternating Inference Chains