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:
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.
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).
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).
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.
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 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.
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.
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.
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.
- Exemplar 1, x1 (score 112)
- Exemplar 2, x1 (score 112)
- Exemplar 3, x1 (score 116)
- Exemplar 4, x1 (score 122)
- Exemplar 5, x1 (score 142)
Thanks for Klaus Brenner for these examples
Comments
... by: Richard
... by: bruceamos
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.
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.
... by: Oluwadarasimi Ogunshote
What do you think is a reasonable depth to stop extending the chain?
... by: Peter Hopkins
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
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
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
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: ATheorist
... by: Stephen Carman
... by: gerp124
Any advice?
Thanks in advance!
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: Pieter, Australia
-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!
... by: Anton Delprado
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
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
... by: Dave
... by: Laura
... by: Laura
Laura