AIC
There is no Sudoku technique which has been as frequently mistreated and misunderstood as Alternating Inference Chains. Since its introduction in 2006 it has become the most popular chaining method, but despite that, there are very few resources online that correctly detail the concept as originally expressed. Instead the majority repackage an earlier chaining technique called Nice Loops, changing a few terms here and there.
With this article I hope to clear up any confusion and document my interpretation of the concept of AIC, and show how it can be applied to Sudoku to solve puzzles, from the intermediate to the incredibly complex. The primary source is the original thread linked above. This article assumes a familiarity with common Sudoku terminology.
Table of Contents
Introduction
You're free to skip this introduction if you're not interested in the history or justification of AIC and just want to learn how to use it.
There have been a number of Sudoku techniques, commonly known as patterns, discovered over the years - Skyscraper, W-Wing, BUG+1, ALC, Swordfish, XY-Wing, Tridagon - to name a few. We've built up an impressive collection of them. However, no matter how many of these named moves we find, there have always been puzzles that resist them. These puzzles require logical analysis that can't be so easily hammered down into repeatable patterns so a number of chaining strategies have sprung up over the years in order to make sense of and untangle the more complex puzzles.
The simplest chaining strategies are based on a concept called Forcing Chains. I've covered them in another article in the past but the basic gist is that you "look ahead" at what will happen if you guess a certain candidate, and if it leads to a contradiction later on, that candidate is incorrect and can be removed. The "chain" consists of the implications that lead from the guess to the contradiction. It's simple but very effective: every puzzle can be solved with this method, although it may require multiple guesses at once. However you don't learn much about the puzzle by solving it like this - every move boils down to proving that a specific guess is wrong because "it just is", either you run into a contradiction sooner or later or the puzzle ends up being solved. It's not really a skill that you can get better at with practice.
Needless to say, people came up with their own variations on Forcing Chains. A common variation is that you identify a cell or region with 2 possible solutions, then you "look ahead" from each of those possible solutions, and any eliminations/placements common to both outcomes can be eliminated/placed. This tends to lead to far more eliminations as you're not limited to the single guess you started with. Another advantage of this method is that you can colour in the candidates involved in each scenario with two colours and easily track the evolution of each scenario across the grid. You can even track 3, 4, or more possible solutions at once if you have enough coloured pens.
Another option is to more strictly define and limit the implications you're allowed to use in the chain. This is what Nice Loops does, and it's the closest precursor to AIC. There are two major "links" used in Nice Loops: "if A is true then B is false", and "if A is false B is true". By alternating between these you build a longer chain: "if A is true B is false, if B is false C is true, if C is true D is false, if D is false E is true", and so on. If this chain continues to the point that it loops back on itself, you have either a Discontinuous or a Continuous Nice Loop, depending on whether the logic implies a contradiction or not.
While Nice Loops had many advantages over other methods, they still left a lot to be desired: for the most part they could only eliminate one candidate - the initial presumption. They were also cell-based and struggled to incorporate more complicated links, leading to dozens of rules that dictated how you can continue a chain and what exactly can be eliminated. Before long it became a huge unwieldy mess. A newer method was sorely needed.
Enter "Myth Jellies", who posted a thread in April 2006 which finally solved the problem: he described AIC, a chaining technique that uses no presumptions, no "if -> then" logic, no brute force, no contradictions, no colouring. It achieves this by abstracting the puzzle into simple logical relationships, which are then combined together, proving new relationships in the original puzzle. Where before an X-Wing required 14 different Nice Loops(!) to find all possible eliminations, a single AIC eliminates them all. Every named technique can be expressed as AIC, typically short ones too. All the advanced logic like ERI and ALS are also simple to integrate into AIC to obtain very difficult eliminations.
I will first explain the theory behind AIC and then show how it can be applied to Sudoku. Bear with me.
AIC in Theory
AIC is a logical technique where you make deductions about relationships between premises, then combine these deductions in order to prove new, more complex relationships between the same premises.
A premise is a fact which can be either true or false, but we may not know which one is the case yet.
An inference is a proven relationship between the possible states of two premises in conjunction.
AIC involves two provable relationships between premises and a resulting statement.
Strong inference: both cannot be false at once. This is notated with an equals sign (=).
Weak inference: both cannot be true at once. This is notated with a dash (-).
A = B - C = D => A = D
That's it.
Now in more human terms: A, B, C and D are all premises. They can be true or false but we don't know which is which yet. What we do know is that there is a strong inference between A and B, as well as between C and D, and we also know there is a weak inference between B and C.
We can use this to construct an chain that alternates strong-weak-strong, starting and ending on a strong inference, which proves that there is a strong inference between A and D - both cannot be false at once. All of these relationships are two-way so they work the same when read forwards or backwards.
To prove that there is a strong inference between A and D, consider what would happen if both were false:
If A is false, B cannot also be false or it would violate the strong inference between them, so B is true.
If D is false, C cannot also be false or it would violate the strong inference between them, so C is true.
Now B and C are both true, but this violates the weak inference between them. Therefore A and D both being false leads to an invalid state, so A and D cannot both be false.
Furthermore building a chain of strictly alternating strong-weak-strong inferences of any length has the same effect: as long as the chain starts and ends with a strong inference, the end premises will have a strong inference between them.
Once these inferences have been defined and the resulting statement A=B-C=D => A=D has been proved, it never has to be revisited. It is a fact that you can take for granted forever. As long as all inferences are valid, so is the AIC itself.
AIC in Practice
Now that we have a logical basis for the technique let's apply it to Sudoku. We need to define our premises and find logical inferences between them.
Sudoku is a game of eliminating possibilities until only one remains, which must be the solution. This article will make use of full candidate notation, which involves pencilling in little numbers showing all the possible values for each unsolved cell. These candidates are removed when one is proven to be incorrect.
.9.3..1.4.6.5.4.8..2......9..........16..57....8.62.3.......5.....983...2.7......
Each of these candidates is actually a premise: for example in r1c1 we have two candidates which each stand for the premise that r1c1 contains a 7 and the premise that r1c1 contains an 8. For brevity I will refer to these as (7)r1c1 and (8)r1c1. The premise (7)r1c1 can be true or false: either r1c1 contains 7, or it doesn't. We don't know which of these is the case yet.
We can obtain our basic inferences directly from the rules of Sudoku.
Every digit from 1-9 must be present exactly once in each row, column, and box.
Additionally, every cell must contain exactly one digit.
This article makes use of Eureka notation so I highly recommend you read the link if you're unfamiliar with the notation.
Basic Weak Inferences
A digit may not appear in the same region more than once. Therefore any pair of candidates that share the same digit and region share a weak inference. An example is all the 3s in row 2: for any given pair of these 3s, both of them cannot be true at once, or there would be two 3s in row 2 which violates the rules of Sudoku. Therefore this pair of 3s has a weak inference.
This would be notated as, for example, (3)r2c3 - (3)r2c9.
A cell may not contain two digits, so any two candidates within the same cell share a weak inference. An example is all the candidates in r2c9: for any given pair of these candidates, both of them cannot be true at once, because a cell can only contain one digit.
This would be notated as, for example, (2-3)r2c9.
The weak inferences (blue) of (3)r2c9 (purple)
Basic Strong Inferences
The two most basic & readily available strong inferences are bivalue and bilocal candidates.
Any cell that contains two candidates is called bivalue. Its candidates have a strong inference between them because the cell needs to have a digit in it, so at least one of the candidates must be true. There are 16 of them in the puzzle above. An example is (7=8)r1c1.
Any candidate within a region that appears exactly twice is called bilocal. An example is the 8s in row 1: row 1 must contain an 8, the two possible positions for it are (8)r1c1 and (8)r1c6. The row needs an 8 in it so at least one of these must be true, so neither can be false, therefore we can say (8)r1c1 = (8)r1c6.
This is often the most common type of strong inference - in the puzzle
above there are 20 in the rows, 20 in the columns, and 4 in the boxes
(excluding duplicates) - 44 in total.
2 bivalue strong inferences and 3 bilocal strong inferences in different regions
It
is worth noting at this point that a pair of premises can have both a
strong & weak inference, or they can have only one, or they can have
neither. When constructing an AIC all that matters is that the
inferences are valid and that they alternate strong-weak-strong,
starting and ending on a strong inference. These inferences are also
called "links", i.e. "strong link", "weak link", but I will avoid using
those terms as they have loaded meanings originating from earlier
chaining methods.
When used to build AIC, these two simple inferences are enough to solve any puzzle up to Sudoku.Coach's "Hell" difficulty, or SE rating up to ~7.6.
Utilising AIC to Eliminate Candidates
We have a total of 60 bivalue/bilocal strong inferences in the example puzzle and many ways to connect them through weak inferences. I won't detail the process I use to search for AIC until later in the article - for now let's look at an example AIC, see how to prove its validity, and how to use it to progress through the puzzle.
(6)r1c8 = r1c6 - r3c4 = (6)r9c4 => r9c8<>6
Note that in the diagrams used in this article (and the other articles on my blog), red lines drawn between two premises correspond to strong inferences, and blue lines correspond to weak inferences. The candidates eliminated by an AIC are highlighted in red.
A
very important point to stress here is that there's no "if-then" logic
following the chain in AIC. In order to prove the validity of an AIC, it
is sufficient to prove the validity of all of its individual inferences
- nothing more is required.
The two strong inferences used in this AIC are bilocal candidates so they're easily verified by making sure their regions contain exactly 2 cells with 6 as a candidate. The weak inference is also easy to verify: both premises are candidate 6s and they're contained within the same box, so both can't be true, a box can only have one 6 in it. The AIC is valid so it successfully proves that (6)r1c8 = (6)r9c4, by A=B-C=D => A=D.
To quote Myth Jellies in the original thread:
"Quite simply, at least one or the other (possibly both) of the two endpoint candidates (or candidate premises) of an AIC is true. Any deductions that you can make based on that are valid. This tends to produce the best results if the endpoints either share a group, or if the endpoints involve the same candidate. When your chain endpoints satisfy one of those conditions, it is time to check for any deductions."
You can eliminate any mutual peer of the two endpoints. In this case both the endpoints involve the same candidate (6), so any 6 that sees both the endpoints can be eliminated. In the example puzzle (6)r9c8 sees both endpoints so we can eliminate it. This short AIC is also known as a two-string kite.
Type 1 elimination in the intersection of r9 & c8
The case where both endpoints are the same candidate digit is called Type 1. There are three elimination types, and they're not particularly important to remember, but I'll point them out.
(1)r8c3 = r2c3 - (1=7)r2c1 - r2c9 = (7)r8c9 => r8c9<>1
Another example AIC, this time a bit more complicated. We have two bilocal strong inferences and a bivalue strong inference in the middle of the chain - this arrangement is known as an S-Wing. You can verify for yourself that the strong & weak inferences are valid.
This AIC proves that either (1)r8c3 or (7)r8c9 are true (or both could be true). In both cases 1 cannot be in r8c9 so it can be eliminated.
Note one of the mutual "peers" is within the cell itself, thanks to the rule that a cell may only contain 1 digit. The elimination case where one of the peers is cellwise is called Type 2.
(4=8)r5c4 - (8=2)r5c9 - r5c8 = (2-7)r8c8 = (7-6)r1c8 = r1c6 - r3c4 = (6)r9c4 => r9c4<>4
AIC in Sudoku can be quite long - this one has 6 strong inferences and it's the shortest possible AIC for this elimination. It's another Type 2 elimination where the peers are found within the intersection of column 4 and cell r9c4.
(1=3)r2c3 - (3=2)r2c7 - (2=4)r8c7 - (4=1)r8c3- => r2c9<>3, r8c128<>4
Later in the solve we get this Type 3 AIC. Its endpoints are also mutual peers of each other, so the AIC forms a continuous circuit called a Ring. You can arbitrarily cut this Ring at any of the weak inferences and you have a new Type 1 AIC, so in effect you can treat every weak inference in the Ring as a strong inference for the sake of eliminations. This also proves a weak inference between all strong inferences which can be important in complex chains.
Rings are extremely powerful and can give you loads of eliminations so it's always nice to find them. In Eureka notation it's typical to add an extra "-" to the end of the chain string to show the looping nature of the Ring.
(4)r3c3 = r8c3 - r9c2 = (4-6)r9c4 = r3c4 - (6=3)r3c7 => r3c3<>3
This AIC is sneaky. Why? Because it's wrong! All of the weak inferences check out, and most of the strong inferences check out, but one is invalid - the bilocal strong inference between (4)r9c2 and (4)r9c4 is incorrect. The statement "both cannot be false" cannot be conclusively proven yet, because the 4 in row 9 doesn't have to be in these two positions - it can also be in r9c7. We can't trust this AIC so we can't eliminate this 3 yet. When solving with AIC it is of the utmost importance that you make sure all your inferences are valid.
Actually Finding Them
The previous section is still quite theoretical as it skips over the entire process of finding AIC by hand. I'll detail 2 possible processes that you can use to find AIC.
The 2 processes are breadth-first search, or "the boring way", and depth-first search, "the fun way".
The Boring Way
This is how my solver finds all possible AIC in the grid and it's efficient enough that it can be done manually, although it takes quite a bit of time depending on how many strong inferences are present in the grid. I'll use a simplified grid for the sake of demonstration.
List every strong inference present in the grid.
(1=2)r2c2
(1=2)r5c8
(1)r2c8 = (1)r5c8
(2)r2c2 = (2)r8c2
(2)r8c2 = (2)r8c8
(2)r5c8 = (2)r8c8
Now go down this list, and for each of the strong inferences, connect the endpoint premises to all possible strong inferences through their weak inferences. You'd start with (1=2)r2c2 and look at the endpoint (1)r2c2 first: (1)r2c2 has a weak inference with (1)r2c8 which gives you the AIC (2=1)r2c2 - r2c8 = (1)r5c8. This gives you the new strong inference (2)r2c2 = (1)r5c8 so check for eliminations - if there are none, add it to the bottom of the strong inference list.
Next look at the other endpoint (2)r2c2. It has a weak inference with (2)r8c2 so you can continue a chain via any strong inferences containing that premise. The 6th entry in the list gives us the AIC (1=2)r2c2 - r8c2 = (2)r8c8 which shortens to (1)r2c2 = (2)r8c8, which has no eliminations, so add it to the bottom of the list.
There's
another strong inference containing (2)r2c8: (2)r2c2 = (2)r8c2. If we
combine this with the initial strong inference we get the AIC (1=2)r2c2 -
r8c2 = (2)r2c2, which shortens to (1=2)r2c2, so it's totally redundant.
We can ignore it.
You continue like this for every strong inference in the original list. You can ignore every strong inference that is earlier in the list than your current position so it gets faster the further you get. Once you're finished, you'll have painstakingly found every single AIC consisting of 2 strong inferences. None of them eliminate candidates but your list is longer now: you found 4 new strong inferences.
(2)r2c2 = (1)r5c8
(1)r2c2 = (2)r8c8
(1)r2c8 = (2)r8c8
(2)r2c2 = (2)r5c8
(1)r2c2 = (2)r8c8
(1)r2c8 = (2)r8c8
(2)r2c2 = (2)r5c8
You can append these strong inferences to the end of your initial list and repeat the process. Keep in mind every new AIC after this point must contain the newest strong inferences in some way. This time you'll find every AIC of length 3-4. Repeating after that will give you every AIC of length 5-8, then 9-16, 17-32, and so on.
You won't have to continue for that long as the very first AIC you find in this second round eliminates candidates:
(2)r8c8 = r8c2 - (2=1)r2c2 - r2c8 = (1)r5c8
=> (2)r8c8 = (1)r5c8
=> r5c8<>2
The Fun Way
This is how I personally do it and it's a lot more engaging for me, although it is admittedly a bit scattershot. I should start by mentioning that I do this all in Windows Snipping Tool purely because it has a red and blue pen by default and you can erase an entire line by clicking on it. That makes it perfect for AIC. You can use Sudoku.coach's line tools if you're using that site. You can also do this in your head or in text but I like to build AIC visually as I am a more visually-oriented thinker.
Choose any strong inference in the grid. If you can't find one that looks promising just pick at random. I'm going to choose the 1c8 bilocal strong inference.
(1)r2c8 = (1)r5c8
Next I extend this AIC for as long as I can in both directions.
(2=1)r2c2 - r2c8 = (1-2)r5c8 = (2)r8c8
After adding each strong inference to the AIC I check for eliminations. Note it's important to check every smaller sub-AIC for eliminations during this process - so you'd check if (2)r2c2 and (1)r5c8 have any mutual peers to eliminate. That wasn't the case in this very simplified example but it can happen.
Checking eliminations can be done quickly if you keep in mind there are only 2 major elimination types: Type 1 is when the endpoint digits are the same so you look at their intersecting peer regions, Type 2 is when the endpoint digits differ so you only need to look at the cells containing the endpoints. Type 3 (Ring) AIC are uncommon but they're spotted when you're checking for Types 1 & 2.
In this case the AIC endpoints are both 2s and they happen to both see (2)r8c2, so that candidate can be eliminated. It took a matter of seconds to find this as the example grid is very simple. Every single strong inference you decide to start on will quickly reveal an elimination, try it yourself.
In a real puzzle the eliminations are not quite so plentiful so you may be extending & pruning your AICs extensively before you're rewarded with eliminations. Don't get too attached to any one chain, keep building and deleting and rebuilding, if you're not getting lucky try looking elsewhere in the puzzle. You can't guarantee that you'll find every elimination with this method, and indeed you can't use it to prove there are no more eliminations, but you'll find them most of the time if you just keep searching.
It's a lot of fun and you get a real feel for the internal logic of the puzzle, certain areas of it become familiar as you draw the same AICs multiple times throughout the course of the solve.
There are myriad tips I could give you that draw from my own experience hunting for AIC with this method, such as focusing on W-Wings and XY-Wings with no eliminations (it can be surprisingly easy to extend the chain a bit to salvage eliminations), and making sure to focus on new strong inferences derived from the most recent eliminations. These are the little things you pick up over time through practice & experience and they make a huge difference.
- - -
If
you've read and understood everything up to this point then
congratulations, you've learned AIC. With this knowledge - and a lot of practice - you can solve
roughly 99.8% of randomly generated Sudoku puzzles.
If you're like me, you won't be satisfied with that number forever - there are always harder puzzles, new challenges, new things to learn. If you're interested in learning more advanced AIC tactics, read Part 2: Exotic Strong Inferences.
Otherwise, thanks for reading and good luck solving with AIC.
Comments
Post a Comment