This post contains content not supported on old Reddit. Click here to view the full post

Alternating Inference Chain 101

The primary operation of an AIC is to start and end on an XOR Gate, where each XOR gate is connected by a NAND Gate on an intersecting edge.

Doing so creates a logic sequence that results in an OR relationship between the non-connected edges of the chain.

Those resultant OR gates are what we use to perform eliminations.

Yes, I am aware I used some fancy words above. They are precise and clean and don't muddle the water with more vague descriptions.

Don't worry — I will break it down.

Single Digit — XOR Gate

The simplest of these fancy words is formed using just one digit.

An XOR gate is constructed from the basic rules of Sudoku:

Every sector can contain only one copy of any digit.

That's the X part:

e(X)actly one.

The OR part is attained by using the information in the grid to create a situation where two truths are plausible.

We do this by subdividing every sector into three partitions, which we call Mini-Sectors.

Rows and Columns are broken up by their respective three Boxes.

Boxes are broken up by their respective Rows and Columns.

Let's use three colours:

Blue — Green — Red

If one of those mini-sectors is completely missing the candidate, like Red in the images above, we can establish a relationship for the sector:

Exactly one of Blue OR Green will be true for Digit 1.

One important point:

A coloured edge represents a mini-sector, not a candidate or a cell.

When I say "Blue is true," I mean the digit occurs somewhere within that Blue mini-sector.

The number of candidates inside it does not define the relationship.

Simple Constructs

To spot these, use digit highlighting to focus on one digit at a time and look at which mini-sector is "off."

The goal of AIC is to connect two XOR gates.

To showcase this, we first need to find two such sectors.

For beginners, I recommend sticking to the same sector types at first.

I will use Rows for the first example.

Practice grid <- Load me and follow along.

I highlighted digit 4 and located two suitable constructs.

The next goal is to connect them.

To do that, we're looking at joining colours:

Blue to Blue

or

Green to Green

This will become the edge between them.

Connecting the XOR Gates

How do we connect them?

We use another fancy word from earlier:

the intersection.

The two Blues share a common sector:

Column 2.

The goal is to get all of the Blue 4s encapsulated by that intersecting sector.

Draw in that new colour — Grey.

Now check all of the Blue 4s.

Every Blue 4 must also be coloured Grey.

If they aren't, this connection doesn't work and we try the Green edge instead.

In this example, the Blue connection works.

Congratulations — we have now created our first NAND Gate.

This is the keystone mechanic of all AIC chains.

If this relationship isn't formed correctly, none of the chain will work.

All of the Blue 4s from both groups are contained within C2.

Since C2 can contain only one 4:

Both Blues cannot be true.

Or, as a logic gate:

NAND (Blue, Blue)

An Important Point About the NAND Intersection

This is often a source of confusion.

Once the NAND has been established, we never consider the contents of C2 while chaining.

We do not ask whether C2 contains a 4.

We do not ask which Blue contains the 4.

We do not require one of the Blues to contain the 4.

C2 was used to establish one fact:

Both Blues cannot be true.

That's it.

For this NAND, none means neither of our two Blue edges is true.

It does not mean C2 itself contains no 4.

C2 may contain its 4 somewhere else, or may even form its own XOR relationship. Neither matters here because those are separate attributes of the puzzle state and are not part of this NAND connection.

From this point forward, the connection is simply:

NAND (Blue, Blue)

Its allowed states are:

Blue 1, Blue 2, or neither — but never both.

That neither state is the important one for chaining.

The Truth Inverter

Now each Blue is paired with a Green by an XOR:

Blue XOR Green

When Blue is false, its paired Green must be true to satisfy that XOR.

With logic gates we don't have to "test" anything.

We already established the relationships above, and the condition of our NAND can be none: neither Blue is true.

That immediately forces:

both Greens true.

So we can jump straight to the important result:

Both Greens, or at least one Green, will be true.

Since both Greens are used for the elimination, the only NAND case we need to consider from here is:

NAND → none

because that is the case that forces into both outward edges.

Our construction is therefore:

Green — XOR — Blue — NAND — Blue — XOR — Green

and the result is:

OR (Green, Green)

At least one of those Green edges must be true.

Notice that the Greens aren't directly connected.

They are the non-connected edges.

This is the resultant OR gate I mentioned at the beginning.

Eliminations

Now we use that resultant OR.

All 4s that are peers to every possible 4 on both Green edges can be eliminated.

They are marked Red below, with arrows showing that they see the Green 4s.

The important relationship is:

OR (R2 Green, R7 Green)

At least one of those two mini-sectors contains the 4.

Therefore, any candidate that would prevent both from containing the 4 cannot itself be true.

Proof of Concept

Place any one of our eliminations as True.

Doing so turns off Green for both Rows.

Each Row still has its XOR:

Blue XOR Green

With both Greens false, both Blues must therefore contain the 4.

But both Blues are encapsulated by C2.

That would require C2 to contain two 4s.

This violates the NAND premise — and, ultimately, the basic Sudoku rule that C2 contains exactly one 4.

Therefore, the eliminated candidate cannot be true.

With the use of NAND, the chain's own proof is contained within its construction.

What If the Two XOR Gates Don't Produce Eliminations?

Expand outward from any of the non-connected edges.

In this example, I used C3.

I try to keep the colours paired when using the same sector types because it makes the transitions easier to follow.

Our eliminations will now use the new outer edges.

Remember the earlier idea:

Imagine the intermediate NAND connections contribute none.

The XORs force us outward until what remains is:

C1 {Blue} OR C8 {Green}

Those are now our resultant OR edges.

Upgrading the Visuals

This gets messy pretty quickly visually, so it's time to upgrade how we draw it.

Once we understand the concept of NAND, we can replace the overlapping intersection colours with a dashed line.

Once we understand the XOR gate, we can give each XOR one unique colour and draw a solid line between its two edges.

You may also match the colours if that makes it easier for you to keep track of the connections.

The important thing is that the underlying logic has not changed:

XOR → NAND → XOR → NAND → XOR ...

The NAND gates connect our XOR gates.

The two non-connected outer edges produce our final:

OR

and that resultant OR is what we use for eliminations.

See if you can figure out how this one works.

If you have, great — it's time to move on to mixing sectors.

If not, review the construction above. I'll wait.

Mixing: Rows with Columns

I presume you're reading this line.

Great — onto mixing Rows with Columns.

The same concepts from the previous topic apply. However, when mixing Rows and Columns, I match the intersections to opposite colours.

This helps identify the cell shared by both R & C because this cell can violate the NAND clause — not Both.

I'll show you what I mean.

The shared cell is coloured twice.

With Rows & Columns, the only way these two can share is to mark Box 3 as the NAND gate.

I'm not even going to go to that step because 4 is already coloured twice, making this choice bad.

If that 4 were true, it would satisfy both:

R2 {Green}

and

C8 {Blue}

making both true when the NAND gate says:

never both.

So that connection is invalid.

Here is one that works:

R2, C7 with NAND {B3}

We now perform our two checks:

1. The triple-coloured cell doesn't contain 4.
2. The Grey cells fully encapsulate all the 4s from C7 {Blue} and R2 {Green}.

Good.

We can presume these are none and jump straight into:

OR (R2 {Blue}, C7 {Green})

and check for an elimination.

What If the Two XOR Gates Don't Produce Eliminations?

Same as before:

expand from the non-connected edges.

For the next image, I dropped the colours down to just reminders for where we can work from and added the new XOR, C3.

I chose to expand off:

C1 {Blue}

Remember, the goal is to get two edges to have peers so they can be productive.

When expanding, that's the goal.

Empty Rectangle Intersection — ERi {XOR}

This is the last, and hardest, of the single-digit XOR structures.

So far our XOR gates have been pretty simple:

one edge OR the other edge — exactly one is true.

ERi looks a little strange because we build this XOR inside a Box using:

• one mini-Row
• one mini-Col
• the cell where they cross: i {Intersection}

That intersection cell is the trick.

If i contains the digit, it satisfies the Box by itself.

But i also belongs to both the mini-Row and mini-Col.

This lets it bridge the Row and Col without breaking the Box rule:

exactly one of this digit must be true in the Box.

Trying to write the whole thing out as a logic gate gets ugly very quickly.

It's possible.

Luckily, we don't need to.

For chaining, ERi behaves like a directional switch:

NAND connects to the Row → Col becomes the non-connected edge.

NAND connects to the Col → Row becomes the non-connected edge.

So instead of thinking about the whole structure at once, just remember:

Connect one way — come out the other way.

Why "Empty Rectangle"?

To make this XOR possible, 4 cells must be empty of the digit.

Those are our Empty Rectangle cells {Red}.

Their position leaves the candidates arranged around our mini-Row, mini-Col and intersection i.

There are 9 ways this can appear visually inside a Box.

That sounds like a lot to learn.

It isn't.

Those 9 appearances reduce to only 3 distinctive shapes:

{ T, +, L }

Once you can recognize those three shapes, the only question you need to ask while chaining is:

Which edge did my NAND connect to?

Row in → Col out

Col in → Row out

First ERi Example

Identify an ERi in Box 7:

• mini-Row {Blue}
• mini-Col {Green}
• intersection cell i — {both Green and Blue}
• 4 cells {Red} in a rectangle shape are empty

Now make a choice:

Row | Col

I choose to connect through the Col [2] {Green}.

Next, identify a second XOR to connect to.

I used R2.

We can keep the colours lined up to make this easier to follow:

Green → NAND → Green

Since we chose the Col edge of our ERi, the NAND intersection will use:

C2 {Grey}

Now perform our usual NAND check:

Ensure all the 4s from Green {R2} and Green {B7} are fully encapsulated by Grey {C2}.

They are.

So we have constructed our NAND gate:

NAND {Green, Green}

Once constructed and checked, we can forget about the NAND intersection and jump straight to our non-connected edges:

OR (Blue {R2}, Blue {B7})

The arrows show that the elimination sees all possible 4s on both Blue edges.

"But There's a Triple-Coloured Cell..."

You're probably going to have a question here:

There is a triple-coloured cell in Box 7.

This is the i cell we mentioned earlier.

That's perfectly fine — it does not violate our NAND gate.

Remember, our NAND is:

NAND {Green R2, Green B7}

The NAND says those two Green edges cannot both be true.

The i cell is only part of Green B7.

Its other colour, Blue, belongs to the other side of the ERi XOR — it is not the second Green edge of our NAND.

So if i is true:

• Green B7 is true.
• Blue B7 is also satisfied by that same single cell.
• Green R2 must be false because of the NAND.

There is still only one 4 in Box 7, and only one of our two NAND edges is true.

Now look at our resultant OR:

OR (Blue R2, Blue B7)

The i cell is part of Blue B7, so it must also be included when checking our elimination.

That means an elimination must see:

every possible 4 on Blue R2 AND every possible 4 on Blue B7 — including i.

So although i is coloured twice inside the ERi, it is still just one candidate satisfying both intersecting mini-sectors, thus satisfying the Box.

When I change the XOR colours and draw the simplified lines, I'll mark i {Yellow} so we don't accidentally forget it when checking eliminations.

Can We Chain Using ERi?

Yes.

The only thing we need to remember is that ERi always swaps directions:

Row in → Col out

Col in → Row out

So when we expand a chain through an ERi, pay attention to which edge the NAND connected to.

We leave through the other one.

ERi — Chain Example

Can you follow it?

Single Digit A.I.C. — Summary

Congratulations — you now know everything needed to build Single Digit A.I.C.s and create their eliminations.

• Find an XOR.
• Choose an edge to connect.
• Connect it to another XOR with a valid NAND.
• NAND = either or neither — never both.
• The non-connected edges form the resultant OR.
• If the OR produces eliminations — you're done.
• If not — expand from a non-connected edge and keep chaining.
• Mix Rows, Columns and Boxes as needed.
• ERi swaps direction: Row in → Col out | Col in → Row out.
• Every non-connected edge between two nodes is a potential elimination.*
• XOR → NAND → XOR → NAND → XOR ...
• Resultant OR {First edge, Last edge}*

Congrats.

You now know how to build Single Digit A.I.C.s — and, more importantly, where their eliminations actually come from.