Alternating Inference Chains

The Alternating Inference Chain (AIC) technique is what I call the Swiss army knife of Sudoku. It is a very powerful technique that combines all other techniques that you know. In short you can use this technique in very creative ways. Even better, if you really understand this technique you do not need to know any other advanced chaining techniques including x-wings, xy-chains, y-wing, simple coloring, multi-coloring and others, because AIC does everything they do and more!

For the purists, I should remark that what I am actually presenting is not strictly a chain technique, it is a network technique. It might be more accurate to call this the Alternating Inference Network Technique (AINT?).

We will start with the big picture and fill in the details later. Look at Figure 1 below. AIC starts by proving that when cell A is not an x then cell D must be an x. That done, x can be eliminated as a candidate from cells B and C. This is easy to understand because there are only 2 possibilities, either cell A is an x or it’s not. If it is, then cells B and C cannot be x. If it’s not then cell D must be an x and again cells B and C cannot be x. So in no case can cells B or C be an x. Note: running things in reverse works too, e.g. proving that when cell D is not an x then cell A must be an x also eliminates x as a candidate in cells B and C. However reversing the logic does not work, e.g. proving that when cell A is an x then cell D cannot be an x tells us nothing about cells B or C, because we cannot say anything about the case when cell A is not an x.

For Figure 1 above I chose cells A and D more or less at random. Any pair of cells could have been chosen. Figure 2 above is an illustration with a different choice of cells A and D which could eliminate x as a candidate from as many as 6 other cells (B, E, F, C, G and H). If you can picture the situation where cells A and D are in the same row, column or block then you should see how it would be possible to eliminate x as a candidate from as many as 7 cells.

The trick then is to prove that if cell A is not an x then cell D must be an x. The good news is that any technique of analysis that you know may be used. The bad news is that figuring out where to start (e.g. deciding which cells are A and D and which digit is x) is more an art than a science. After all, many choices of A, D and x will give you no information at all because the cells B and C (and others as the case may be) may already be filled in or perhaps x is not a candidate in any of those cells. So let’s look at some examples.

Before we begin, a little explanation of the descriptive convention I will use in the examples is in order. I am going to use the RxCy notation to describe the location of cells in the grid. For instance, the cell in the upper left hand corner of the grid (row 1, column 1) is R1C1. The cell in the lower right hand corner (row 9, column 9) is R9C9.

In the illustration below (Figure 3) the puzzle has been solved as far as it can be using the basic solving and analysis techniques that we have described to this point. The small red digits indicate the candidate sets in each of the empty cells to the best of our knowledge after applying virtual cross-hatching and tuples analysis. Use the “Next step” and “Previous step” buttons to step through the Alternating Inference process.

If you are familiar with the x-wing technique you may have recognized this example as an x-wing. In fact you may be thinking that the x-wing technique would be a better one to use here because it would also eliminate 1 as a candidate in R5C8. However, a second application of the AIC technique (prove that if R6C8 is not 1 then R7C8 must be 1) will eliminate 1 as a candidate in R5C8. Try it, see if you can do it.

So is the AIC technique better than the x-wing technique? Yes and no. Obviously, if you only know the AIC technique you should be able to find all x-wings. But if you know the x-wing technique you should be able to find them much faster and easier than if you used the AIC technique. So AIC is more powerful, but not as easy to use.

Below is another illustration (figure 4) of using the AIC technique on the same puzzle after the result of the previous example and the suggested problem for the reader. This is a more complex example and better illustrates the power of AIC. Again, just use the “Next step” button below the illustration to step through the example.

You may have noticed how every other step in the illustration above alternates between can’t be and must be. There is a technical reason for this and if you are curious see the write-up on AIC at Sudopedia. In practice, you might not explicitly state all the steps, but they should be there. For instance, in the example above, after showing that R8C1 must be an 8, we could immediately deduce that R5C1 must be a 6, but the intermediate step is still there (R8C1 must be 8 implies R5C1 cannot be 8, and then R5C1 cannot be 8 implies that it must be 6) even though we don’t explicitly state it.

There is another way to use alternating inference chains (or networks). Consider the 2 illustrations below (Figures 5 and 6). If we begin by assuming that cell A (in either Figure 5 or 6) cannot be an x and then we use the alternating inference technique to prove that cell B must be a y. In that case we can eliminate y as a possibility in cell A. We can also eliminate x as a possibility in cell B. As before, there are only 2 possibilities, either cell A is an x or it’s not. First if cell A is an x then it is not a y, and if cell A is not an x then we have proved that cell B is a y and so again cell A cannot be a y. To prove that x is eliminated from cell B, when cell A is an x cell B cannot be an x, and when cell A is not an x we have proved that cell B must be a y and so again it is not an x. The examples above of constructing alternating inference chains (and networks) work for this case too, the only difference is that the chain ends by proving that the terminal cell must be y, not x and cells A and B must be able to “see” each other.

There is still one more way to use AIC. Suppose you create a chain that starts and ends on the same cell. If you began by assuming the cell could not contain an x and ended proving that in that case it must be a y then you have eliminated all candidates except x and y from that cell.