Brute-force search systematically tries every available candidate or combination without using special knowledge about the problem. It is also called uninformed, unguided, or blind search. The approach is straightforward: represent the possibilities, explore them, and keep track of visited states when cycles could cause endless repetition. section 2.8
Brute-force search is useful when:
- The search space is small enough that checking every possibility is practical. section 2.8
- You need a dependable baseline that can find an answer without domain-specific guidance. section 2.8
- You can compare all valid candidates and select the best one, as in a constrained optimization problem. section 4.2
Two common search orders are depth-first search, which follows one path as far as possible, and breadth-first search, which examines all options at one depth before going deeper. Both may require visited-state tracking. Generating the entire possibility tree first is usually wasteful, so search algorithms generate and inspect it iteratively. section 2.8
Knapsack: inspect every combination
Suppose a knapsack has a fixed weight limit and several items with different weights and values. A brute-force solution calculates every combination, discards combinations exceeding the weight limit, compares the values of the remaining combinations, and chooses the most valuable one. This can produce the optimal answer for a small example, but the number of combinations makes the approach increasingly expensive as the dataset grows. section 4.2
Figure 2.15 All possible movement options represented as a tree
Use the maze tree to inspect how brute-force search represents alternative paths, valid solutions, and a path invalidated by the no-repeated-block constraint. section 2.8
