Brute-force search
A problem-solving method checking all possible candidates.
Brute-force search, also known as exhaustive search or generate and test, is a general problem-solving technique and algorithmic paradigm in computer science. It involves systematically checking all possible candidates for a problem to determine whether each satisfies the problem's statement.
- field
- Computer science
- known_for
- Systematic enumeration of all candidate solutions
- type
- Algorithmic paradigm
- also_known_as
- Exhaustive search, generate and test
- related_concepts
- Combinatorial explosion, linear search, backtracking
Lore & Background
The brute-force search method is simple to implement and will always find a solution if one exists. Its implementation costs are proportional to the number of candidate solutions, which in many practical problems grows very quickly as problem size increases—a phenomenon called combinatorial explosion. For example, finding divisors of a number n requires testing all integers from 1 to n; for a 64-bit natural number, this could take about 10 years on a typical PC. The method is typically used when problem size is limited, when heuristics can reduce the candidate set, or when simplicity of implementation outweighs processing speed.
Reader's Guide
Brute-force search serves as a baseline method for benchmarking other algorithms or metaheuristics and can be viewed as the simplest metaheuristic. It is used in critical applications where algorithm errors would have serious consequences, or when using a computer to prove a mathematical theorem. The method should not be confused with backtracking, which can discard large solution sets without explicit enumeration. Reordering the search space can also improve expected running time when only one solution is needed. The technique remains fundamental in computer science for its generality and reliability.
Did You Know?
- A brute-force algorithm for the eight queens puzzle would examine all possible arrangements of 8 pieces on a 64-square chessboard.
- The number of candidates for 20 letters is 20!, about 2.4×10^18, requiring about 10 years of search.
- Linear search, checking all entries of a table sequentially, is a brute-force method for finding an item.
Frequently Asked Questions
Who is Brute-force search?
Brute-force search is a foundational algorithmic paradigm in computer science that solves problems by methodically testing every single candidate until the correct one is identified. It is one of the most straightforward and universally applicable strategies in the field.
What are Brute-force search's powers/role?
Its core ability is systematic enumeration: it generates every possible candidate and checks each one against the problem's requirements. This makes it applicable to virtually any problem where a finite set of candidates exists, regardless of domain.
How does Brute-force search's story end?
Brute-force search typically gets outpaced by more efficient algorithms once the candidate space grows large, a phenomenon known as combinatorial explosion. In practice it often serves as a correctness baseline or last-resort fallback rather than the final solution for large-scale problems.
Why is Brute-force search important?
It provides a guaranteed-correct reference point that proves a problem is solvable and sets the performance bar against which smarter techniques like backtracking or pruning are measured. Without it, there would be no simple benchmark to demonstrate that an optimization actually helps.
What are Brute-force search's aliases?
It is also widely called "exhaustive search" or "generate and test" in the literature. All three names describe the same core idea of leaving no candidate unchecked before declaring a result.
More in Algorithms And Data Structures 1-24
Elsewhere in the Algorithms And Data Structures universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record