Prev Up Next
# Subsets

**Subset Principle**
Let *S* be a subset of the set of cells of a partially filled
Sudoku diagram, and let for each digit *d* the number of occurrences
of *d* in *S* be at most *n*_{d}.
If the sum of the numbers *n*_{d} equals the
size of the set *S*, then the situation is tight: each digit *d*
must occur precisely *n*_{d} times in S.
In this case we can eliminate a digit *d* from the candidates
of any cell *C* such that the presence of *d* in *C*
would force the number of *d*'s in *S* to be less than
*n*_{d}.
Matching Principle B was the special case where the cells of *S* are all
in one row or column or box. There are many other useful special cases.

## Line-box intersection

The argument below was given by Sue de Coq.
Consider the intersection of a line (row or column) and a box.
Suppose there are *n* unsolved cells there, and these have
together *m* candidates, and you can find *m-n* other
cells in the same line or the same box that have no candidates
other than these *m*, and such that for these *m-n* other
cells there is no candidate common to a cell in the same box
not on the line and a cell on the same line not in the box.
Then matching applies: the *m* values go into the *m* cells,
and the values can be removed elsewhere.

An example given by `ronk`:

The three yellow squares have together the five possibilities 2,3,4,5,9.
The two green squares also have their possibilities inside the set 23459,
and since no digit can be seen twice in the yellow and green squares
together, these five squares contains these five digits.
But that means that 345 can be eliminated elsewhere in the same box,
and 259 elsewhere in the same column.

Clearly, this is a special case of the general subset principle.

## Extended subset principle

**Extended Subset Principle**
Let *S* be a subset of the set of cells of a partially filled
Sudoku diagram, and let for each digit *d* the number of occurrences
of *d* in *S* be at most *n*_{d}.
If Σ*n*_{d} = |S| + δ then we can eliminate
a digit *d* from the candidates of any cell *C* such that
the presence of *d* in *C* would force the number of *d*'s
in *S* to be less than *n*_{d} - δ.

## Almost Locked Sets

If *A* and *B* are two disjoint sets of cells such that
each of them has one more candidate than its size, and there is
a digit *e* that is candidate for both but can occur in at most one,
then one may eliminate a digit *d* different from *e* that
is a common candidate for both *A* and *B* from a cell *C*
outside *A* and *B* whenever *C* is adjacent to all possible
cells in *A* or *B* that have candidate *d*.
(This is the special case δ = 1 of the extended subset principle:
*S* is the union of *A* and *B*, and the condition on *e*
makes sure that Σ*n*_{d} is at most
|*A*| + |*B*| + 1.)

**Terminology** A 'locked subset' is one with as
many candidates as its size. An 'almost locked subset' is one with
one more candidate than its size.

The above observation is due to `bennys`. He gave the following example.

Starting from the given puzzle one arrives after some work
at the situation with candidates as shown. Let the sets A and B be the yellow
and green sets. A has size 4 and candidates 1,3,5,7,8. B has size 3 and
candidates 1,2,5,7. So both are almost locked. The digit 1 is candidate
for both but can occur only in one. So, the candidate 5 can be removed
from both blue fields.

Thinking in terms of the extended subset principle, it is not
necessary to separate the yellow and green sets. Their union
is a single set of size 7, and the digits 1,2,3,5,7,8 can occur
at most 1,1,1,2,2,1 times, for a total of 8. So δ=1, and every
placement that eliminates 2 candidates is wrong. But a 5 at one of
the two blue fields would eliminate both 5s and hence cannot occur.

Prev Up Next