In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, given a collection of
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
, an exact cover is a subcollection of such that each element in is contained in ''exactly one'' subset in . In other words, is a
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of consisting of subsets contained in .
One says that each element in is covered by exactly one subset in . An exact cover is a kind of
cover
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of co ...
.
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the exact cover problem is a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
to determine if an exact cover exists. The exact cover problem is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
[
This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems.
] and is one of
Karp's 21 NP-complete problems
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the bo ...
. It is NP-complete even when each subset in contains exactly three elements; this restricted problem is known as exact cover by 3-sets, often abbreviated X3C.
The exact cover problem is a kind of
constraint satisfaction problem
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constra ...
.
An exact cover problem can be represented by an
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
or a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
.
Knuth's Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the d ...
is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
that finds all solutions to an exact cover problem. DLX is the name given to Algorithm when it is implemented efficiently using
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
's
Dancing Links
In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Knuth's Algorithm X for the exact ...
technique on a computer.
The standard exact cover problem can be generalized slightly to involve not only "exactly one" constraints but also "at-most-one" constraints.
Finding
Pentomino
Derived from the Greek word for ' 5', and "domino", a pentomino (or 5-omino) is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to ...
tilings and solving
Sudoku
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
are noteworthy examples of exact cover problems. The
n queens problem is a slightly generalized exact cover problem.
Formal definition
Given a collection
of
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of a set
, an exact cover of
is a subcollection
of
that satisfies two conditions:
* The
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
of any two distinct subsets in
is
empty
Empty may refer to:
Music Albums
* ''Empty'' (God Lives Underwater album) or the title song, 1995
* ''Empty'' (Nils Frahm album), 2020
* ''Empty'' (Tait album) or the title song, 2001
Songs
* "Empty" (The Click Five song), 2007
* ...
, i.e., the subsets in
are
pairwise disjoint
In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
. In other words, each element in
is contained in ''at most one'' subset in
.
* The
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
of the subsets in
is
, i.e., the subsets in
cover
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of co ...
. In other words, each element in
is contained in ''at least one'' subset in
.
In short, an exact cover is "exact" in the sense that each element in
is contained in ''exactly one'' subset in
.
Equivalently, an exact cover of
is a subcollection
of
that
partitions
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
.
For an exact cover of
to exist, it is necessary that:
* The union of the subsets in
is
. In other words, each element in
is contained in at least one subset in
.
If the
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
∅ is contained in
, then it makes no difference whether or not it is in any exact cover. Thus it is typical to assume that:
* The empty set is not in
. In other words, each subset in
contains at least one element.
Basic examples
Let = be a collection of subsets of a set ''X'' = such that:
* ''N'' = ,
* ''O'' = ,
* ''P'' = , and
* ''E'' = .
The subcollection is an exact cover of ''X'', since the subsets ''O'' = and ''E'' = are disjoint and their union is ''X'' = .
The subcollection is also an exact cover of ''X''.
Including the empty set ''N'' = makes no difference, as it is disjoint with all subsets and does not change the union.
The subcollection is not an exact cover of ''X''.
Even though the union of the subsets ''E'' and ''P'' is = ''X'', the intersection of the subsets ''E'' and ''P'', , is not empty. Therefore the subsets ''E'' and ''P'' do not meet the "disjoint" requirement of an exact cover.
The subcollection is also not an exact cover of ''X''.
Even though ''N'' and ''P'' are disjoint, their union is not ''X'', so they fail the "cover" requirement.
On the other hand, there is no exact cover—indeed, not even a cover—of ''Y'' = because
is a proper subset of ''Y'': None of the subsets in contains the element 5.
Detailed example
Let = be a collection of subsets of a set ''X'' = such that:
* ''A'' = ;
* ''B'' = ;
* ''C'' = ;
* ''D'' = ;
* ''E'' = ; and
* ''F'' = .
Then the subcollection = is an exact cover, since each element in ''X'' is contained in exactly one of the subsets:
* ''B'' = ;
* ''D'' = ; or
* ''F'' = .
Moreover, is the only exact cover, as the following argument demonstrates: Because ''A'' and ''B'' are the only subsets containing 1, an exact cover must contain ''A'' or ''B'', but not both. If an exact cover contains ''A'', then it doesn't contain ''B'', ''C'', ''E'', or ''F'', as each of these subsets has an element in common with ''A''. Then ''D'' is the only remaining subset, but the collection doesn't cover the element 2. In conclusion, there is no exact cover containing ''A''. On the other hand, if an exact cover contains ''B'', then it doesn't contain ''A'' or ''C'', as each of these subsets has an element in common with ''B''. Because ''D'' is the only remaining subset containing 5, ''D'' must be part of the exact cover. If an exact cover contains ''D'', then it doesn't contain ''E'', as ''E'' has an element in common with ''D''. Then ''F'' is the only remaining subset, and the collection is indeed an exact cover. See the
example
Example may refer to:
* '' exempli gratia'' (e.g.), usually read out in English as "for example"
* .example, reserved as a domain name that may not be installed as a top-level domain of the Internet
** example.com, example.net, example.org, ex ...
in the article on
Knuth's Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the d ...
for a matrix-based version of this argument.
Representations
An exact cover problem is defined by the
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
"contains" between subsets in and elements in ''X''. There are different equivalent ways to represent this relation.
Standard representation
The standard way to represent the relation "contains" is to list the elements in each subset.
For example, the
detailed example above uses this standard representation:
* ''A'' = ;
*
''B'' = ;
* ''C'' = ;
*
''D'' = ;
* ''E'' = ; and
*
''F'' = .
Again, the subcollection = is an exact cover, since each element is contained in exactly one selected subset, as the highlighting makes clear.
Inverse representation
The relation "contains" between subsets and elements can be
converted, listing the subsets in which each element is contained.
For example, the relation "contains" in the
detailed example above can be represented by listing the subsets each element is contained in:
* 1 is an element of ''A'',
''B'';
* 2 is an element of ''E'',
''F'';
* 3 is an element of
''D'', ''E'';
* 4 is an element of ''A'',
''B'', ''C'';
* 5 is an element of ''C'',
''D'';
* 6 is an element of
''D'', ''E''; and
* 7 is an element of ''A'', ''C'', ''E'',
''F''.
Again, the subcollection = is an exact cover, since each element is contained in exactly one selected subset, as the highlighting makes clear.
When solving an exact cover problem, it is often useful to switch between the standard and inverse representations.
Matrix and hypergraph representations
The relation "contains" can be represented by an
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
.
The matrix includes one row for each subset in and one column for each element in ''X''.
The entry in a particular row and column is 1 if the corresponding subset contains the corresponding element, and is 0 otherwise.
As each row represents the elements contained in the corresponding subset and each column represents the subsets containing the corresponding element, an incidence matrix effectively provides both the standard and inverse representations.
In the matrix representation, an exact cover is a selection of rows such that each column contains a 1 in exactly one selected row.
For example, the relation "contains" in the
detailed example above can be represented by a 6×7 incidence matrix:
:
Again, the subcollection = is an exact cover, since each element is contained in exactly one selected subset, i.e., each column contains a 1 in exactly one selected row, as the highlighting makes clear.
See the
example
Example may refer to:
* '' exempli gratia'' (e.g.), usually read out in English as "for example"
* .example, reserved as a domain name that may not be installed as a top-level domain of the Internet
** example.com, example.net, example.org, ex ...
in the article on
Knuth's Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the d ...
for a matrix-based solution to the
detailed example above.
In turn, the incidence matrix can be seen also as describing a
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
. The hypergraph includes one node for each element in ''X'' and one edge for each subset in ; each node is included in exactly one of the edges forming the cover.
Graph representation
The relation "contains" can be represented by a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
.
The vertices of the graph are divided into two disjoint sets, one representing the subsets in and another representing the elements in ''X''. If a subset contains an element, an edge connects the corresponding vertices in the graph.
In the graph representation, an exact cover is a selection of vertices corresponding to subsets such that each vertex corresponding to an element is connected to exactly one selected vertex.
For example, the relation "contains" in the
detailed example above can be represented by a bipartite graph with 6+7 = 13 vertices:
![Exact-cover-bigraph-highlighted](https://upload.wikimedia.org/wikipedia/commons/9/96/Exact-cover-bigraph-highlighted.svg)
Again, the subcollection = is an exact cover, since each element is contained in exactly one selected subset, i.e., the vertex corresponding to each element in ''X'' is connected to exactly one selected vertex, as the highlighting makes clear.
Equivalent problems
Although the canonical exact cover problem involves a collection of subsets of a set ''X'', the logic does not depend on the presence of subsets containing elements. An "abstract exact cover problem" arises whenever there is a
heterogeneous relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
between two sets ''P'' and ''Q'' and the goal is to select a subset ''P*'' of ''P'' such that each element in ''Q'' is related to ''exactly one'' element in ''P*''. In general, the elements of ''P'' represent choices and the elements of ''Q'' represent "exactly one" constraints on those choices.
More formally, given a binary relation ''R'' ⊆ ''P'' × ''Q'' between sets ''P'' and ''Q'', one can call a subset ''P*'' of ''P'' an "abstract exact cover" of ''Q'' if each element in ''Q'' is ''R''
T-related to exactly one element in ''P*''. Here ''R''
T is the
converse
Converse may refer to:
Mathematics and logic
* Converse (logic), the result of reversing the two parts of a definite or implicational statement
** Converse implication, the converse of a material implication
** Converse nonimplication, a logical c ...
of ''R''.
In general, ''R''
T restricted to ''Q'' × ''P*'' is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
from ''Q'' to ''P*'', which maps each element in ''Q'' to the unique element in ''P*'' that is ''R''-related to that element in ''Q''. This function is
onto
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
, unless ''P*'' contains the "empty set," i.e., an element which isn't ''R''-related to any element in ''Q''.
In the canonical exact cover problem, ''P'' is a collection of subsets of ''X'', ''Q'' is the set ''X'', ''R'' is the binary relation "contains" between subsets and elements, and ''R''
T restricted to ''Q'' × ''P*'' is the function "is contained in" from elements to selected subsets.
Exact hitting set
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, given a collection of subsets of a set ''X'', an exact hitting set ''X*'' is a subset of ''X'' such that each subset in contains ''exactly one'' element in ''X*''. One says that each subset in is hit by exactly one element in ''X*''.
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the exact hitting set problem is a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
to find an exact hitting set or else determine none exists.
The exact hitting set problem is an abstract exact cover problem. In the
notation above, ''P'' is the set ''X'', ''Q'' is a collection of subsets of ''X'', ''R'' is the binary relation "is contained in" between elements and subsets, and ''R''
−1 restricted to ''Q'' × ''P*'' is the function "contains" from subsets to selected elements.
Whereas an exact cover problem involves selecting subsets and the relation "contains" from subsets to elements, an exact hitting set problem involves selecting elements and the relation "is contained in" from elements to subsets.
In a sense, an exact hitting set problem is the inverse of the exact cover problem involving the same set and collection of subsets.
Exact hitting set example
As in the
detailed exact cover example above, let = be a collection of subsets of a set ''X'' = such that:
* ''A'' = ;
* ''B'' = ;
* ''C'' = ;
* ''D'' = ;
* ''E'' = ; and
* ''F'' = .
Then ''X*'' = is an exact hitting set, since each subset in contains exactly one element in ''X*'', as the highlighting makes clear.
Moreover, is the only exact hitting set, as the following argument demonstrates:
Because 2 and 7 are the only elements that hit ''F'', an exact hitting set must contain 2 or 7, but not both.
If an exact hitting set contains 7, then it doesn't contain 1, 2, 3, 4, 5, or 6, as each of these elements are contained in some subset also containing 7.
Then there are no more remaining elements, but is not an exactly hitting set, as it doesn't hit ''B'' or ''D''.
In conclusion, there is no exact hitting set containing 7.
On the other hand, if an exact hitting set contains 2, then it doesn't contain 3, 6, or 7, as each of these elements are contained in some subset also containing 2.
Because 5 is the only remaining element that hits ''D'', the exact hitting set must contain 5.
If an exact hitting set contains 5, then it doesn't contain 4, as both hit ''C''.
Because 1 is the only remaining element that hits ''A'', the exact hitting set must contain 1.
Then there are no more remaining elements, and is indeed an exact hitting set.
Although this example involves the same collection of subsets as the detailed exact cover example above, it is essentially a different problem. In a sense, the exact hitting set problem is the inverse (or transpose or converse) of the corresponding exact cover problem above, as the matrix representation makes clear:
:
Dual example
But there is another exact hitting set problem that is essentially the same as the
detailed exact cover example above, in which numbered elements become subsets and lettered subsets become elements, effectively inverting the relation between subsets and element.
For example, as the subset ''B'' contains the elements 1 and 4 in the exact cover problem, the subsets ''I'' and ''IV'' contain the element ''b'' in the dual exact hitting set problem.
In particular, let = be a collection of subsets of a set ''X'' = such that:
* ''I'' =
* ''II'' =
* ''III'' =
* ''IV'' =
* ''V'' =
* ''VI'' =
* ''VII'' =
Then ''X*'' = is an exact hitting set, since each subset in contains (is hit by) exactly one element in ''X*'', as the highlighting makes clear.
The exact hitting set ''X*'' = here is essentially the same as the exact cover = above, as the matrix representation makes clear:
:
Finding solutions
Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward Recursion (computer science), recursive, Nondeterministic algorithm, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate ...
is the name
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
gave for "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem.
Technically, Algorithm X is a
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
,
nondeterministic,
depth-first
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...
,
backtracking
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
.
When Algorithm X is implemented efficiently using
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
's
Dancing Links
In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Knuth's Algorithm X for the exact ...
technique on a computer, Knuth calls it DLX. DLX uses the matrix representation of the problem, implemented as a series of
doubly linked list
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked record (computer science), records called node (computer science), nodes. Each node contains three field (computer science), fields: ...
s of the 1s of the matrix: each 1 element has a link to the next 1 above, below, to the left, and to the right of itself. (Technically, because the lists are circular, this forms a torus). Because exact cover problems tend to be sparse, this representation is usually much more efficient in both size and processing time required. DLX then uses the
Dancing Links
In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Knuth's Algorithm X for the exact ...
technique to quickly select permutations of rows as possible solutions and to efficiently backtrack (undo) mistaken guesses.
Generalizations
In a standard exact cover problem, each constraint must be satisfied exactly once.
It is a simple generalization to relax this requirement slightly and allow for the possibility that some "primary" constraints must be satisfied by ''exactly one'' selection but other "secondary" constraints can be satisfied by ''at most one'' selection.
As Knuth explains, a generalized exact cover problem can be converted to an equivalent exact cover problem by simply appending one row for each secondary column, containing a single 1 in that column. If in a particular candidate solution a particular secondary column is satisfied, then the added row isn't needed.
But if the secondary column isn't satisfied, as is allowed in the generalized problem but not the standard problem, then the added row can be selected to ensure the column is satisfied.
But Knuth goes on to explain that it is better working with the generalized problem directly, because the generalized algorithm is simpler and faster: A simple change to his Algorithm X allows secondary columns to be handled directly.
The
N queens problem is an example of a generalized exact cover problem, as the constraints corresponding to the diagonals of the chessboard have a maximum rather than an exact queen count.
Noteworthy examples
Due to its NP-completeness, any problem in NP can be
reduced to exact cover problems, which then can be solved with techniques such as Dancing Links. However, for some well known problems, the reduction is particularly direct. For instance, the problem of tiling a board with
pentominoes, and solving
Sudoku
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
can both be viewed as exact cover problems.
Pentomino tiling
The problem of tiling a 60-square board with the 12 different free
pentominoes is an example of an exact cover problem, as
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
explains in his paper "Dancing links."
For example, consider the problem of tiling with pentominoes an 8×8 chessboard with the 4 central squares removed:
:
The problem involves two kinds of constraints:
: Pentomino: For each of the 12 pentominoes, there is the constraint that it must be placed exactly once. Name these constraints after the corresponding pentominoes: F I L P N T U V W X Y Z.
: Square: For each of the 60 squares, there is the constraint that it must be covered by a pentomino exactly once. Name these constraints after the corresponding squares in the board: ''ij'', where ''i'' is the rank and ''j'' is the file.
Thus there are 12+60 = 72 constraints in all.
As both kinds of constraints are "exactly one" constraints, the problem is an exact cover problem.
The problem involves many choices, one for each way to place a pentomino on the board.
It is convenient to consider each choice as satisfying a set of 6 constraints: 1 constraint for the pentomino being placed and 5 constraints for the five squares where it is placed.
In the case of an 8×8 chessboard with the 4 central squares removed, there are 1568 such choices, for example:
*
*
* …
*
*
* …
*
*
* …
One of many solutions of this exact cover problem is the following set of 12 choices:
*
*
*
*
*
*
*
*
*
*
*
*
This set of choices corresponds to the following solution to the pentomino tiling problem:
![Pentomino Puzzle Solution 8x8 Minus Center](https://upload.wikimedia.org/wikipedia/commons/2/20/Pentomino_Puzzle_Solution_8x8_Minus_Center.svg)
A pentomino tiling problem is more naturally viewed as an exact cover problem than an exact hitting set problem, because it is more natural to view each choice as a set of constraints than each constraint as a set of choices.
Each choice relates to just 6 constraints, which are easy to enumerate. On the other hand, each constraint relates to many choices, which are harder to enumerate.
Whether viewed as an exact cover problem or an exact hitting set problem, the matrix representation is the same, having 1568 rows corresponding to choices and 72 columns corresponding to constraints. Each row contains a single 1 in the column identifying the pentomino and five 1s in the columns identifying the squares covered by the pentomino.
Using the matrix, a computer can find all solutions relatively quickly, for example, using
Dancing Links
In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Knuth's Algorithm X for the exact ...
.
Sudoku
''Main articles:
Sudoku
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
,
Mathematics of Sudoku
The mathematics of Sudoku refers to the use of mathematics to study Sudoku puzzles to answer questions such as ''"How many filled Sudoku grids are there?"'', "''What is the minimal number of clues in a valid puzzle?''" and ''"In what ways can S ...
,
Sudoku solving algorithms''
The problem in
Sudoku
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
is to assign numbers (or digits, values, symbols) to cells (or squares) in a grid so as to satisfy certain constraints.
In the standard 9×9 Sudoku variant, there are four kinds of constraints:
: Row-Column: Each intersection of a row and column, i.e, each cell, must contain exactly one number.
: Row-Number: Each row must contain each number exactly once
: Column-Number: Each column must contain each number exactly once.
: Box-Number: Each box must contain each number exactly once.
While the first constraint might seem trivial, it is nevertheless needed to ensure there is only one number per cell. Intuitively, placing a number into a cell prohibits placing that number in any other cell sharing the same column, row, or box and also prohibits ''placing any other number'' into the now occupied cell.
Solving Sudoku is an exact cover problem.
More precisely, solving Sudoku is an exact
hitting set
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
problem, which is equivalent to an exact cover problem, when viewed as a problem to select possibilities such that each constraint set contains (i.e., is hit by) exactly one selected possibility.
In the notation above for the (generalized) exact cover problem, ''X'' is the set of possibilities, ''Y'' is a set of constraint sets, and ''R'' is the binary relation "is contained in."
Each possible assignment of a particular number to a particular cell is a possibility (or candidate). When Sudoku is played with pencil and paper, possibilities are often called pencil marks.
In the standard 9×9 Sudoku variant, in which each of 9×9 cells is assigned one of 9 numbers, there are 9×9×9=729 possibilities.
Using obvious notation for rows, columns and numbers, the possibilities can be labeled
: R1C1#1, R1C1#2, …, R9C9#9.
The fact that each kind of constraint involves exactly one of something is what makes Sudoku an exact hitting set problem. The constraints can be represented by constraint sets. The problem is to select possibilities such that each constraint set contains (i.e., is hit by) exactly one selected possibility.
In the standard 9×9 Sudoku variant, there are four kinds of constraints sets corresponding to the four kinds of constraints:
: Row-Column: A row-column constraint set contains all the possibilities for the intersection of a particular row and column, i.e., for a cell. For example, the constraint set for row 1 and column 1, which can be labeled R1C1, contains the 9 possibilities for row 1 and column 1 but different numbers:
:: R1C1 = .
: Row-Number: A row-number constraint set contains all the possibilities for a particular row and number. For example, the constraint set for row 1 and number 1, which can be labeled R1#1, contains the 9 possibilities for row 1 and number 1 but different columns:
:: R1#1 = .
: Column-Number: A column-number constraint set contains all the possibilities for a particular column and number. For example, the constraint set for column 1 and number 1, which can be labeled C1#1, contains the 9 possibilities for column 1 and number 1 but different rows:
:: C1#1 = .
: Box-Number: A box-number constraint set contains all the possibilities for a particular box and number. For example, the constraint set for box 1 (in the upper lefthand corner) and number 1, which can be labeled B1#1, contains the 9 possibilities for the cells in box 1 and number 1:
:: B1#1 = .
Since there are 9 rows, 9 columns, 9 boxes and 9 numbers, there are 9×9=81 row-column constraint sets, 9×9=81 row-number constraint sets, 9×9=81 column-number constraint sets, and 9×9=81 box-number constraint sets: 81+81+81+81=324 constraint sets in all.
In brief, the standard 9×9 Sudoku variant is an exact hitting set problem with 729 possibilities and 324 constraint sets.
Thus the problem can be represented by a 729×324 matrix.
Although it is difficult to present the entire 729×324 matrix, the general nature of the matrix can be seen from several snapshots:
The complete 729×324 matrix is available from Robert Hanson.
Note that the set of possibilities R''x''C''y''#''z'' can be arranged as a 9×9×9 cube in a 3-dimensional space with coordinates ''x'', ''y'', and ''z''. Then each row R''x'', column C''y'', or number #''z'' is a 9×9×1 "slice" of possibilities; each box B''w'' is a 9x3×3 "tube" of possibilities; each row-column constraint set R''x''C''y'', row-number constraint set R''x''#''z'', or column-number constraint set C''y''#''z'' is a 9x1×1 "strip" of possibilities; each box-number constraint set B''w''#''z'' is a 3x3×1 "square" of possibilities; and each possibility R''x''C''y''#''z'' is a 1x1×1 "cubie" consisting of a single possibility. Moreover, each constraint set or possibility is the
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
of the component sets. For example, R1C2#3 = R1 ∩ C2 ∩ #3, where ∩ denotes set intersection.
Although other Sudoku variations have different numbers of rows, columns, numbers and/or different kinds of constraints, they all involve possibilities and constraint sets, and thus can be seen as exact hitting set problems.
''N'' queens problem
The
''N'' queens problem is an example of a generalized exact cover problem.
The problem involves four kinds of constraints:
: Rank: For each of the ''N'' ranks, there must be exactly one queen.
: File: For each of the ''N'' files, there must be exactly one queen.
: Diagonals: For each of the 2''N'' − 1 diagonals, there must be at most one queen.
: Reverse diagonals: For each of the 2''N'' − 1 reverse diagonals, there must be at most one queen.
Note that the 2''N'' rank and file constraints form the primary constraints, while the 4''N'' − 2 diagonal and reverse diagonals form the secondary constraints. Further, because each of first and last diagonal and reverse diagonals involves only one square on the chessboard, these can be omitted and thus one can reduce the number of secondary constraints to 4''N'' − 6. The matrix for the ''N'' queens problem then has ''N''
2 rows and 6''N'' − 6 columns, each row for a possible queen placement on each square on the chessboard, and each column for each constraint.
See also
*
Constraint satisfaction problem
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constra ...
*
Dancing Links
In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Knuth's Algorithm X for the exact ...
*
Difference map algorithm
*
Hitting set
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
*
Karp's 21 NP-complete problems
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the bo ...
*
Knuth's Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the d ...
*
List of NP-complete problems
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in . ...
*
Perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
and
3-dimensional matching
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (inste ...
are special cases of the exact cover problem
*
Partition of a set
In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.
Every equivalence relation on a set defines a partition of this set, and every parti ...
References
External links
Free Software implementation of an Exact Cover solver in C- uses Algorithm X and Dancing Links. Includes examples for sudoku and logic grid puzzles.
Exact Cover solver in Golang- uses Algorithm X and Dancing Links. Includes examples for sudoku and n-queens.
- Math Reference Project
{{DEFAULTSORT:Exact Cover
Theoretical computer science
NP-complete problems