Mirrored from Sudopedia, the Free Sudoku Reference Guide

Uniqueness Clue Cover

A pattern of clues in a designated area of the grid is said to be a Uniqueness Clue Cover (UCC) when at least one of the eliminations that it makes, independent of the rest of the puzzle, is possible only by assuming that the puzzle has a unique solution.

The UCC eliminations are those inferences that required the uniqueness assumption.

UCCs may be invoked by lookup into a catalogue: if all of the clues and any of the placements (treating as clues) in some area (e.g. band) of the puzzle match a pattern in the catalogue, then the corresponding eliminations can be made. UCCs are applicable only quite rarely, usually on puzzles specially designed for them, and usually near the start of the puzzle-solving path.

UCCs are generally not amenable to discovery by manual analysis, requiring instead a lookup into a computer-generated catalogue. This, and the underlying uniqueness assumption, may not be to every solvers' tastes; hence the informal verbal abbreviation, "Yuck".

Notation and examples

We will use the following notation:

*x  = clue or placement x (must include all clues; can include any or no placements)
-Y  = inferred eliminations Y (that required the uniqueness assumption)
 @  = all values that don't have a star (*) against them

Example 1

Suppose that, within a band of the puzzle, the clues (possibly including some placements) form the following pattern:

+-------------+-------------+-------------+
|  *1   .   . |  *4   .   . |  *5   .   . |
|  *2   .   . |  *1   .   . |  *4   .   . |
|  *3   .   . |  *2   .   . |  *1   .   . |
+-------------+-------------+-------------+

Then the following UCC eliminations apply:

+-------------+-------------+-------------+
|   .   .   . |   .   .   . |   .  -3  -3 |
|   .   .   . |   . -35 -35 |   .   .   . |
|   .  -5  -5 |   .   .   . |   .   .   . |
+-------------+-------------+-------------+

This may be summarised in a single diagram:

+-------------+-------------+-------------+
|  *1   .   . |  *4   .   . |  *5  -3  -3 |
|  *2   .   . |  *1 -35 -35 |  *4   .   . |
|  *3  -5  -5 |  *2   .   . |  *1   .   . |
+-------------+-------------+-------------+

Example 2

More dramatically, if a band contains just two clues in the arrangement shown (starred) below, then all of the unclued values are eliminated from two other cells. Note that although it is obvious that -@ in r2c3 implies r2c3=1, this placement is not shown because the elimination of 2 from r2c3 does not require any uniqueness assumption: we are applying the definition strictly.

+-------------+-------------+-------------+
|   .   .   . |   .   .   . |   .   .  *1 |
|   .   .  -@ |   .   .   . |   .   .  -@ |
|   .   .  *2 |   .   .   . |   .   .   . |
+-------------+-------------+-------------+

These eliminations are available because only a few special types of band (in this case) can be covered by just two clues in any proper, single-solution, puzzle. Knowing the form that these special band types take, by computer searching, allows us to make the eliminations shown.

A formal treatment

Formal definition

A pattern, P, is a designated set of cells, some of which contain a digit and the rest of which are blank. We will always consider the pattern P in isolation, independent of any puzzle in which P may be found.

The completions of a pattern, P, are those ways of filling in the blanks so that the whole designated set of cells obeys the rules of sudoku.

P covers a completion if any of the following equivalent conditions holds:

no other completion of P has the same footprint;
every unavoidable set in the completion has at least one (cell,value) pair in common with P;
blanking those cells in the completion that are non-blank in P leaves no unavoidable sets.

Then we can say that a candidate, x, is a UCC elimination for clue pattern P in designated area A if and only if:

 P is a cover for at least one of its completions; and
 P+x has >0 completions, but P   is not a cover for any of them.

Generalisation of Reverse BUG-lite

The corresponding requirement for a Reverse BUG-lite elimination is:

 P is a cover for at least one of its completions; and
 P+x has >0 completions, but P+x is not a cover for any of them.

Thus UCC generalises Reverse BUG-lite.

Formal test

The following is a formal test to say whether or not a candidate x@(r,c) is a UCC elimination for pattern P in some designated area of the grid:

solutions = 0

for each completion of P+x:
    solutions = solutions + 1
    if P covers that completion:
        return "No elimination: P covers at least one completion of P+x"

if solutions > 0:
    return "Yes! - x@(r,c) is eliminated by UCC"
else:
    return "No - x@(r,c) is eliminated by a non-uniqueness technique"

The "Yes!" conclusion is valid only if P is a cover for at least one of its completions ("P is a cover"). In a proper puzzle, where P consists of all clues and maybe some placements in a designated area, P is necessarily a cover. However when building the UCC catalogue shown in this article it takes additional work to check that a potential catalogue entry, P, is a cover:

for completion of P:
    if P covers that completion:
        return "Yes, P is a cover"

return "No, P is not a cover"

Dead-end completions

Recall the definition of completion given earlier in this article:

The completions of a pattern, P, are those ways of filling in the blanks so that the whole designated set of cells obeys the rules of sudoku.

For the purposes of the definition, the rules of sudoku are that there shall be no repeated digits in any row, column or box within the cells in question.

Therefore certain dead-end patterns, such as this ...

 +-------+----
 | 1 2 . | 3 4
 | 3 4 . | 1 2

... that could never appear in any solution grid are allowed by the definition.

The consequence for the UCC technique is that sometimes not all possible eliminations will be made.

Catalogue

The following catalogue of UCC eliminations is split into sections according to the size (number of clues/placements) of the pattern and the type of the area in which the pattern is defined. Everything is unique up to isomorphism/scrambling.

Two rows

To do: exhaustive search ...

???

One band, two clues

There is only one UCC:

+-------------+-------------+-------------+
|   .   .   . |   .   .   . |   .   .  *1 |
|   .   .  -@ |   .   .   . |   .   .  -@ |
|   .   .  *2 |   .   .   . |   .   .   . |
+-------------+-------------+-------------+

Here are two puzzles solved using those UCC eliminations:

// credit: Mauricio
*-----------*
|...|...|...|
|...|...|..2|
|...|..1|...|
|---+---+---|
|..1|.3.|.4.|
|..5|6.7|3..|
|.3.|.2.|..8|
|---+---+---|
|..2|.6.|5..|
|65.|..8|9.4|
|9..|4..|..7|
*-----------*

// credit: JPF
*-----------*
|...|...|...|
|...|...|..1|
|...|..2|...|
|---+---+---|
|..2|3..|4..|
|..5|6..|.17|
|.8.|..9|..3|
|---+---+---|
|.4.|..7|..8|
|.53|1..|7..|
|72.|95.|.6.|
*-----------*

One band, three clues

There are five UCCs:

+----------+----------+----------+
| -2 -2 -2 |  .  . -2 |  .  .  . |
|  .  .  . | -2 -2 -2 |  .  . *1 |
|  .  .  . |  .  . *1 |  .  . *2 |
+----------+----------+----------+

+----------+----------+----------+
| -2 -2 -2 |  .  .  . |  .  .  . |
|  .  .  . | -2 -2 -2 |  .  . *1 |
|  .  .  . |  .  . *1 |  . *2  . |
+----------+----------+----------+

+----------+----------+----------+
| -1 -1 -1 | -1  .  . |  .  .  . |
|  .  .  . |  .  .  . |  .  . *1 |
|  .  .  . | -1 *2 *3 |  .  .  . |
+----------+----------+----------+

+----------+----------+----------+
|  .  .  . |  .  .  . |  .  . -@ |
|  .  .  . |  .  .  . |  .  . *1 |
|  .  . *1 |  .  . *2 |  .  .  . |
+----------+----------+----------+

+----------+----------+----------+
|  .  .  . |  .  . -@ |  .  . *1 |
|  .  .  . |  .  .  . |  . *2  . |
|  .  .  . |  .  . *1 |  .  .  . |
+----------+----------+----------+

Other

???

Extensions

To do, maybe: note feasibility of extending to patterns where the clues and singles/placements are distinguished (tedious), to inferences that generate weak/strong/conjugate links (also tedious), and to areas other than bands (e.g. 2x2 boxes - difficult but worth investigating).