SAT solver

A SAT solver answers one deceptively simple question: given a Boolean formula — a big AND of OR-clauses over true/false variables — is there any assignment of the variables that makes the whole thing true? It is the original NP-complete problem, the one against which all hardness is measured, yet modern SAT solvers routinely crack formulas with millions of variables. In chip design they are the workhorse behind equivalence checking, bounded model checking, ATPG test generation, and even routing and timing puzzles that can be encoded as 'is this constraint satisfiable?'

The engine is CDCL — Conflict-Driven Clause Learning: guess a variable's value, propagate the forced consequences (unit propagation), and when you hit a contradiction, analyze WHY it happened, learn a new clause that forbids that mistake forever, then backjump and try again. Two ideas made it explode in power: clever activity-based branching (VSIDS) that focuses on recently-troublesome variables, and watched-literal data structures that make propagation blisteringly fast. SAT and its richer cousin SMT have quietly replaced many BDD-based flows because they scale to designs where BDDs would explode.