Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Exact cover

Index Exact cover

In mathematics, given a collection \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^* of \mathcal such that each element in X is contained in exactly one subset in \mathcal^*. [1]

42 relations: Algorithm, Backtracking, Binary relation, Bipartite graph, Computer science, Computers and Intractability, Constraint satisfaction problem, Converse relation, Cover (topology), Dancing Links, Decision problem, Depth-first search, Difference-map algorithm, Disjoint sets, Donald Knuth, Doubly linked list, Eight queens puzzle, Empty set, Function (mathematics), Heterogeneous relation, Hypergraph, Incidence matrix, Intersection (set theory), Karp's 21 NP-complete problems, Knuth's Algorithm X, List of NP-complete problems, Matching (graph theory), Mathematics, Nondeterministic algorithm, NP-completeness, Partition of a set, Pentomino, Recursion (computer science), Reduction (complexity), Restriction (mathematics), Set cover problem, Subset, Sudoku, Sudoku solving algorithms, Surjective function, Union (set theory), 3-dimensional matching.


In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: Exact cover and Algorithm · See more »


Backtracking is a general algorithm for finding all (or some) 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 determines that the candidate cannot possibly be completed to a valid solution.

New!!: Exact cover and Backtracking · See more »

Binary relation

In mathematics, a binary relation on a set A is a set of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2.

New!!: Exact cover and Binary relation · See more »

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 such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.

New!!: Exact cover and Bipartite graph · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Exact cover and Computer science · See more »

Computers and Intractability

In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.

New!!: Exact cover and Computers and Intractability · See more »

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.

New!!: Exact cover and Constraint satisfaction problem · See more »

Converse relation

In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation.

New!!: Exact cover and Converse relation · See more »

Cover (topology)

In mathematics, a cover of a set X is a collection of sets whose union contains X as a subset.

New!!: Exact cover and Cover (topology) · See more »

Dancing Links

In computer science, dancing links is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem.

New!!: Exact cover and Dancing Links · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: Exact cover and Decision problem · See more »

Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.

New!!: Exact cover and Depth-first search · See more »

Difference-map algorithm

The difference-map algorithm is a search algorithm for general constraint satisfaction problems.

New!!: Exact cover and Difference-map algorithm · See more »

Disjoint sets

In mathematics, two sets are said to be disjoint sets if they have no element in common.

New!!: Exact cover and Disjoint sets · See more »

Donald Knuth

Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.

New!!: Exact cover and Donald Knuth · See more »

Doubly linked list

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes.

New!!: Exact cover and Doubly linked list · See more »

Eight queens puzzle

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.

New!!: Exact cover and Eight queens puzzle · See more »

Empty set

In mathematics, and more specifically set theory, the empty set or null set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero.

New!!: Exact cover and Empty set · See more »

Function (mathematics)

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.

New!!: Exact cover and Function (mathematics) · See more »

Heterogeneous relation

In mathematics, a heterogeneous relation is a subset of a Cartesian product A × B, where A and B are distinct sets.

New!!: Exact cover and Heterogeneous relation · See more »


In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices.

New!!: Exact cover and Hypergraph · See more »

Incidence matrix

In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects.

New!!: Exact cover and Incidence matrix · See more »

Intersection (set theory)

In mathematics, the intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.

New!!: Exact cover and Intersection (set theory) · See more »

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.

New!!: Exact cover and Karp's 21 NP-complete problems · See more »

Knuth's Algorithm X

"Algorithm X" is the name Donald Knuth used in his paper "Dancing Links" to refer to "the most obvious trial-and-error approach" for finding all solutions to the exact cover problem.

New!!: Exact cover and Knuth's Algorithm X · See more »

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.

New!!: Exact cover and List of NP-complete problems · See more »

Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.

New!!: Exact cover and Matching (graph theory) · See more »


Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

New!!: Exact cover and Mathematics · See more »

Nondeterministic algorithm

In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.

New!!: Exact cover and Nondeterministic algorithm · See more »


In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: Exact cover and NP-completeness · See more »

Partition of a set

In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.

New!!: Exact cover and Partition of a set · See more »


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.

New!!: Exact cover and Pentomino · See more »

Recursion (computer science)

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to iteration).

New!!: Exact cover and Recursion (computer science) · See more »

Reduction (complexity)

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.

New!!: Exact cover and Reduction (complexity) · See more »

Restriction (mathematics)

In mathematics, the restriction of a function f is a new function f\vert_A obtained by choosing a smaller domain A for the original function f. The notation f is also used.

New!!: Exact cover and Restriction (mathematics) · See more »

Set cover problem

The set cover problem is a classical question in combinatorics, computer science and complexity theory.

New!!: Exact cover and Set cover problem · See more »


In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

New!!: Exact cover and Subset · See more »


(originally called Number Place) is a logic-based, combinatorial number-placement puzzle.

New!!: Exact cover and Sudoku · See more »

Sudoku solving algorithms

A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns.

New!!: Exact cover and Sudoku solving algorithms · See more »

Surjective function

In mathematics, a function f from a set X to a set Y is surjective (or onto), or a surjection, if for every element y in the codomain Y of f there is at least one element x in the domain X of f such that f(x).

New!!: Exact cover and Surjective function · See more »

Union (set theory)

In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.

New!!: Exact cover and Union (set theory) · See more »

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-uniform hypergraphs.

New!!: Exact cover and 3-dimensional matching · See more »

Redirects here:

Exact Cover, Exact cover problem, Exact hitting set.


[1] https://en.wikipedia.org/wiki/Exact_cover

Hey! We are on Facebook now! »