Overview
WalkSAT starts with a random truth assignment, repeatedly chooses an unsatisfied clause, and flips a variable using a mix of greedy improvement and random exploration.
CoreSource checked
WalkSAT
Searches for a satisfying assignment by flipping variables in unsatisfied clauses.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- SAT Solving
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
satisfiabilitysat solvinglocal searchrandom samplingoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(2^n)
Worst
O(2^n)
Space
O(2^n)
When to Use
- Use when a good assignment is enough and randomized local search is acceptable.
- Use when restart limits and randomness can be controlled experimentally.
When Not to Use
- Avoid when unsatisfiability must be proven.
- Avoid when deterministic, reproducible solver traces are required without fixed seeds.
What It Does
- Maintains a candidate Boolean assignment
- Chooses unsatisfied clauses
- Flips variables to reduce or escape conflicts
Use Cases
- Local-search SAT heuristics
- Large satisfiable formulas where a proof is not required
- Randomized baseline for constraint satisfaction
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Pseudocode
- 1.Generate a random assignment
- 2.Repeat until the flip limit
- 3.If all clauses are satisfied, return the assignment
- 4.Choose an unsatisfied clause
- 5.Flip a variable greedily or randomly according to the noise rule
- 6.Restart if the run reaches its limit
Canonical Example
- Input
- clauses (A or B), (!A or C), (!B or !C) and a random assignment
- Output
- a satisfying assignment if local flips find one before the limit
- Explanation
- Each step selects an unsatisfied clause and flips one of its variables.
Implementation Notes
- Maintain clause satisfaction counts incrementally.
- Expose seed, noise probability, flip limit, and restart count.
- Test formulas with known satisfying assignments.
Common Pitfalls
- Treating failure after a fixed number of flips as proof of unsatisfiability.
- Using noise parameters without validation can stall or random-walk too much.
- Forgetting to track which clauses become satisfied after each flip is expensive.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow flipping variables in unsatisfied clauses using a mix of greed and randomness on a small satisfiability example.
Step 1 of 6: Generate a random assignment
optimization-mechanismNotes
WalkSAT is a heuristic SAT solver; it can find satisfying assignments but does not prove unsatisfiability.
Sources (2)
What each reference supports for this entry.
Handbook of Satisfiability
BookReference for WalkSAT within SAT solving, including search, simplification, learning, or local-search mechanisms.
Open sourceNoise Strategies for Local Search
PaperReference for random-walk noise strategies used by WalkSAT-style local-search SAT solvers.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toCDCL
Optimization · Core
WalkSAT and CDCL solve related satisfiability problems with different assumptions and tradeoffs.
Compare with thisAlternative toDPLL
Optimization · Core
WalkSAT and DPLL solve related satisfiability problems with different assumptions and tradeoffs.
Compare with thisAlternativesPure Literal Elimination
Optimization · Core
Pure Literal Elimination and WalkSAT solve related satisfiability simplification problems with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toDPLL
WalkSAT and DPLL solve related satisfiability problems with different assumptions and tradeoffs.
Alternative toCDCL
WalkSAT and CDCL solve related satisfiability problems with different assumptions and tradeoffs.
Alternative toDavis-Putnam Algorithm
WalkSAT and Davis-Putnam Algorithm solve related satisfiability problems with different assumptions and tradeoffs.
Related Algorithms
Tags
OptimizationConstraint SolvingRandomness