In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically checking all possible candidates for whether or not each candidate satisfies the problem's statement.
A brute-force algorithm that finds the divisors of a natural number n would enumerate all integers from 1 to n, and check whether each of them divides n without remainder.
This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences or when using a computer to prove a mathematical theorem.
The brute-force method for finding an item in a table – namely, check all entries of the latter, sequentially – is called linear search.
The main disadvantage of the brute-force method is that, for many real-world problems, the number of natural candidates is prohibitively large.
If n is a random 64-bit natural number, which has about 19 decimal digits on the average, the search will take about 10 years.
This steep growth in the number of candidates, as the size of the data increases, occurs in all sorts of problems.
In 2005, all chess game endings with six pieces or less were solved, showing the result of each position if played perfectly.
[3][4] One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class.
As this example shows, a little bit of analysis will often lead to dramatic reductions in the number of candidate solutions, and may turn an intractable problem into a trivial one.
However, that problem can be solved much more efficiently by starting with 417 and repeatedly adding 417 until the number exceeds 1,000,000 – which takes only 2398 (= 1,000,000 ÷ 417) steps, and no tests.
There are many other search methods, or metaheuristics, which are designed to take advantage of various kinds of partial knowledge one may have about the solution.