Print Version Page Index
Solvers
Puzzles
Basic Strategies
Tough Strategies
Diabolical Strategies
Extreme Strategies
Deprecated Strategies
Str8ts
Other

Order Now!
Order Now!

# Alternating Inference Chains

Chaining strategies now take a new leap with Alternating Inference Chains. These extend X-Cycle into a new dimension - where X-Cycles stuck to a single number, AICs use any candidate number.

AICs encapsulate all the discussion of chaining strategies so far. It's very useful to split out chain-like strategies into X-Wings, XY-Chains, Forcing Chains, XYZ-Wings, X-Cycles, Nice Loops and so on, since they have special characteristics which make them spottable. But it turns out they are all part of a larger extended family.

As we saw in the previous chapter, alternation is just what X-Cycles are about. However, you'll remember that X-Cycles are applied only to a single candidate number. AICs, on the other hand, take everything from an X-Cycle and extend the logic to as many different candidate numbers as necessary.

AICs ask the question "How many ways are there to make a strong or a weak link?" If there is more than one way, we can join them up in an alternating manner and make deductions leading to eliminations. Let's look back on the previous chain-like strategies and note the following:

• We can link two candidates of the same value in a unit - this is called "bi-location" (X-Cycles).
• We can link two different candidates in the same cell - this is called "bi-value".

There are also other ways (see later articles), but for now let's keep it simple and stick to these two dimensions - links between cells and within cells.

## Nice Loops Rule 1

Nice Loops that alternate all the way round are said to be 'continuous', and they must have an even number of nodes. With a continuous AIC, candidates are not removed from the loop since the loop does not have any flaws. Instead we are looking to eliminate on the units that can be seen by two or more cells that belong to the loop.

Specifically, if a unit has an ON number X and an OFF number X then one or other will be the solution. All other candidates X in that unit can be removed. These are called off-chain eliminations. Take this example:

AIC (Alternating Inference Chain) Rule 1:
+4[B7]-4[B2]+7[B2]-7[B5]+6[B5]
-6[H5]+4[H5]-4[H7]+4[B7]
- Off-chain candidate 7 taken off B3 - weak link: B2 to B5
- Off-chain candidate 6 taken off J5 - weak link: B5 to H5

Two off-chain eliminations occur on the weak links B2 to B5 (candidate 7) and B5 to H5 (candidate 6).
This is a classic and pleasingly short Continuous Alternating Inference Chain.
Starting a B7 we turn 4 ON.
This removes the 4 in B2 turning on 7 in that cell.
That turns OFF 7 in B5 turning on 6.
6 in B5 turns off 6 in H5.
That turns on 4 in H5 removing 4 in H7
Which confirms 4 must be ON in B7

Thus...there is no contradiction in the loop. The nice thing about Nice Loops is they can be reversed. Try starting with 4 ON in B7 and turning 4 OFF in H7 - it will come back round with the same conclusion. In fact, the loop is especially "Nice" because you can start with any candidate in the loop and work your way round, provided it is the same On/Off state as described in the example.

So having proved the loop we can look for extra candidates on any unit linked by the chain - or indeed, extra candidates in the same cell where an ON/OFF has occurred. (There are none in this case, only bi-value cells have been used).

Off-chain eliminations can also occur within a cell. In this excellent example sent to me by Andreas von Delius, there is a fine Nice Loop. It can start anywhere and can be traced in either direction, but the solver picks it up on A3. The loop picks out a series of 6s and 2s that alternate on and off. All the links between cells are strong links, but there are two switches between 2 and 6 in the loop. In those cells, A8 and H1, other candidates exist. 2 or 6 will be the answer - we don't know which yet, but one or other, so other candidates in those cells can be removed.

AIC (Alternating Inference Chain) Rule 1:
+6[A3]-6[C1]+6[H1]-2[H1]
+2[H7]-2[G8]+2[A8]-6[A8]+6[A3]
- Off-chain candidates 8/9 taken off cell H1, link is between 6 and 2 in H1
- Off-chain candidates 4/9 taken off cell A8, link is between 2 and 6 in A8

## Nice Loops Rule 2

Now we turn to flawed loops - ones that show a discontinuity. In terms of strong/weak links, there are two types, as described in the article on X-Cycles. Those where two strong links join up and those where two weak links join up.

If the adjacent links are links with strong inference (solid line), a candidate can be fixed in the cell at the discontinuity. It removes all other candidates as is the solution to that cell. This type is unfortunately much rarer than the Nice Loop Rule 3, two weak links.

This AIC starts and ends in A2. Setting 5 to be OFF creates a loop and a contradiction - that 5 must be ON if 5 is OFF. So removing the 5 forces it to reappear! We can't safely remove the 5 in A2 so we must set it - removing the other candidates.

AIC on 5 (Discontinuous Alternating Nice Loop, length 8):
-5[A2]+5[G2]-3[G2]+3[G8]
-3[B8]+3[A9]-5[A9]+5[A2]
- Contradiction: When 5 is removed from A2 the chain implies it must be 5 - other candidates 1/8 can be removed

In terms of strong/weak links, we have a candidate where two strong link join up, hence the thick lines drawn by the solver.

## Nice Loops Rule 3

Our third rule dictates what happens when two weak links form a discontinuity in a loop:
If the adjacent links are links with weak inference (broken line), a candidate can be eliminated from the cell at the discontinuity. In terms of ON/OFF this is where you try and set a candidate to be ON but the loop comes round and shows that doing so forces that candiate to be turned OFF.

A2 is again the start and end of the loop (coincidence, its a completely different puzzle).
By setting A2 to be 5 (+5[A2]) we turn off 5 in A7
That leaves 7 in A7 turning off 7 in F7.
The strong (bi-location) link makes 7 on in F2.
That removes 7 in E2 making 5 the solution in that cell.
If 5 is ON in E2 it has to be OFF in A2....

AIC on 5 (Discontinuous Alternating Nice Loop, length 8):
+5[A2]-5[A7]+7[A7]-7[F7]
+7[F2]-7[E2]+5[E2]-5[A2]
- Contradiction: When A2 is set to 5 the chain implies it cannot be 5 - it can be removed

## In summary...

AICs are chains of links going across a unit and within a cell.

If a candidate is turned ON you create a weak link turning OFF any other candidates in that cell and across the units it can see.

If you turn a candidate OFF you can turn ON other candidates in that cell (if there are only two candidates in the cell - bi-value) or across the unit if candidate X occurs just twice (bi-location).

However, bi-value and bi-location are just two ways of making chain links. There are other interesting ways of making chain links: Grouped Cells and Almost Locked Sets are documented here and other patterns as well can be made into links, even Unique Rectangles.

## AIC Exemplars

These puzzles require an Alternating Inference Chain strategy at some point but are otherwise trivial.
They make good practice puzzles.
All are non-syemtrical but valid Sudoku puzzles.
Thanks for Klaus Brenner for these examples

 Go back to Grouped X-Cycles Continue to AICs with Grouped Cells

Email Address - required for confirmation (it will not be displayed here)

 Please enter theletters you see: Remember me
Email addresses are never displayed, but they are required to confirm your comments. When you enter your name and email address, you'll be sent a link to confirm your comment. Line breaks and paragraphs are automatically converted - no need to use <p> or <br> tags.

## ... by: Peter Hopkins

In the first Nice Loops 1 example above, you say:

The nice thing about Nice Loops is they can be reversed. Try starting with 4 ON in B7 and turning 4 OFF in H7 - it will come back round with the same conclusion.

I believe you mean that we can start with 4 OFF in B7 and ON in H7. This gives us:

-4[B7]+4[H7]-4[H5]+6[H5]-6[B5]+7[B5]-7[B2]+4[B2]-4[B7] completing the loop.

If we start with 4 ON in B7 and reverse the direction in the example, we get stuck, because 6 is OFF at H5, and there is no strong link allowing us to turn 6 ON in another cell in column 5.

The ability to reverse a Nice Loop is important, because it proves the strategy allows candidate elimination. In the example puzzle, whether B7 is 4 or not, the Nice Loop working in both directions proves that either B2 or B5 is 7, and either B5 or H5 is 6, and that is the basis for the eliminations. If the Nice Loop could not be reversed, all it would prove is that B2 or B5 is 7, and B5 or H5 is 6 on the condition that B7 is 4.

## ... by: Robert

D4 - the link between A3 and C1 is a strong link. However, every strong link is also a weak link, and a weak link is what is needed at that position in the AIC. So it is treated as weak, even though it is strong.

The logic of the weak link is that "on" at one end implies "off" at the other, but this is also true for strong links. What is true *only* for strong links is that "off" at one end implies "on" at the other, but this is not needed in the example.

## ... by: D4

Quick question.
In the second example, why is a3 to c1 a weak link if those places are the only two places for a 6?

## ... by: Robert

This one was quite challenging, but I did manage to get software working to find alternating inference chains. My original version was so slow as to be unusable; my latest version is about 12,000 times as fast.

There must be some theoretical maximum for the longest possible chain - does anyone know what it is? There are only 729 possible combinations of cells/values even if a puzzle has no clues at all, so there cannot be a chain longer than this. But the requirement to have strong links must cut the maximum possible length down a bit. I'm just not sure how much.

In my database of 100 puzzles that cannot be solved using the most basic techniques, the longest chain I found was 47 links. That's when I used only basic techniques and AIC. When I add other techniques, the longest chain found in my sample is 33 links. It's one thing to have the computer search for these, but trying to find a chain of this length manually is, well, challenging

## ... by: Brett

I know it's a little late to reply to gerp124's question, but since it's likely someone else will have the same question in the future, I'll give my method here.

First I look through all bi-valued cells (then tri-valued, then quad-valued, etc.) until I see one with strong links to a candidate in another cell with a in the same box/row/column. If I find one I'll mark that candidate. Then I'll look through all the strong links to that candidate and alternate between two markings around them creating a 3D medusa.

Once I find one of these 3D medusas (and do any eliminations it creates), I look through each of the candidates seen by the 3D medusa and see if it can make any strong links, and if so, create a 3D medusa with it using 2 more alternating markings. Off to the side of the sudoku grid, I'll draw the markers and how they see each other, using those to represent the chains (= for weak, - for strong, like in the article).

I'll then look through each marking seeing either 3D medusa above and do the same.

After doing this, I can see both Nice loops 1 and 3 (and some 2) using my diagram on the side. (Nice loop 3s reduce to Nice loop 2s in the diagram). In the case of nice loop 1s, after marking the eliminations, I'll re-mark all the 3D medusa involved and redraw the diagram.

Then, I'll separate each sequence of chains of =-=-...-=-= from the diagram and look through the entire puzzle to see if there are any candidates not included in any of the 3D medusas that see the markings at both ends of the chains. This'll find the remainder of the nice loop 2s.

After finding all possible eliminations with this, I'll look through each 3D medusa and see if I can create additional links using grouped cells, ALSs and Empty Rectangles, as described in other articles on this site.

After finding all the possible eliminations, I will mark all the candidates to notify that no more AICs can be found using them. If there are any unmarked candidates which can be used to create 3D medusas, I will repeat the process with those.

Although it's a tedious process (and not very efficient), it should find all AICs within the puzzle.

## ... by: ATheorist

Nice Loops Rule 1 becomes a lot more simple to understand if one notes that when a continuous loop (of any sort) is found, all links within it become strong - of course, as noted below, strong links also count as weak links, when you need them to.

## ... by: gerp124

So... I can follow the reasoning when the solver shows me the way, but I can't for the life of me figure out how to spot them!

## ... by: Pieter, Australia

In your first example in AIC's/Nice Loops Rule 1, the chain quoted above starts & ends in a different cell to the graphic. The solver quotes the chain as:
-4[B2]+7[B2]-7[B5]+6[B5]-6[H5]+4[H5]-4[H7]+4[B7]-4[B2].

In the example in AIC/Nice Loops Rule 2, the chain quoted goes the opposite way around to the graphic. The solver quotes:
-5[A2]+5[G2]-3[G2]+3[G8]-3[B8]+3[A9]-5[A9]+5[A2].

I'll bet you updated the graphics Andrew after a solver version update, but didn't realise the solver now did them differently!

## Wednesday 1-Feb-2012

It is interesting to note that 3D Medusas (or should that be gorgons?) are expressible as AICs as well.

You have to note that strong links are also weak links. Then you have cells with opposing colours have alternating links starting and ending strong. Cells of the same colour start strong and end weak.

Type 1-6 Medusas are then AICs rule 3. I'll leave the specifics to the reader.

Oh, Finned X-Wings and if you really want to push it Naked Pairs, Hidden Pairs and Pointing Pairs (although not triples) are too.

## ... by: Guy Renauldon

This is to reply to Laura question dated Saturday 17-Oct-2009

When three numbers, ore more, are in a cell, this is a weak link. Yes, if one number is true, each one of the others is wrong. But one number wrong does not implies one of the two other numbers true. We don't know which one is true. This is very important to understand the chain strategies.

A strong link in on bivalues cells only.

Guy

To Andrew Stuart
Thank you for your excellent site.
Guy

## ... by: Fred

I am just learning about strong and weak links.Your last example is confusing to me since they all look like strong links. what makes some of them weak.

## ... by: Dave

I hope you update the AIC strategy soon. I still have problems with AIC's.

## ... by: Laura

when is the alternating inference chain strategy going to be updated

## ... by: Laura

On the aic strategy, is there a limit to how many strong links having weak interference you can use on 1 example? Also, when you go from 1 number to another in the same cell and there are 3 numbers in that cell, is that a weak link or strong? Thank-you

Laura
Article created on 12-April-2008. Views: 158073