Brute-force search

Brute-force search, also called exhaustive search or generate and test, is a foundational algorithmic paradigm in computer science. It operates by enumerating every possible candidate solution to a problem and testing each one against the problem’s requirements. For instance, to find the divisors of a natural number, a brute-force algorithm would check every integer from one up to that number, testing whether each divides it evenly. For the eight queens puzzle, a brute-force approach would examine every possible arrangement of eight queens on a sixty-four-square chessboard and verify whether any queen attacks another. The method is straightforward to implement and guarantees finding a solution if one exists, but its cost scales directly with the number of candidates. This number often grows explosively as the problem size increases, a phenomenon known as combinatorial explosion. For example, checking all divisors of a sixteen-digit number requires roughly ten quadrillion instructions, taking days on a typical computer. Similarly, rearranging twenty letters yields about two quintillion candidates, a search that can last years. Consequently, brute-force search is practical mainly for small problem instances, when problem-specific heuristics can shrink the candidate set, or when simplicity of implementation outweighs processing speed. It is also used in critical applications where algorithm errors are unacceptable, or when proving mathematical theorems. The technique serves as a baseline for benchmarking other algorithms and can be viewed as the simplest metaheuristic. It differs from backtracking, which discards large groups of solutions without explicit enumeration. The core algorithm requires four procedures: one to generate the first candidate, one to produce the next candidate (returning a null value when none remain), one to validate a candidate, and one to output a valid solution. The search then iterates through candidates, testing each.