A General Sudoku Logic Odd Loops, Broken Wings, and Dark Logic |
Points.
Odd length loops are present in many solving methods such as chains and
dis-continuous nice loops. The broken wing method eliminates candidates by
using the fact that odd length loops of strong links cannot occur in a valid
puzzle. This method can be generalized using sets and represents a
fundemental principle in Sudoku set logic.
Odd Length Loops Many Sudoku solving methods are based on odd length
loops. The simple chain example below left has 5 links and a target candidate
(red) at the intersection of two linksets, r5c5. With a different set of
strong links (right), the same nodes form a discontinuous nice loop that
assigns the target candidate rather than eliminate it. Illegal Logic and Rank Illegal logic is any group of sets (or candidates)
that has no solution, i.e., there is no way to arrange the candidates that is
allowed by the rules. The illegal 'fish' below has 3 sets connected by two
linksets where it's easy to verify that 3 candidates
cannot be placed in 3 sets without placing 2 in a single linkset. The illegal
structure, denoted by black sets, has a rank of 2 linksets - 3 sets, which
equals minus 1. Odd length loops of bi-value strong links are also
illegal. The length 5 loop below can contain at most two nodes without double
occupancy, which leaves one set unoccupied. Loops of any odd length have a
rank of minus 1. Broken Wings Broken Wing is a unique method that has been widely
applied. It assumes that a valid puzzle cannot contain loops with an odd
number of bi-value strong links (conjugate
pairs). To be legal, at least one link
must contain at least one extra candidate, called a guardian. If there is one
guardian, it can be assigned. If there are multiple guardians, eliminations
can be logically deduced. Guardians can be connected to a variety of logic. The lone guardian (G) in r3c8 below prevents the logic from being
illegal and is thus assigned becoming a single. It then eliminates the
orange candidates in column 8. Additional assignments and eliminations are
explained later. Broken Wings and Dark Logic Broken wings occur naturally in set logic along with
other odd length, strong-set logic. The following is a simple set logic view
of broken wing principles that applies to a wide range of logic. In terms of
set logic, the broken wing principle is both unique and elegant. The same
principles can be applied to deadly patterns and URs. To keep track of what's
what, the term dark refers to anything illegal caused by odd
length loops. A dark loop contains the sets
and nodes belonging to illegal logic but not guardians or other logic that
may be in the same sets. Defined this way, dark loops have the following
properties: A
dark loop of any size has a rank of minus 1 and is outside of the set
and linkset groups that determine eliminations in the rest of the logic
(according to set theory) A
dark loop can be removed and the remaining candidates, such as guardians,
placed in a virtual set that behaves like ordinary sets. This virtual set can
span rows, columns, and boxes. In short, a broken wing is made of a dark loop plus
guardian candidates, all contained in the same sets. The dark logic disappears
(sets and nodes) leaving behind the guardians that act as if they were in one
virtual set. (Why?, becasue of the dark force,
of course.) Below is a two-guardian broken wing. Although
neither guardian can be assigned, one must be true so the linkset in column 8
is always occupied, or rank 0, which eliminates the
red candidates. From the set logic view, the dark loop's guarantee
of one true guardian effectively divides the problem in two. On the right,
the guardians now work as if they are in a single virtual set, which forms
something like locked candidates, except it spans 2 boxes. On
the left, the guarantee of one true guardian means that rows r3 and r5 are
linksets for the dark loop, which is solved in the normal way as a
discontinuous nice loop that assigns 7r2c6, thus eliminating the two red
candidates. Implications There must be a large number of odd length loops in
every Sudoku grid, each of which can be broken into a dark loop and a virtual
set. A set logic solver could first catalog these virtual sets and add them
to the set base when searching for logic. Something similar could probably be
done with other solvers. The same principles can be applied to deadly
patterns and unique rectangles, which also require at least one additional
candidate to be legal. The deadly patterns can be removed and the remaining
candidates from their sets placed in a virtual set. The only difference is
that broken wings are naturally illegal while deadly rectangles are illegal
by the convention that valid puzzles have one solution. Examples Below is a chain is made of 4 linksets and 3 sets including
the virtual set in the middle of the chain. In set terms, the dark loop is
replaced by virtual set V making the chain: c55-(r55)-n52-(V)-n38-(c85)-r75
=> r7c5 <> 5 where sets are in ( ) and linksets are not. Written as a
chain: 5r7c5-5r5c5=5r5c2-7r5c2=V=7r3c8-5r3c8=5r7c8-5r7c5 => r7c5 <> 5 Set r37 is then a linkset and the dark loop is
solved as another chain: 7r3c2-7r3c4=7r2c6-7r6c6=7r6c2-7r3c2 => r3c2 <> 7 This X-wing has a set in column 8, a virtual set
from 7r2c4 to 7r6c6, and linksets in rows 2 and 6, which eliminate candidates
7r2c3 and 7r6c9. The 3D Kraken fish, shown in 3D, has 5 sets,
including the dark loop, 6 linksets, and a rank of 1. The virtual set has 3
candidates. The loop sits vertical with the virtual set on the bottom and the
middle red row set on top. Complex Examples The dark logic principle should work with any logic
as long as the dark logic nodes do not link to the the rest of the logic,
even then the principle still applies This example has 12 sets, 10 linksets,
and a 5 set dark loop that is replaced by virtual set V. The replaceable sets
are in red and the set logic is given
by: S-12 = [r84 r66 r96 c26 c66 c(59)6 c(24)7 n26 b46 b82], L-10 =
[r(24)6 r17 c6(27) n16 n72 n8(45) n94] Substitute V1
=> S8=[V r84 c(59)6 c(24)7 n26 b82], L10=[r(24)6 r17 c6(27)
n16 n72 n8(45) n94] =>
r1c6<>7 The logic now has 8 sets, 10 linksets. It is
therefore 2 so thus 3 overlap linksets are needed to
eliminate a candidate. Linksets r17, c67, and n16 overlap at cell r1c6 to
eliminate candidate 7r1c6. Three dimensional view of the above logic example. . Another extreme example below comes from Easter
Monster. It has 3 linksets and 18 sets of which 17 are linked into one great
piece of dark logic. There are 3 guardians but two are in the same linkset.
The logic is thus 2 sets + 3 linksets => rank 1, or a simple chain. The
dark logic acts like a box or a hinge because it place puts guardians in the
same linkset. The two linksets at the ends of the chain overlap to eliminate
the orange candidate. |