Understanding SAT by Implementing a Simple SAT Solver in Python (2014)
The practical significance of SAT is that almost all modern verification techniques are based on SAT solvers.<p>The algorithm he describes is not very interesting because it doesn't even implement unit-propagation. The idea with unit propagation is that if my current assignment has set a variable A=True and I also have a clause (~A + B) then B must be true for the instance to be satisfiable. Unit propagation is about propagating such implied constraints. If he'd implemented unit propagation along with his brute force search he'd have ended up with what is called the DPLL algorithm for SAT.<p>Modern SAT solvers are actually even smarter and have two important improvements over DPLL: (i) Conflict-Driven Clause Learning (CDCL) which introduced a very cool technique called non-chronological backtracking, and (ii) 2-literal watching which is an extremely clever data structure for efficient unit propagation. Both of these ideas are generalizable to many other versions of constraint solving (e.g. sudoko, router search, etc.) so they are well worth learning.<p>CDCL was introduced by this paper: <a href="https://dl.acm.org/citation.cfm?id=244560" rel="nofollow">https://dl.acm.org/citation.cfm?id=244560</a> while 2-literal watching is from the Chaff solver: <a href="https://www.princeton.edu/~chaff/publication/DAC2001v56.pdf" rel="nofollow">https://www.princeton.edu/~chaff/publication/DAC2001v56.pdf</a>.