AIC 2
This is part 2 of my article on AIC. Originally it was part of the original
article but it got so long that I felt it was detracting from the focus of
the original, so I decided to split the article into 2. Please read part 1
if you're unfamiliar with the concept of AIC.
With the knowledge from part 1 you can solve roughly 99.8% of randomly
generated Sudoku puzzles. Everything within this subsequent article builds
on that basic introduction in order to raise that number as close to 100% as
possible. The skill ceiling for Sudoku is extremely high and there are many puzzles
that cannot be solved with classical AIC. To climb the ladder of difficulty
we will have to define more types of strong inferences.
Table of Contents
Grouping Premises
Until now we've only been considering inferences between a single pair of
candidate premises. However if you can prove that a whole set of premises
cannot all be false at once then they form what's known as a
strong inference set, and any division of this set into two subsets
(groups) will give you a strong inference between the subsets. These subsets
can be overlapping, the only restriction is that every element of the
original set has to be in at least one subset.
All instances of a digit in a row, column or box form a strong inference
set. Additionally, all the candidates within a cell form a strong inference
set, but this case is not as easy to make use of.
For a practical demonstration, in the example below, the 9s in column 8
form a strong inference set because at least one of them must be true (every
column needs a 9). We can split this into two premises: 9 being in r8c5 and
9 being contained within box 9.
The most practical way to group premises is by mutual weak inferences, as
it allows you to continue the chain.
(8)r1c8 = r1c7 - (8=9)r7c7 - r89c8 = (9)r5c8 =>
r5c8<>8
All the instances of 9 in column 8 form a strong inference set. Notice that
these 9s are contained within 2 boxes, so we can group them into two subsets
depending on which box they're in. This gives us a strong inference between
the two subsets: {9r5c8} = {9r8c8, 9r9c8}.
Three Grouped strong inferences obtained by grouping the candidates in a
row according to the box they're contained in
(1)r4c1 = r4c8 - c8b3 = (1)r1b3 => r1c1<>1
The strong inference set here is comprised of all the 1s within box 3. 1
can be in r1c7, r1c8, r1c9, r2c8 or r3c8. All these cells are contained
within either row 1 (blue), or column 8 (purple), or both (pink) - so I've
grouped them into these two subsets. The grouped link formed by this is
referred to as an Empty Rectangle Intersection (ERI) because
the other cells in that box form a rectangle. Blame whoever
named this move years ago if you find that confusing.
The first group contains the candidate premises 1r1c7, 1r1c8 and 1r1c9. The
second group contains 1r1c8, 1r2c8 and 1r3c8. The fact that 1r1c8 is
contained within both groups means this is an example of a strong inference
where the premises involved do not also have a weak inference - both can be
true if 1r1c8 is true.
Alternatively, you can split these into two groups with no overlap and
still successfully obtain the elimination:
{1r1c7, 1r1c9} = {1r1c8, 1r2c8, 1r3c8}
{1r1c7, 1r1c8, 1r1c9} = {1r2c8, 1r3c8}
But it is simpler to define the Empty Rectangle as the intersection between
a row and a column within a box, hence (1)c8b3 = (1)r1b3.
Adding these Grouped strong inferences to your repertoire will allow you to
solve maybe 50% of the "Beyond Hell" difficulty puzzles on sudoku.coach. But
to solve more than that, we're going to need even more complex strong
inferences.
Almost Locked Sets
An Almost Locked Set (ALS) is a set of N cells within a region that
together contain N+1 unique digits.
(1478)r9c578: 3 cells containing 4 digits
If any of these digits were removed from the ALS you would have a locked
Triple containing the remaining 3 digits. We can use this relationship to
prove new strong inferences. The typical way to do this is to simply say
there's a strong inference between the extra digit and the resulting locked
set. This gives us four strong inferences:
(1=478)r9c578
(4=178)r9c578
(7=148)r9c578
(8=147)r9c578
The locked set's weak inferences are just its potential eliminations, which
is every candidate in a cell that sees every instance of that digit within
the ALS.
(7=184)r9c578 - r8c8 = (4)r8c4 => r8c4<>7
This AIC proves a strong inference between (7)r9c5 and (4)r8c4, so we can
eliminate any mutual peers. It is standard to push the digit that continues
the chain to the end of the LS in Eureka notation to make the continuity of
the chain more apparent, hence (7=184)r9c578.
Only two of the ALS digits are relevant to the chain as a whole - the 4s
and 7s - so I often ignore the rest and treat ALS strong inferences as being
between the two groups of digits, effectively (7)r9c5 = (4)r9c78. Any two
ALS digit sets cannot be false at the same time because then the N cells
would have N-1 unique candidates, meaning it would be impossible to fill
them all. This has the effect that every digit in the ALS is strongly linked
to every other digit.
The same AIC with the strong inference directly between the ALS digits
(4=7).
It's not a big deal which of these you use when chaining, they're both
valid and lead to the same result in the end, so it's up to whichever you
find most convenient.
(1)r1c2 = r1c5 - (1=87)r7c56 - (7=3681)r4567c2- => r28c5<>1,
r7c78<>8, r8c56<>8, r2c2<>1, r12c2<>8,
r6c1<>8
Another important thing to note about ALS is how they act in Rings. Focus
on (178)r7c56.
Recall that when an AIC forms a Ring, all of its weak inferences are proven
to also be strong. By the same token, all strong inferences are also proven
to be weak. This has profound consequences for ALS: if two of the candidate
digits have a weak inference, that means both of them cannot be true at
once. Rephrased, this means exactly one of the candidate digits used in the
Ring (1 and 7) must be false.
As an ALS is composed of N+1 candidate digits in N cells, exactly one of
those candidate digits is false. The Ring just proved that either 1 or 7
must be false, therefore the other candidate digits in the
ALS must be true. In this case the other candidate digit is 8, so we can
eliminate all the 8s that it sees.
Same goes for the other ALS, (13678)r4567c2. The AIC proves a weak inference between (1) and (7), so all the
other digits are locked into the ALS: the ALS must contain 3, 6 and 8.
Almost Hidden Sets
An Almost Hidden Set (AHS) is a set of N digits within a region that are together contained within N+1
unique cells. It can be seen as complimentary to ALS - every ALS has an
equivalent AHS and vice versa.
(56)r9c124: 2 digits contained within 3 cells
If the (56) candidates were removed from one of the AHS's cells, the
remaining cells would become a hidden set. Again we can use this to define
new strong inferences. The Eureka notation for AHS isn't standardised as far
as I know, so I'd like to take the opportunity to advance my own standard
for them. This AHS gives us three strong inferences:
(56)(r9c1 = r9c24)
(56)(r9c2 = r9c14)
(56)(r9c4 = r9c12)
The strong inference is between the premises that (56) is contained within
particular cells in row 9. The weak inferences of an AHS are a bit more
complicated than for ALS: there are cellwise weak inferences for every cell
of the AHS (r9c124), and also regional weak inferences from every cell that
contains only one AHS digit. If this cell was part of the hidden set, it
would have an exposed naked single, so it would eliminate all other
instances of that digit in its row/col/box.
(8=7)r8c5 - r8c2 = r9c2 - (56)(r9c2 = r9c14) =>
r9c4<>8
This AIC proves that at least one of the endpoints (8)r8c5 and (56)(r9c14)
must be true. The AHS weak inference here is cellwise within r9c2.
(9=3)r6c1 - (39)(r5c2 = r5c75) - (1)r5c5 = (1)r6c4 =>
r6c4<>9
This AIC shows off the regional weak inferences from an AHS cell containing
only a single candidate, 3. I extend the convention from ALS to AHS by
putting the cell that continues the chain at the end of the AHS strong
inference (39)(r5c2 = r5c75).
(1)r1c2 = r1c5 - (1=87)r7c56 - (74)(r7c2 = r21c2)- => r28c5<>1,
r7c78<>8, r8c56<>8, r2c2<>18, r1c2<>8
As this is a Ring all the weak inferences are also strong inferences and
vice versa - the strong inferences are all weak inferences.
This has important ramifications for an AHS: we just proved that in the
pink AHS the strong inference between (47)r7c2 and (47)r1c2 is also weak,
so both cannot be true at the same time - recall that an AHS is formed
from N digits being present within N+1 cells.
If we know that two of the cells cannot both contain AHS digits, that
means one of these two cells must not contain the
AHS digits, which further implies the other AHS cells must contain
the AHS digits, therefore we can eliminate every other candidate from
them. In this example, 1 and 8 are removed as candidates for r2c2.
- - -
You won't see AHS often on Sudoku websites. There are two main reasons for
this: the first is that they're quite hard to spot when you scan the grid,
they are "hidden" after all. I miss hidden pairs all the time when I'm
solving puzzles.
The second reason is that most of the time there's an equivalent ALS that
can achieve the same thing. Here are the first two examples from this
section with their AHS replaced by the equivalent ALS:
(8=7)r8c5 - r8c2 = r9c2 - (7=148)r9c578 => r9c4<>8
(9=3)r6c1 - (3=41)r5c28 - r5c5 = (1)r6c4 => r6c4<>9
So the major use-case for them is to simplify a chain by replacing for
example a 7-cell ALS with a 2-digit AHS. However, there is a rare case where
two AHS can intersect in such a way that there is no equivalent ALS. I wrote
about it further in another article so I'll only show one example.
(514)(r4c9 = r4c342) - (2695)(r4c2 = r1589c2) =>
r9c9<>5
This is an AIC formed by two intersecting AHS. The weak inference (14)r4c2 - (29)r4c2 is easy to prove as all the candidates are
contained within the same cell, so both AHS cannot contain that
cell.
There is no equivalent AIC that you can obtain by replacing these AHS by
their ALS counterparts, as their counterparts are actually two intersecting
AALS (N+2 candidates in N cells).
Kraken Fish
If a candidate digit's locations in N base regions are contained within N
intersecting regions then you can eliminate that candidate from all non-base
positions in the intersecting regions. This is called a Fish and the common
cases are the X-Wing, Swordfish and Jellyfish for N = 2, 3 and 4
respectively.
If however these candidates are contained within N+1 intersecting regions,
this is 1 candidate or set of candidates off of being a Fish, so it's called
"Almost Fish" or "Kraken Fish". This gives us a strong inference between the
Fish and the extra candidates, which are known as the "Fins". The most
common example of this is a Finned X-Wing.
(1)r5c1 = (1)r58/c35 => r46c3<>1
Fishing is a very complicated subject so please refer to the Ultimate Fish Guide for all there is to know on the matter. For the sake of this section
it is necessary to establish some basics.
- Fish are defined by their base sets and their cover sets. If all the candidates of N base sets can be covered by N cover sets, all non-base candidates can be eliminated from the covers.
- If however you require N+1 cover sets to cover all the candidates, you can only eliminate candidates that are contained within 2 cover sets.
- Furthermore, if you require N+X cover sets, you can only eliminate candidates that are contained within X+1 cover sets. The value X is known as the "Rank".
When putting Fish into Eureka notation, you list the base sets first, then
a slash (/), then the cover sets. This Kraken Fish is thusly expressed as
(1)r58/c35.
The Finned X-Wing can be expressed as an N+1 type Fish: (1)r58/c35b4. Box 4
is the extra cover set required to cover all candidates in rows 5 & 8,
and the candidates that are contained within 2 cover sets can be eliminated.
These are the candidates contained within the intersection of c3 and b4. If
the Fish can be resolved into an elimination like this it's not typical to
call it a Kraken Fish, it's just a Finned Fish. "Kraken Fish" implies some
AIC chaining through other digits.
If you find an N+1 type Fish with no candidates contained within
overlapping cover sets then all hope is not lost: you can call the extra
Fins that require the +1 cover set the "Kraken candidates" and define a new
strong inference "Kraken candidates = Fish". This is a whole load of
complicated terminology so another example is in order.
(8)c24/r69 = (8-6)r7c2 = r8c1 - (6=8)r3c1 => r6c1<>8
This AIC proves that the endpoints (8)c24/r69 and (8)r3c1 have a strong
inference so at least one must be true. Both cases would eliminate 8 from
r6c1 so we can safely eliminate it.
The Kraken Fish strong inference is a type of Grouped link: there has to be
an 8 in column 2 so the 8s form a strong inference set. If we divide them
into the two subsets {8r7c2} = {8r6c2, 8r9c2} we have a new strong
inference. The second subset stands for the premise that 8 is only contained
within r69c2, and if this is true then the Fish is true. Again the Fish's
weak inferences (not showcased here) are just its potential eliminations
because the fact the Fish eliminates them means they cannot co-exist - both
cannot be true.
Avoidable Pattern Guardians
An Avoidable Pattern is an arrangement of candidates that provably cannot
be part of the solution. There are two major types of Avoidable
Patterns:
Impossible patterns are candidate arrangements that are simply
impossible to solve, any attempt to fill in the cells according to the
candidates will result in you being unable to do so according to the rules
of Sudoku. This is quite a broad definition with a lot of potential for
interpretation but there are many well-defined impossible patterns which can
be easily recognised. Examples include Bivalue & Trivalue Oddagons and
negative-rank patterns
such as Broken Wing (a single-digit Oddagon).
Deadly patterns are candidate arrangements that can only have
multiple solutions. If they are included within a greater candidate field
then this candidate field either has 0 or multiple solutions. If you know
the puzzle you're solving has a unique solution, removing candidates can
never produce more valid solutions, so if you encounter a deadly pattern
you've made a mistake and ended up in an unsolvable state with 0 solutions.
Examples include
Unique Rectangles and the BUG state.
You absolutely do not want to see an Avoidable Pattern in your puzzle so
you do not want to eliminate the extra candidates that are preventing one
from appearing. The candidates preventing the impossible state are called
the Guardians.
If there is only one of these candidates you can place it as a solved cell,
but if there are more you can treat them as a strong inference set and use
them in AIC - you know that at least one of them must be true.
(2=6)r5c6 - (6=2)r2c28- => r2c1<>2, r2c7<>26
The blue cells would form a Bivalue Oddagon if they all contained {45} so
the extra candidates are the Guardians. They form a strong inference set
which I've grouped by their digits. The resulting strong inference combines
with the bivalue cell (26)r2c6 to form a Ring which is effectively a naked
Pair.
(8)r2c46 = r4c46 - (8=4)r5c5 - r5c4 = (4)r1c4 =>
r1c4<>8
The blue cells here would form a Unique Rectangle if they all contained
{23} so the extra candidates are the Guardians. They form a strong inference set
which I've grouped by their boxes. A short AIC proves a strong inference
between (4)r1c4 and (8)r2c46 leading to one elimination.
Fireworks
Fireworks are a wonderful and surprisingly recent idea, being advanced only
three years ago by shye. The basic gist is that "when a candidate in an intersecting row and
column is limited to the same box, it must be placed in the intersecting
cell".
Take this arrangement of candidates for example. If (1)r1c9 and (1)r9c1 are
both set to false then box 1 would have two separate instances of claiming
candidates, resulting in 1 being placed in r1c1.
It follows that these blue cells form a strong inference set: all of them
cannot be false at once. If they were, you would be forced to place two 1s
in box 1 which is impossible.
In my experience if the Fireworks are only present on a single digit they
have limited utility and most if not all AIC constructed with these links
can be expressed via Kraken Fish instead. Still, the simplicity & added
power when there are two or more overlapping sets of Fireworks (check the
original thread linked above, and
this thread) make it
worth learning.
Equivalence
"Equivalence" is a placeholder name for a particular logical relation
outside of strong & weak inferences. If two premises are always true at
the same time and always false at the same time, these premises are said to
be equivalent, and any resulting structures such as Fish or Locked Sets are
also equivalent.
If you have the strong inference A = B, but you also know B is equivalent
to C - when B is true C is true, when B is false C is false, and vice versa
- then you can swap it out for the new strong inference A = C and all chains
resulting from this are still valid. I tentatively propose that this should
be notated as A = B + C.
These equivalences can be proven under certain circumstances between the
three major logical structures in Sudoku: ALS, AHS and Fish. The three
possible pairs are ALS+AHS, ALS+Fish, and AHS+Fish.
AHS+ALS
In this puzzle row 5 has an AHS (12)r5c258, marked in blue. This gives us
strong inferences between the premises that each of these cells contains the
AHS digits (12).
(12)r5c2 = (12)r5c5
(12)r5c2 = (12)r5c8
(12)r5c5 = (12)r5c8
Note that when the premise (12)r5c2 is true, it clears all other candidates
from the cell r5c2 and the new contents of the cell combine with r2c2 to
form a Locked Pair, marked in purple. When (12)r5c2 is false this Locked
Pair is invalid as the two cells contain too many digits. So the premise
(12)r5c2 can be considered equivalent to the premise that the Locked Pair is
valid, as they always come together. We can represent this as (12)(r5c5 =
r5c82) + (12)r25c2, or the reverse, (12)r25c2 + (12)(r5c2 = r5c58).
(38)(r5c6 = r5c31) + (38)r25c1 - (3)r3c1 = (3)r3c56 =>
r12c6<>3
This puzzle has a similar setup. The premise (3)r5c6 has a strong inference
with (38)r5c1 thanks to the AHS, and this latter premise is equivalent to
the Locked Pair (38)r25c1, so the chain continues from its weak
inferences.
I'm afraid that aside from serving as an introduction to the equivalence
concept, these ALS+AHS combinations are limited in their practicality as (as
far as I know) every instance can also be considered a case of the cellwise
double AHS intersection. Replace the above (38+)r25c1 ALS with its dual AHS
(259)c1, and you get this AIC:
(38)(r5c6 = r5c31) - (259)(r5c1 = r673c1) - (3)r3c1 = (3)r3c56
So the major use-case would be to simplify a complicated chain by replacing
a (for example) 7-cell AHS with its 2-cell ALS counterpart. Disappointing
but I promise the ALS+Fish equivalence is a lot more exciting.
ALS+Fish
In this puzzle row 5 has an ALS (123)r5c28, marked in blue. This gives us
strong inferences between the premises that the ALS contains each of its
candidate digit sets.
(1)r5c28 = (2)r5c28
(1)r5c28 = (3)r5c28
(2)r5c28 = (3)r5c28
Note that when the premise (1)r5c28 is true, it clears all other 1s from the region it is contained
within (row 5), so when this premise is true row 5's possible positions
for 1s are reduced to the strong inference set (1)r5c28. This strong
inference set can be used as a base set for the X-Wing (1)r58/c28. So when
the premise (1)r5c28 is true the X-Wing is valid, but when (1)r5c28 is
false the X-Wing is invalid because the column cover sets no longer cover
every candidate within row 5. The premises (1)r5c28 and (1)r58/c28 are
thus equivalent and can be freely replaced in any AIC.
(9)r123c2 = r6c2 - (9=18)r6c19 + r68/c19 - (8=9)r3c1- =>
r6c25<>1, r6c56<>9, r7c1<>8, r4c9<>8
In this puzzle the premise that the ALS (189)r6c19 contains 8 is equivalent
to the premise that the X-Wing (8)r68/c19 is valid so they can be freely
swapped out. This gives us a Ring with plentiful eliminations.
In Xsudo language this AIC is composed of 5 truths: 9c2, 8r8, r3c1, r6c1,
r6c9. The candidates are covered by the 5 cover sets 1r6, 9r6, 8c1, 8c9,
9b1. 5 - 5 = 0 so the move is rank0.
In fact the entire puzzle is solvable using moves consisting of 5 or fewer
truths, putting it at the lower end of difficulty in this metric - despite
this, its SE rating is 9.0, and it requires Whips and Braids of length 7 to
solve. YZF's solver can't find a single rank0 move - no Rings, ALS-Rings,
Blossom Loops, MSLS, nothing. All this hints that the ALS+Fish equivalence
has a powerful nature inherent to it which makes its eliminations very
difficult to obtain with standard AIC & FC procedures.
(6=57)r2c39 + r27/c39b9 - (7=4)r9c9 - (4=6)r9c4 - r4c4 = (6)r4c1 =>
r12c1<>6, r5c3<>6
Another example except in this case the equivalent X-Wing is Finned so its
only potential eliminations (weak inferences) are (7)r8c9 and
(7)r9c9.
There is also the AHS+Fish equivalence but it's quite redundant as ALS are
easier to use. I won't go into detail but it works the same way by
effectively giving the AHS premises more weak inferences.
Almost-AIC
You may have noticed a pattern in the definitions for ALS, AHS and Almost
Fish strong inferences: each one has a candidate, or set of candidates,
which if removed cause a logical structure to become valid. This gives us a
strong inference with the removed candidates on one side and the resulting
structure on the other side. Can we do this with other logical structures,
such as ALC, MSLS, Sue-de-Coq, even other AIC?
Yes we can. However there isn't much information online on this so I'll
have to advance my own standards and notation. Keep in mind everything in
this section is my own conception of Almost-AIC, born of months of
experimentation and a couple of failed attempts at formalising branching
chains into AIC (my older articles have lots of very very ugly awful moves
because I wasn't as good at finding them yet). There are undoubtedly other
solvers out there with their own procedures, this is just the
conceptualisation that works best for me.
Let's step back and examine our understanding of AIC so far. AIC is formed
by constructing chains via inferences between premises. If these inferences
are valid then the AIC is automatically valid and proves that the endpoint
premises have a strong inference, and in Sudoku we can leverage this new
strong inference to eliminate mutual peers.
If however one of the strong inferences within the chain is invalid, the
AIC is no longer valid and cannot be used to eliminate the candidates. An
example is presented below.
Almost-W-Wing: (2=1)r7c2 - r4c2 = r4c5 - (1=2)r9c5
Most of the AIC checks out but the strong inference (1)r4c2 = (1)r4c5 is
invalid as there's an extra 1 in row 4 preventing these candidates from
being bilocal. We can't assert that both of these candidates can't be false,
because they clearly can, if 1 is in r4c8. As a result these eliminations
are invalid and potentially even incorrect.
Recall that all of the instances of a digit candidate within a single
region form a strong inference set. We can split this strong inference set
into two subsets and as long as the two subsets together contain every
element of the main set, there is a strong inference between these subsets.
Each of the subsets is equivalent to the premise "the location of digit N in
this region is within these cells". Previously we just grouped these by
their mutual row/column/box weak inferences and went on our merry way, but
we don't have to stop the analysis there. We can group these subsets by
their AIC-derived weak inferences.
If I group the strong inference set into the following two subsets:
{1r4c2, 1r4c5} = {1r4c8}
When the left premise is true the strong inference (1)r4c2 = (1)r4c5 is valid and so our AIC is valid. In a sense, the left
premise is equivalent to the premise that the AIC is valid. What we've shown
is that there is a strong inference between this "Almost-AIC" and the
candidates preventing it from being valid.
This has major implications. Any AIC that "almost works" can potentially
have its eliminations rescued by chaining off the extra candidates.
Furthermore, AIC themselves become a premise that we can freely use in
chains, even multiple within the same chain. The weak inferences of an AIC
are simply its eliminations: both cannot be true at once for obvious
reasons.
I like to call the candidates preventing the AIC from being valid the
"Kraken candidates". It's a term derived from Fish, referencing the mythical
Kraken with its many tentacles. I'd say it's accurate here as Kraken AIC
tend to branch out across the entire grid, although the overall structure of
the AIC is still linear.
When it comes to notation, I like to enclose the Almost-AIC in [square
brackets] with the Eureka notation of the Almost-AIC included within. Other
than that there's nothing too special, the rest looks like any other linear
AIC. In diagrams I tend to colour the Kraken candidates in grey and I don't
draw the strong inference between the AIC and its Kraken candidates because
it makes things messy.
Here's a slight modification to the example above allowing one of the
eliminations to be rescued.
(4)r7c6 = (4-3)r7c8 = (3-1)r4c8 = [(2=1)r7c2 - r4c2 = r4c5 - (1=2)r9c5] => r7c6<>2
This AIC proves that the endpoints have a strong inference, (4)r7c6
= [(2=1)r7c2 - r4c2 = r4c5 - (1=2)r9c5]. At least one is true so we may
eliminate all mutually eliminated candidates. The only candidate eliminated
by both the W-Wing and (4)r7c6 is (2)r7c6.
Here are some examples from real puzzles.
[(7=8)r3c6 - r13c5 = r7c5 - (8=7)r7c3] = (8)r5c5 - (8=14)r6c46 -
(4=2597)r1256c1 => r3c3<>7
This is a Kraken Grouped W-Wing, similar to above.
(5)r4c5 = [(8=3)r4c5 - r18/c15 = r1c9 - (3=8)r3c8] - (8)r4c8 = (8-5)r6c9 =
(5)r5c79 => r5c6<>5
The candidates of a cell can be used as a strong inference set in this
manner too. In this example there's a strong inference between (5)r4c5 and
(38)r5c4 and the latter is used in an Almost-AIC (actually another W-Wing
variant containing a Kraken X-Wing).
[(1=4)r8c5 - r8c1 = r3c1 - (4=1)43c2] = [(4=5)r4c2 - (5=8)r3c2 - r3c6 =
(8-6)r2c6 = (6)r4c6] - (4)r4c6 = r7c6 - (4=1)r8c5 => r8c2<>1
The strong inference set (1458)r3c2 is divided into two groups, (14) and
(58). Each of these groups has an associated Almost-AIC. (14) gives us a
W-Wing and (58)'s weak inferences can be chained off in order to reach
around to the W-Wing eliminations. I've coloured the sets in blue and purple
respectively to make the diagram easier to read.
(789)r5c6 = [(1=2)r9c6 - r7c5 = (2-49)r5c5 = (4-1)r9c5 = (1)r45c5] =>
r5c6<>1
In this example the potential Unique Rectangle (12)r59c56 has 6 guardians,
forming a strong inference set. This strong inference set can be divided
into two subsets:
{7r5c6, 8r5c6, 9r5c6} = {4r5c5, 9r5c5, 4r9c5}
The latter of which gives us the AIC (1=2)r9c6 - r7c5 = (2-49)r5c5 = (4-1)r9c5 = (1)r45c5 by grouping the
candidates according to their common cells.
(2)r9c2 = [(8)r3c2 = r6c2 - (8=7)r6c3 - (7=491)r9c237 - (1=2)r3c7] =>
r3c2<>2
In this example the Kraken candidate is an AALS digit. Recall that an ALS
is formed by N cells in a region that contain N+1 unique candidate digits,
and there is a strong inference between every pair of digits.
An AALS is formed by N cells in a region that contain N+2 unique candidate
digits, and every triplet of digits forms a strong inference set.
This strong inference set can be grouped and used in Almost-AIC. This can be
generalised to AAALS, AAAALS, etc. for strong inference sets of quadruplets
and quintuplets respectively.
The same property extends to AAHS - every triplet of cells forms a strong
inference set.
[(2=5)r4c2 - r2c2 = r2c3 - (5=2)r9c3] = (5)r2c7 - (5)r8c7 = [(2=6)r8c7 -
(6=52)r89c3] => r8c2<>2
Here's a delightful move which I like to call a "tie". We have a W-Wing
which is almost valid save for (5)r2c7, and an XYZ-Wing which is almost
valid save for (5)r8c7. Both of these Kraken candidates are in the same
column so both cannot be true at once, therefore at least one of the AICs
must be valid. This Almost-W-Wing and Almost-XYZ-Wing are thus tied together
and their mutual eliminations may be removed. It's really the simplest AIC,
A = B - C = D => A = D, except A and D are both Almost-AIC
premises.
Blossom Loop
Over on the Chinese internet the high-level Sudoku solvers have also been
developing their own theories of branching chains. It's hard for me to know
the full story as there's a significant language barrier but they refer to
Almost-AIC as "Burring Chain", where the chain is the AIC, and the Kraken
candidate is referred to as the "Burr", sometimes "Thorn". You can find a
great wealth of information about the topic in this Baidu group and particularly in this bilibili collection.
One of these Burring Chain techniques is the Blossom Loop, which has been brought to the English-speaking Sudoku sphere by
YZF.
Recall that when chaining, an Almost-AIC's weak inferences are simply its
eliminations. Most AIC will only eliminate one or two candidates so it can
be difficult to get everything to line up and lead to mutual eliminations.
The exception to this is Rings - Rings can have a multitude of eliminations,
even dozens. Chaining off Almost-Rings is a good strategy that can reward
you with easier eliminations.
(7)r6c7 = (7-1)r1c7 = r1c4 - r3c5 = (1-7)r4c5 = (7)r6c5- =>
r1c7<>238, r3c4<>1, r4c5<>2, r6c2<>7
Unfortunately this potential Ring is invalid because column 7 contains an
extra 7. We can declare (7)r2c7 the Kraken candidate and attempt to build an
AIC that rescues the potential Ring eliminations.
While doing this you may run into a situation where the Kraken end node is
one of the potential eliminations of the Almost-Ring, meaning they share a
weak inference. This makes the entire AIC a Ring, including the internal
almost-Ring itself.
[(7)r6c7 = (7-1)r1c7 = r1c4 - r3c5 = (1-7)r4c5 = (7)r6c5-] = (7)r2c7 - r2c12
= (7-9)r1c1 = r1c2 - (9=7)r6c2- => r1c7<>238, r3c4<>1, r4c5<>2, r1c1<>38,
r49c2<>9
This rare technique is called the Blossom Loop. Any strong inference set
can be used for this process - YZF's solver has region, cell and AALS
variants implemented.
[(3=14)r7c78 - r5c7 = (4-3)r4c9 = (3)r9c9-] = (7)r7c8 - r7c23 = (7-5)r8c2 =
r8c1 - (5=238)r126c1 - r6c9 = (8)r4c9- => r7c5,r8c8<>1,
r4c9<>29, r7c4<>7, r8c2<>8, r4c1<>2
Here we have an AALS Blossom Loop built off the strong inference set
between the three AALS digits 3, 4 and 7. As this is a Ring all weak
inferences become strong, all strong inferences become weak, all that is
solid melts into air, all that is holy is profaned, and the remaining ALS
digits (in this case it's just 1) are locked into the ALS, so we can remove
all 1s that see the ALS, just like in standard Rings.
---
You've reached the end of the article. Thanks for reading. Applying every
technique as described up to this point will solve almost every puzzle up to
~9.3 SE. This point represents the extent of my current Sudoku solving
capacity, and unless there's an MSLS, Exocet, etc. to lower the difficulty
it's unlikely I'll be able to crack the harder puzzles without extensive
trial and error.
The next step up would be to implement Almost-Almost-AICs but these take
absolutely forever to search for manually and I imagine they would even slow
down a modern computer. I wonder how many "Almost"s you need to solve any
puzzle without fail.
I have some ideas for generalising the "Almost" process into grouped strong
inference sets based on common AIC-derived weak inferences and iteratively
applying this to get the "Almost-Almost", "Almost-Almost-Almost"-AICs etc.,
once I've coded it up I'll revisit the relevant section of this
article.
Comments
Post a Comment