The New Sudoku Players' Forum

[blue]

I wish everyone would participate in this discussion because it would help the most if we had a consensus about it. I'm perfectly fine with switching to another usage of the terms if need be. It's quite possible that I'm the one that has been using them the wrong way. The only significant part for me is that we need two different words for two different concepts, and we should preferably agree to what they are.

From the top of Myth Jellies' semimal post on 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.

That is the "definition" that I would favor.
The definition isn't explicit, but given the historical significance of the thread, I think it shouldn't be taken lightly.

It wouldn't allow for an ALS to be called a "node" (as in the Sudopedia definition).

IMO, the Sudopedia definition is incorrect, and it should have been written:

A node is an item in a chain or loop. It can be a cell, a candidate or a complex structure like a Locked Set.

There's also this:
An ALS, in the context of an AIC, always appears as two (boolean) nodes, connected by a strong link.
The ALS itself (i.e. in its entirety), doesn't link to anything. It's the two parts, that have links.

Cheers,
Blue.

Added: I underlined "labeled" in Myth's first sentence, thinking that he must have been referring to the choice of "-" or "=" to distinguish weak and strong links. Nice-loop notation was still common at the time, though, and since the sentence mentions cells rather than candidates, it may be that he was only referring to digit part of "-d-" and "=d=" links.

[blue]

Follow up: As discussed above, I don't think an ALS can be a "node".
We could have nodes like these, however:

a = b - c = (finned fish) - (finned fish elimination) = f
a = b - c = (body|fin1|...) - (finned fish elimination) = f
a = b - c = [body = (fin1|...)] - (finned fish elimination) = f
a = b - c =* [d = e - f *= g] - h = i

In the finned fish example(s), the 'c' node would be an OR of one or more additional/"would be" fins for a larger (finned) fish pattern -- a "same sized" fish, but with more fins.

Like with an ALS, the larger pattern splits into two parts/"nodes" connected by a strong link.

[SpAce]

Thanks for your input, blue!

If I understood it correctly, it seems that my original understanding was actually perfectly in line with Myth's and your definition of "node". I think it's also in line with Eppstein's paper which talks about vertices (nodes) and edges (links). So, should we stick to that, after all? (Problem is, I can't deny that there's also historical support for both Steves' competing definitions.)

The nodes of an AIC are really just the candidate premises themselves.

That is the "definition" that I would favor.
The definition isn't explicit, but given the historical significance of the thread, I think it shouldn't be taken lightly.

I would prefer that definition too, obviously. It's the simplest to use too, because then there's zero ambiguity about the number of nodes in a chain: every linked element is one.

It wouldn't allow for an ALS to be called a "node" (as in the Sudopedia definition).

I fully agree in the context of normal ALS usage. In a wider context, I must slightly disagree (see explanation below).

IMO, the Sudopedia definition is incorrect, and it should have been written:

A node is an item in a chain or loop. It can be a cell, a candidate or a complex structure like a Locked Set.

There's also this:
An ALS, in the context of an AIC, always appears as two (boolean) nodes, connected by a strong link.
The ALS itself (i.e. in its entirety), doesn't link to anything. It's the two parts, that have links.

That's exactly how I see it too when ALSs are used normally. However, if we allow a bit more complexity, I think an ALS can actually be a node too (but then it must be part of a larger structure to begin with). For example, if we have an AALS (abcd) with four digits in two cells, the normal way to use it in a chain would be:

... = ab - (a|b=cd) - (d=e) ...

In that, the "cd" becomes a locked set just like in a normal ALS case. However, we could also use the AALS like this:

... = a - (a=b|cd) - (bd=e) ...

Now the "b|cd" (<-> (b=cd)) is actually an ALS and it's also a node, isn't it? In that light the Sudopedia definition isn't entirely incorrect, though I doubt that's anywhere close to what was meant. Would you agree with that?

[blue]

However, we could also use the AALS like this:

... = a - (a=b|cd) - (bd=e) ...

Now the "b|cd" (<-> (b=cd)) is actually an ALS and it's also a node, isn't it?

Yes. Nice observation.

In that light the Sudopedia definition isn't entirely incorrect, though I doubt that's anywhere close to what was meant.
Would you agree with that?

Yes.

AALS/ALS example:

Code: Select all

.  124 . | 23 . . | 45 . .
14 .   . | .  . . | .  . .
.  .   . | .  . . | .  . .
---------+--------+-------
-4 .   . | 34 . . | 45 . .

(4=5)r4c7 - (5=4)r1c7 - (4=1|23)r1c24 - (13=4)r2c1,r4c4 => -4r4c1

[ or: 4r4c7 = r1c7 - (4=1|23)r1c24 - (13=4)r2c1,r4c4 => -4r4c1 ]

[eleven]

Maybe OT (did not read the above). I would see/write it as
(4=35)r4c46 - (3|5=241)r1c462 - (1=4)r2c1

[SpAce]

Maybe OT (did not read the above). I would see/write it as
(4=35)r4c46 - (3|5=241)r1c462 - (1=4)r2c1

Yes, it would be better in this case, but doesn't invalidate blue's nice POC of an actual ALS node. What if we change it a bit:

Code: Select all

.  124 23 | .  .  . | 45 . .
14 .   .  | .  .  . | .  . .
.  .   .  | .  .  . | .  . .
----------+---------+-------
-4 .   .  | .  .  . | 45 . .
.  .   34 | .  .  . | .  . .


How would you write it now? The POC chain is still:

(4)r4c7 = r1c7 - (4=1|23)r1c23 - (13=4)r2c1,r5c3 => -4 r4c1

In practice, I'd rather write it:

(4)r4c7 = r1c7 - (42=1|3)r1c23 - (13=4)r2c1,r5c3 => -4 r4c1

or:

(4=3)r5c3 - (324=1|5)r1c327 - (15=4)r2c1,r4c7 => -4 r4c1

Both might be easier to read if reversed.

(It can also be written as an Almost-[WXYZ-Wing|ALS-XZ|XY-Chain], but that gets pretty far from the point.)

[eleven]

How would you write it now?

Here i prefer your second version.

But i also like the almost wxyz-wing, because you could add 2 digits.

Code: Select all

.  12+4 123| .  .  . | 45 . .
124.    .  | .  .  . | .  . .
.  .    .  | .  .  . | .  . .
-----------+---------+-------
-4 .    .  | .  .  . | 45 . .
.  .    34 | .  .  . | .  . .

[SpAce]

But i also like the almost wxyz-wing, because you could add 2 digits.

Code: Select all

.  12+4 123| .  .  . | 45 . .
124.    .  | .  .  . | .  . .
.  .    .  | .  .  . | .  . .
-----------+---------+-------
-4 .    .  | .  .  . | 45 . .
.  .    34 | .  .  . | .  . .

Nice. Writing it explicitly (i.e. without the wxyz-wing node) gets interesting:

(4)r4c7 = r1c7 - (4=12|3)r1c23 - ((1|2)&3=4)r2c1,r5c3 => -4 r4c1

Though I'd probably write:

(4)r4c7 = r1c7 - r1c2 = (12,4)b1p234|(34)r15c3 => -4 r4c1

--

Added. Could also be written like your original suggestion:

(4=35)r5c3,r4c7 - (3|5=412)r1c723 - (1|2=4)r2c1 => -4 r4c1

...which also means that my earlier change of the puzzle wasn't actually significant at all. Your way might still be the best way to write all of these.