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
There have been a number of Sudoku techniques, commonly known as "patterns",
discovered over the years - Skyscraper, W-Wing, Two-String Kite, Swordfish,
XY-Wing - 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.
In my eyes AIC is a natural extension to the idea of a pattern, as it relies on the same concept: a pattern is an arrangement of candidates that result in an elimination. The proof for these eliminations can be simple or it can be complex, but at the end of the day, once you've internalised it you can apply this pattern by rote. The burden of proof is shifted to an earlier point in time - if you know how an X-Wing works, you no longer have to rigorously prove every single X-Wing you encounter, you can be satisfied that the eliminations will be correct based on your existing knowledge.
AIC defines a set of rules for constructing arbitrary patterns. As long as these rules are followed, the resulting pattern will be valid and its eliminations will be apparent. It is not necessary to go through the chain thinking "well if this is 6 that can't be 6, so this has to be 2, then this can't be 2", or anything like that - we've shifted the burden of proof onto a simpler statement which has already been verified. As long as the components of the AIC are valid, its eliminations automatically are too.
I will first prove the logic 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
While the previous section details how to prove an existing AIC, it still 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 depth-first search, or "the fun way", and breadth-first search, "the boring way".
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.
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
- - -
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