Brute-force search tests many or all possible candidates until it finds a valid solution. It is straightforward to implement, but the candidate space can grow too quickly for larger problems. section 8.2 section 3.5
A practical brute-force solution usually follows these steps:
- Represent the input and candidate choices in searchable structures, such as city arrays and distance dictionaries. section 8.2
- Generate candidates, often with recursion and backtracking; permutation generation swaps elements, recurses, and restores the previous arrangement. section 8.2
- Validate each candidate, rejecting duplicate assignments or incomplete paths and retaining the best valid result. section 8.2 section 3.5
Traveling salesman problem
For five Vermont cities, generate every city permutation, append its starting city to close the route, total the pairwise distances, and keep the shortest path. The implementation finds a 318-mile route. The same exhaustive pattern solves SEND+MORE=MONEY by trying digit assignments, enforcing distinct digits, and checking the equation when all letters are assigned. section 8.2 section 3.5
Table 8.2. Driving distances between cities in Vermont
| Rutland |
Burlington |
White River Junction |
Bennington |
Brattleboro |
|
|---|---|---|---|---|---|
| Rutland | 0 | 67 | 46 | 55 | 75 |
| Burlington | 67 | 0 | 91 | 122 | 153 |
| White River Junction | 46 | 91 | 0 | 98 | 65 |
| Bennington | 55 | 122 | 98 | 0 | 40 |
| Brattleboro | 75 | 153 | 65 | 40 | 0 |
Use the distance table to trace candidate routes and understand how each path receives its total. section 8.2
