If you're taking a local search approach to a constraint satisfaction problem, something like two SAT or three SAT, a common approach is to define two variable assignments to be neighbors, if and only if they differ in the value of a single Variable. 