Solving Techniques

From Sudopedia
Revision as of 05:07, 31 May 2020 by Rooted (talk | contribs) (Created page with "These are the methods used to solve a Sudoku. There are many different solving techniques discovered in the last few years, mainly because there is a large community of puzzle...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

These are the methods used to solve a Sudoku. There are many different solving techniques discovered in the last few years, mainly because there is a large community of puzzlers who share their knowledge on the various Sudoku Forums.

Because there are so many, a rough subclassification has been made:

Singles

Full House
A house with a single empty cell.
Last Digit
The last instance of a digit.
Hidden Single | Pinned Digit
A single candidate remaining for a digit in a house.
Naked Single | Forced Digit | Sole Candidate
A single candidate remaining in a cell.

Intersections

Locked Candidates | Intersection Removal | Line-Box Interaction | Pointing (Pair, Triple) | Claiming
Candidates are locked in the intersection of a line and a box.
Locked Pair
A Naked Pair located in a single intersection.
Locked Triple
A Naked Triple located in a single intersection.
Almost Locked Candidates
A box-line intersection where the line or the box contains an Almost Locked Set, and the remaining cells in the line or box outside the intersection does not contain digits from the Almost Locked Set.

Subsets

Naked Subset
N cells with candidates for N digits.
Naked Pair
2 cells with candidates for 2 digits.
Naked Triple
3 cells with candidates for 3 digits.
Naked Quad
4 cells with candidates for 4 digits.
Hidden Subset
N digits with candidates in N cells.
Hidden Pair
2 digits with candidates in 2 cells.
Hidden Triple
3 digits with candidates in 3 cells.
Hidden Quad
4 digits with candidates in 4 cells.

Fish

Basic Fish
Rows and columns only.
X-Wing
2 rows vs. 2 columns
Swordfish
3 rows vs. 3 columns
Jellyfish
4 rows vs. 4 columns
Squirmbag
5 rows vs. 5 columns
Fish and Subsets
general relationship between Fish and Subsets.
Finned Fish
Fish patterns with additional candidates in a single box.
Sashimi Fish
Incomplete basic fish patterns with a fin.
Franken Fish
Fish patterns that include box constraints.
Mutant Fish
Fish patterns with mixed sets of constraints.
Kraken Fish
A fish pattern with indirect connections to a candidate which can be eliminated.

Single Digit Patterns

Skyscraper
Two parallel strong links, weakly connected at the base.
2-String Kite
Two crossing strong links, weakly connected in a box.
Empty Rectangle
A single-digit technique that makes use of a box whose candidates for that digit are contained within the union of a boxrow and a boxcol.

Coloring

Simple Colors
Uses only 2 colors to form a single color cluster.
Multi-Colors | Supercoloring
Uses multiple colors (4, 6 or a higher multiple of 2) to form multiple color clusters.
Weak Colors
Extends Simple-Colors by the use of hinge linkages.
X-Colors
Uses only 2 colors, but also takes the implications for each color into account.
Color Trap
A technique that uses a single cluster to eliminate candidates outside the cluster.
Color Wrap
A technique that uses a single cluster to detect a contradiction in one of the colors.
Color Wing
A technique that uses multiple clusters to eliminate candidates outside these clusters. Same as Multi-Colors.
3D Medusa Coloring | Advanced Coloring | Ultracoloring
A set of techniques that uses colors on multiple digits.

Uniqueness

Uniqueness Test
A set of techniques that avoids the Unique Rectangle deadly pattern.
Avoidable Rectangle
A set of techniques that avoids the Unique Rectangle deadly pattern. Perhaps unique in solving techniques in that it employs solved cells as well as those unsolved.
Bivalue Universal Grave
A set of techniques that avoids the Bivalue Universal Grave deadly pattern.
BUG Lite
A set of techniques that avoids the BUG Lite deadly pattern.
Reverse BUG
While BUG looks at candidates of unsolved cells, Reverse BUG looks at solved cells instead.
Reverse BUG Lite
While BUG Lite looks at candidates of unsolved cells, Reverse BUG Lite looks at solved cells instead.
Uniqueness Clue Cover
Eliminates candidates by making the uniqueness assumption.
Uniqueness Controversy
These solving techniques assume that the Sudoku puzzle has a unique solution. It is not universally accepted that this assumption is a valid one.

Chains and Loops

Forcing Chain
Generic term for any type of chain.
X-Chain
Single digit chain of cells.
XY-Chain
Chain of bivalue cells.
Remote Pairs
Simplified form of XY-Chain, involving only two digits.
Fishy Cycle | X-Cycle
Single digit continuous loop.
Generalized Fishy Cycles
Strong generalization of Fishy Cycles and several other techniques. More difficult to apply.
Broken Wing
Eliminations caused by loops of odd length.
Nice Loops
Several types of loops formed by cells following strict rules and a notation system.
Double Implication Chain | DIC
There are 2 interpretations circulating. The first originates from a reliable source [1].
  • A Forcing Chain that has implications in both directions.
  • 2 Forcing Chains starting from a bivalue cell or a bilocal unit showing a verity.
Alternating Inference Chain | AIC
A chain that connects nodes of one or more candidates using alternating weak and strong inferences.
Oriented Chains
Oriented chains are generalisations of the basic xy-chains. The central idea is that the information collected from previous candidates in a chain (and/or from the target) can be used to select the next candidates. Oriented chains are either 2D or 3D:
- oriented 2D chains: xyt-chains, xyz-chains and xyzt-chains, together with their "hidden" counterparts: hxyt-chains, hxyz-chains and hxyzt-chains;
- oriented 3D chains: nrct-chains, nrcz-chains, nrczt-chains.
(The original reference to all these chains is the book "The Hidden Logic of Sudoku". Further web references forthcoming)

Wings

XY-Wing
Three cells with pivot cell XY and two pincer cells XZ and YZ.
XYZ-Wing
Three cells with pivot cell XYZ and two pincer cells XZ and YZ.
WXYZ-Wing
Four cells with pivot cell WXYZ and three pincer cells WZ, XZ and YZ.
W-Wing
Four cells in a chain: a cell WX, a cell with X as a candidate, another cell with X as a candidate, another cell WX, such that the two cells containing X as a candidate have a strong link.

Almost Locked Sets

ALS-XZ rule
2 Almost Locked Sets with restricted common digit X perform eliminations for common digit Z.
ALS-XY-Wing rule
3 Almost Locked Sets with 2 restricted common digits Y and Z perform eliminations for common digit X.
ALS-XY-Chain
Very similar to XY-Chain, except that the nodes in the chain are Almost Locked Sets.
Death Blossom
A stem cell of N candidates pointing to N petals, each an Almost Locked Set.
Almost ALS
An almost locked set with 1 extra digit.

Enumeration on Selected Cells

Aligned Pair Exclusion
Checks combinations of digits in a pair of cells located in an intersection.
Aligned Triple Exclusion
Checks combinations of digits in a triple of cells located in an intersection.
Subset Exclusion
Extension of Aligned Pair Exclusion to arbitrary sets that need not be aligned.

Miscellaneous

Sue de Coq
Uses two intersecting sets A and B, where A is a set of N cells with N candidates in a line, B is a set of N cells with N candidates in a box, and the sets A - B and B - A have no common candidates.
Subset Counting | Extended Subset Principle
Considers the number of times a digit can be placed in a selected subset of cells.
Braid Analysis | Braiding | Traveling Pairs
Analyzes the distribution of digits in a chute, especially how pairs repeat in a chute.
Constraint Subsets
Generalized view of subset and fish techniques.
Equivalence Marks
Similar to coloring, but uses marks instead of colors to represent parity.
Gurth's Symmetrical Placement
Technique for puzzles with rotational symmetry.

Techniques of Last Resort

Most of these techniques are controversial. They are either too complex to be used by human solvers, or they require a lot of extra work, or they are not based on logic.

Forcing Net
A general term for techniques that investigate branching chains.
Tabling | Trebor's Tables
All implications for each move are collected in tables.
Graded Equivalence Marks | GEM
A system of marking candidates starting from 2 complementary starting positions.
Bowman Bingo
A systematic approach to investigate implications.
Trial & Error | Ariadne's Thread | Bifurcation
The implications for a single move are investigated.
Nishio
Trial & Error limited to single digit.
Templating | Pattern Overlay Method | POM
All possible ways to place a digit in the remaining candidate space are investigated.
Guessing
Random moves are made, without any logic behind them.

Brute Force

These are primarily designed for computer solver programs.

External Links