SudokuWiki
SudokuWiki.org
Strategies for Popular Number Puzzles

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.

AIC Rule 1
AIC Rule 1 : Load Example or : From the Start

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 in cells
Off-chain eliminations in cells : Load Example or : From the Start
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.

AIC Rule 2
AIC Rule 2 : Load Example or : From the Start
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.

AIC Rule 3
AIC Rule 3 : Load Example or : From the Start
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....
Contradiction!

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





Comments

Comments
Talk

... by: bruceamos

Tuesday 13-Jun-2023
My sudoku solver has a method for eliminating candidates.
Basically, it starts by assuming a candidate is true and at each step
it must deduce that another candidate is true until it arrives at a
contradiction. As a result the original proposition is eliminated.

Do you consider this to be a trial and error method or a legitimate technique?
It is not a full blooded trial & error method because at each step the options are severely
limited. We are not allowed any deductions except to assert that another proposition is true,
either because it is the only value left for a point or it is the only place in a unit where
the value can exist.
If you consider this not to be a trial and error method, then there I have a complete logical
solution for the Weekly unsolvable 545.

Here is an example step taken near the beginning of the solution for the weekly unsolvable 545.
The three previous steps were Chain steps eliminating I5=7, I5=8, B5=6.
CHAIN: I3~7 D3=7 D8~7 A8=7 B9~7 B5=7 -> I5~7
CHAIN: I7~8 D7=8 D2~8 B2=8 A1~8 A5=8 -> I5~8
CHAIN: B5~7 B9=7 B9~9 C8=9 C8~6 B7=6 -> B5~6

Key step 4
A B C D E F G H I
1 1458 128 7 3 26 2568 1245 9 2456
2 6 2389 249 5789 279 1 23457 2345 23457
3 135 1239 129 5679 4 256 8 12356 23567
4 9 1268 1246 1456 136 7 12345 1234568 234568
5 1478 178 3 2 169 456 14579 14568 4569
6 147 5 1246 1469 8 346 123479 12346 234679
7 2 136 5 1468 136 9 34 7 348
8 37 4 69 678 5 2368 239 238 1
9 137 1379 8 147 1237 234 6 2345 23459
A5~7 else D8=7, B9=7, A1=8, C8=9, F8=6 -> no 8 in COLUMN F
Chains CPU: solve=135, chains=186, XChains=21905 (microseconds)


The logical steps are as follows:

If A5=7 then D8=7 (A5=7 -> A8~7 -> D8=7 as there are only two 7's on row 8)
then B9=7 (since A5=7 eliminated both A8=7 and A9=7)
A5=7 -> A1=8 (only remaining 8 in Column A).
-> C8=9 (only remaining 9 in the box surrounding B8)
-> F8=6 (only remaining 6 in row 8 since C8=9 and D8=7)
Now both F1=8 has been eliminated by A1=8 and F8=6 so there is no place for an 8 in Column F.


Ymiros replies:Wednesday 5-Jul-2023
I do not understand what you are trying to say, what you are describing is just a "Unit Forcing Chain" as it is described on this wiki. (Although you are looking at it in reverse)
The solver is unable to continue without "Trial and Error" after eliminating 7 from what you call A5 and also 8 from what you call B5.
Add to this Thread

... by: Oluwadarasimi Ogunshote

Saturday 19-Feb-2022
Hey, I am coding a sudoku solver and I wanted to ask a question.

What do you think is a reasonable depth to stop extending the chain?
Andrew Stuart writes:
That is a very good question. If you are coding a depth-first algorithm you need to set a limit otherwise it takes to long going down rabbit holes. I have a limit of 12. Reasonable compromise. However I have also coded the NRC algorithm which is breadth first and does not need a limit. But due to memory limits it is not used for the online solver. - [Del]
Add to this Thread

... by: Peter Hopkins

Thursday 9-Sep-2021
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.
REPLY TO THIS POST

... by: Robert

Thursday 21-Jan-2021
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.
REPLY TO THIS POST

... by: D4

Wednesday 25-Nov-2020
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?
REPLY TO THIS POST

... by: Robert

Saturday 20-Jun-2020
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
REPLY TO THIS POST

... by: ATheorist

Friday 26-Feb-2016
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.
REPLY TO THIS POST

... by: Stephen Carman

Friday 27-Mar-2015
AIC rule three shows an example which violates the first rule of chains that there be an even number of nodes. I'm not sure why it works in every example and with the solver but when I try to do it on my own I fail almost every time. The 7 nodes in this example thus leave me more confused. So basically what is the reason for the even node rule and why doesn't it matter in this example for RULE 3??
REPLY TO THIS POST

... by: gerp124

Thursday 25-Sep-2014
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!

Any advice?

Thanks in advance!
Brett replies:Tuesday 23-Aug-2016
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.
Add to this Thread

... by: Pieter, Australia

Wednesday 27-Jun-2012
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!
REPLY TO THIS POST

... by: Anton Delprado

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.
REPLY TO THIS POST

... by: Guy Renauldon

Monday 7-Mar-2011
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
REPLY TO THIS POST

... by: Fred

Monday 27-Sep-2010
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.
REPLY TO THIS POST

... by: Dave

Monday 13-Sep-2010
I hope you update the AIC strategy soon. I still have problems with AIC's.
REPLY TO THIS POST

... by: Laura

Monday 17-May-2010
when is the alternating inference chain strategy going to be updated
REPLY TO THIS POST

... by: Laura

Saturday 17-Oct-2009
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
REPLY TO THIS POST
Article created on 12-April-2008. Views: 179178
This page was last modified on 18-January-2015.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles, Privacy, 2007-2024
Playwire