WalkSAT

WalkSAT is a family of stochastic local-search algorithms for solving satisfiability (SAT) problems expressed in conjunctive normal form (CNF). It is designed for large, difficult instances and is commonly used as a component in SAT solvers. WalkSAT starts from a random truth assignment and iteratively improves it by flipping variable values.

At each step, the algorithm selects an unsatisfied clause at random. From the literals in that clause, it chooses a variable to flip. The choice is probabilistic: with probability p the algorithm flips a randomly chosen variable from that clause; otherwise it flips the variable that minimizes the number of newly unsatisfied clauses after the flip (the break count). After performing the flip, the formula is re-evaluated. The process repeats until all clauses are satisfied or a predefined limit on flips or restarts is reached.

WalkSAT is incomplete; it does not guarantee finding a solution even if one exists. However, it often locates solutions quickly on many practical instances, especially when combined with restarts and adaptive parameter settings. It tends to perform well on random 3-SAT problems and on large industrial formulas, where the mix of greedy and random moves helps escape local minima.

Variations of the basic approach include WalkSAT with higher randomness to enhance exploration and different restart strategies. The algorithm has influenced a range of stochastic local-search methods in SAT and constraint satisfaction, serving as a practical tool for probing satisfiability in large-scale problems.