Techniques¶
The default pipeline applies 28 technique instances from 20 families, ordered from simplest to most advanced; after every successful deduction it restarts from the top, exactly how a human solver escalates only when the easy moves dry up. Each module below documents the logic of its family.
The shared framework classes (Technique,
Step, Placement,
Elimination) are documented in the API reference.
Naked candidates¶
Naked candidate techniques: Single, Pair, Triple, and Quad.
A naked subset is a group of n unsolved cells inside one house whose
candidates, taken together, span exactly n digits. Those digits must go
into those cells, so they can be eliminated from every other cell of the
house. With n = 1 the cell simply receives its only candidate.
- class dedoku.techniques.naked.NakedSingle[source]¶
Place the value of any cell left with a single candidate.
- class dedoku.techniques.naked.NakedPair[source]¶
Two cells of a house sharing the same two candidates.
Intersection removal¶
Intersection removal techniques: Pointing and Claiming.
Both techniques exploit the three-cell intersection between a subgrid and a line (row or column):
Pointing — if, inside a subgrid, every home of a digit sits on the same line, the digit must occupy that intersection, so it can be removed from the rest of the line.
Claiming (box/line reduction) — if, inside a line, every home of a digit falls within the same subgrid, the digit is claimed by that box, so it can be removed from the box cells outside the line.
- class dedoku.techniques.intersections.PointingCandidates[source]¶
Remove a digit from a line when a subgrid confines it to that line.
Fish (X-Wing, Swordfish, finned variants)¶
Fish techniques: X-Wing, Swordfish, and their finned variants.
A basic fish of size n for a digit is a set of n base lines
(all rows, or all columns) in which the digit’s candidate homes fall into
the same n cover lines of the perpendicular orientation. The digit must
then occupy the base/cover intersections, so it can be eliminated from the
rest of each cover line.
A finned fish tolerates a few extra homes (the fins) as long as they share one subgrid: either a fin is true, or the fins are all false and the plain fish holds. Cells inside both a cover line and the fin subgrid are false in either case.
Chute remote pairs¶
Chute Remote Pairs technique.
A chute is a band (three stacked rows covering three subgrids) or a
stack (three adjacent columns covering three subgrids). Take two bivalue
cells with the same candidate pair {a, b} inside one chute, lying in
different subgrids and different lines, so they share no house. Exactly
three chute cells see neither of them: the intersection of the remaining
line and the remaining subgrid.
If digit a can appear in none of those three cells (neither as a value
nor as a candidate), the two pair cells cannot both hold a — otherwise
the remaining subgrid would have no home for a at all. Hence at least
one pair cell holds b, and b can be eliminated from every cell that
sees both pair cells.
Simple colouring¶
Simple Colouring (single-digit chains) technique.
For one digit, a conjugate link connects the two cells of a house that are its only remaining homes there: exactly one of them must hold the digit. Following such links builds chains whose cells can be split into two alternating colours — one colour is entirely true, the other entirely false.
Two classic deductions follow:
Colour wrap — if two cells of the same colour see each other, that colour is false, and the digit is removed from every cell of it.
Colour trap — if an uncoloured cell sees both colours, one of the two colours must be true, so the cell can never hold the digit.
- class dedoku.techniques.colouring.SimpleColouring[source]¶
Eliminate a digit through two-colour conjugate chains.
- apply(grid)[source]¶
Find the first productive colour wrap or colour trap.
- Parameters:
grid (Grid) – The board to inspect and mutate.
- Returns:
The eliminations performed, or
Noneif no chain yields a deduction.- Return type:
Step | None
- Raises:
ContradictionError – If a chain contains an odd conjugate cycle, which proves the board inconsistent.
W-Wing¶
W-Wing technique.
Take two bivalue cells with the same candidate pair {a, b} that share
no house, plus a house in which digit b has exactly two homes (a strong
link), one home seeing the first pair cell and the other seeing the second.
If neither pair cell held a, both would hold b, and both ends of
the strong link would be blocked — leaving that house with no home for
b at all. Hence at least one pair cell holds a, and a can be
eliminated from every cell that sees both pair cells.
Wings (Y-Wing, XYZ-Wing)¶
Wing techniques built on a pivot cell: Y-Wing and XYZ-Wing.
A Y-Wing consists of a bivalue pivot {x, y} seeing two bivalue
pincers {x, z} and {y, z}. Whatever the pivot holds, one of the
pincers is forced to z, so z can be eliminated from every cell
that sees both pincers.
The XYZ-Wing extends the pattern with a trivalue pivot {x, y, z}: the
pivot itself may also hold z, so the elimination only applies to cells
that see all three pattern cells.
- class dedoku.techniques.wings.YWing[source]¶
Eliminate the shared pincer digit of an XY-Wing pattern.
Uniqueness rectangles¶
Uniqueness-based rectangle techniques.
These techniques assume the puzzle has exactly one solution — the standard convention for published Sudokus. A deadly pattern is four unsolved cells on the corners of a rectangle spanning exactly two subgrids, all restricted to the same two digits: any solution containing it could swap the two digits and yield a second solution. A valid puzzle can therefore never be forced into a deadly pattern, and moves that would create one can be ruled out.
- class dedoku.techniques.rectangles.UniqueRectangle[source]¶
Type 1 Unique Rectangle: strip the pair digits off the roof cell.
When three corners of a two-box rectangle are bivalue cells with the same pair
{a, b}, the fourth corner (the roof) may hold neitheranorb: placing either would force the rectangle into the deadly pattern and give the puzzle two solutions.
- class dedoku.techniques.rectangles.UniqueRectangleType2[source]¶
Type 2 Unique Rectangle: the shared extra digit must sit on the roof.
Two corners of a two-box rectangle (the floor) are bivalue cells with the same pair
{a, b}; the other two corners (the roof) hold exactly{a, b, c}with the same extra digitc. If neither roof cell werec, all four corners would collapse to the deadly pair pattern, sococcupies one of the roof cells and can be eliminated from every other cell that sees them both.
- class dedoku.techniques.rectangles.AvoidableRectangle[source]¶
Type 1 Avoidable Rectangle: avoid recreating a swappable rectangle.
Take a two-box rectangle with three corners solved during solving (none of them givens), where the two corners sharing a line with the remaining unsolved corner hold the same digit
band the diagonal corner holdsa. If the unsolved corner tooka, the four valuesa, b / b, acould be swapped without touching any given, so the puzzle would have a second solution:acan be eliminated.
Bivalue universal grave¶
Bivalue Universal Grave (BUG) technique, in its BUG+1 form.
A bivalue universal grave is a board state where every unsolved cell has exactly two candidates and every candidate appears exactly twice in each house. Such a state can never belong to a puzzle with a unique solution: the remaining digits could be assigned in two complementary ways.
The practical BUG+1 deduction: when every unsolved cell is bivalue except a single cell with three candidates, that cell must take the one candidate appearing three times in its row, column, and subgrid — placing any other value would leave the board as a deadly BUG. Like the other uniqueness arguments, this assumes the puzzle has exactly one solution.
Single-digit and bivalue chains¶
Chain techniques built on alternating inference.
An inference chain alternates strong links (“if this candidate is false, that one is true”) and weak links (“if this candidate is true, that one is false”). A chain that starts and ends with a strong link proves that at least one of its two endpoints is true, so anything weakly linked to both endpoints can be eliminated.
This module hosts the single-digit variant (XChain, the core of
X-Cycles) and the bivalue-cell variant (XYChain). Chains are
found breadth-first, so the shortest productive chain is reported.
- class dedoku.techniques.chains.XChain[source]¶
Single-digit alternating chain (the basic form of X-Cycles).
Strong links are conjugate pairs (a house with exactly two homes for the digit); weak links connect any two homes sharing a house. A chain with an odd number of links, starting and ending strongly, pins the digit to one of its endpoints: every outside home seeing both endpoints is eliminated.
- class dedoku.techniques.chains.XYChain[source]¶
Chain of bivalue cells whose endpoints pin a shared digit.
Consecutive cells see each other and hand over one candidate: a cell entered on digit
pexits on its other candidate. A chain that starts by leaving digitzbehind and ends by producingzproves that one of its endpoints holdsz, sozis eliminated from every outside cell seeing both endpoints. Within a single house the two-cell case degenerates to a naked pair, so only chains of three or more cells are reported.
3D Medusa¶
3D Medusa: multi-digit two-colouring of strong links.
Simple colouring works on one digit at a time; 3D Medusa extends the same idea across digits by also following the strong link inside every bivalue cell (its two candidates cannot both be false). Colouring the resulting network splits each component into two colours, exactly one of which is entirely true.
Deductions implemented:
colour wrap (cell) — two same-coloured candidates inside one cell falsify that whole colour;
colour wrap (unit) — two same-coloured candidates of one digit sharing a house falsify that whole colour;
bicoloured cell — a cell holding both colours must use one of them, so its uncoloured candidates are eliminated;
colour trap — an uncoloured candidate weakly linked to both colours can never be placed.
- class dedoku.techniques.medusa.Medusa3D[source]¶
Eliminate through multi-digit strong-link colouring.
- apply(grid)[source]¶
Colour each strong-link component and apply the Medusa rules.
- Parameters:
grid (Grid) – The board to inspect and mutate.
- Returns:
The eliminations performed, or
Noneif no component yields a deduction.- Return type:
Step | None
- Raises:
ContradictionError – If a component contains an odd cycle of strong links, which proves the board inconsistent.
Almost locked sets¶
Almost Locked Set techniques: the ALS-XZ rule.
An almost locked set (ALS) is a group of n unsolved cells inside one
house whose candidates span exactly n + 1 digits — one candidate away
from a naked subset. A single bivalue cell is the smallest ALS.
ALS-XZ rule. Take two disjoint ALSs A and B sharing digits x
and z, where x is a restricted common: every x-cell of A
sees every x-cell of B, so x can be placed in at most one of the
two sets. If an outside cell holding z saw every z-cell of both
sets, z would vanish from A and B, locking both and forcing x
into each of them — impossible. Such cells therefore lose z.
This single rule subsumes many named patterns (WXYZ-Wing, Sue-de-Coq and parts of Death Blossom arise as special cases of small ALS pairs).
Alternating inference chains¶
Alternating Inference Chains (AIC) over candidate nodes.
Where X-Chains work on one digit and XY-Chains on bivalue cells, an AIC
walks the full candidate graph: nodes are (cell, digit) candidates.
A strong link (“if false, then true”) joins the two candidates of a bivalue cell, or the two homes of a conjugate pair.
A weak link (“if true, then false”) joins two candidates of the same cell, or two same-digit candidates sharing a house.
A chain with an odd number of links, starting and ending strongly, proves that at least one endpoint is true: every candidate weakly linked to both endpoints is eliminated. Chains are searched breadth-first, shortest first. XY-Chains, X-Chains, and W-Wings are all special cases; the AIC is kept last in the pipeline as the most general (and most expensive) rule.