Generate-and-Test

Generate-and-test is the simplest heuristic search strategy: repeatedly generate a possible solution, then test whether it is actually a solution — keep going until one passes, or the space is exhausted.

Algorithm

1. Generate a possible solution (a point in the problem space, or a path from the initial state)
2. Test the candidate to see if it is actually a solution, by comparing it to the goal
3. If it is a solution, stop and report it
4. Otherwise, go back to step 1 and generate another candidate

Variants

Classic Example: Cryptarithmetic (SEND + MORE = MONEY)

Generate an assignment of digits 0–9 to letters S, E, N, D, M, O, R, Y (no leading zero, all letters distinct), then test whether SEND + MORE = MONEY holds arithmetically. Exhaustive generate-and-test over roughly 1.8 million possible assignments is workable by computer but wasteful by hand — a heuristic version prunes using column-wise carry constraints (M must be 1, since two 4-digit numbers summing to a 5-digit number forces a carry into a new digit).

Strengths and Weaknesses

Generate-and-test is the conceptual ancestor of hill climbing and best-first search — both are "smarter" versions that use a heuristic to decide which candidate to generate next, rather than generating blindly.