How Well Does It Work?
First intuition: Will get stuck in local minimum, with a few unsatisfied clauses.
No use for almost satisfying assignments. E.g., a plan with a “magic” step is useless. Contrast with optimization problems.
Surprise: It often finds global minimum! I.e., finds satisfying assignments.
Inspired by local search for CSP initially used on N-Queens: Heuristic Repair Method. (Minton et al. 1991)