SAT Solving: DPLL

import type { Tracer } from "../trace";import { clauseVariables, type Clause } from "./clauses";export type SatVerdict = "satisfiable" | "unsatisfiable";export type DecisionHeuristic = "first" | "frequent";export interface SatResult {  verdict: SatVerdict;  /** The satisfying assignment, or the empty map. */  assignment: Map<string, boolean>;  decisions: number;  propagations: number;  conflicts: number;}/** The most events a run may trace before it is cut off: the stage's fixtures stay well under it. */export const MAX_SAT_STEPS = 400;/** * The Davis-Putnam-Logemann-Loveland procedure: a backtracking search * for an assignment that satisfies every clause of a CNF. Before each * guess it propagates: a clause with every literal false but one forces * that literal true, and a clause with every literal false is a * conflict that ends the branch. Then it decides an open variable, tries * true, and on failure undoes everything since and tries false; both * failing at the top level means no assignment exists. The decision * heuristic is the first open variable or the one in most clauses. * * Time: O(2^n) in the worst case, far less with propagation on real * instances. Space: O(n + m) for n variables and m clauses. */export class DpllSolver {  private assignment = new Map<string, boolean>();  private trail: { name: string; level: number }[] = [];  private decisions = 0;  private propagations = 0;  private conflicts = 0;  private steps = 0;  constructor(    private readonly tracer?: Tracer,    private readonly heuristic: DecisionHeuristic = "first",  ) {}  solve(clauses: readonly Clause[]): SatResult {    this.assignment = new Map();    this.trail = [];    this.decisions = 0;    this.propagations = 0;    this.conflicts = 0;    this.steps = 0;    const names = clauseVariables(clauses);    const found = this.search(clauses, names, 0);    // ▸ every clause has a true literal: a model    if (found) this.emit("satisfied", { assigned: this.assignment.size, decisions: this.decisions, propagations: this.propagations, conflicts: this.conflicts });    // ▸ both values failed at the top: no model exists    else this.emit("unsatisfiable", { decisions: this.decisions, propagations: this.propagations, conflicts: this.conflicts });    return { verdict: found ? "satisfiable" : "unsatisfiable", assignment: new Map(found ? this.assignment : []), decisions: this.decisions, propagations: this.propagations, conflicts: this.conflicts };  }  /** A literal's value under the assignment so far: true, false, or undefined while its variable is open. */  private valueOf(clause: Clause, i: number): boolean | undefined {    const literal = clause[i]!;    const value = this.assignment.get(literal.name);    return value === undefined ? undefined : literal.negated ? !value : value;  }  private search(clauses: readonly Clause[], names: readonly string[], level: number): boolean {    // Propagate until nothing is forced, or a clause is falsified.    for (;;) {      let forced = false;      for (let c = 0; c < clauses.length; c++) {        const clause = clauses[c]!;        let open = -1;        let openLiteral = -1;        let openCount = 0;        let openLiterals = 0;        let satisfied = false;        for (let i = 0; i < clause.length; i++) {          const value = this.valueOf(clause, i);          if (value === true) satisfied = true;          else if (value === undefined) {            open = i;            openLiteral = i;            openCount += 1;            openLiterals += 1;          }        }        if (satisfied) continue;        if (openCount === 0) {        if (openLiterals === 0) {          this.conflicts += 1;          // ▸ a clause with every literal false: this branch is dead          this.emit("conflict", { clause: c, level, conflicts: this.conflicts });          return false;        }        if (openCount === 1) {        if (openLiterals === 1) {          const literal = clause[open]!;          const literal = clause[openLiteral]!;          this.assign(literal.name, !literal.negated, level);          this.propagations += 1;          // ▸ a clause with one literal left open forces it true          this.emit("unit-propagate", { clause: c, name: literal.name, value: !literal.negated, level, assigned: this.assignment.size });          forced = true;        }      }      if (!forced) break;    }    const satisfied = clauses.every((clause) => clause.some((_, i) => this.valueOf(clause, i) === true));    if (satisfied) return true;    const name = this.choose(clauses, names);    if (name === null) return true;    for (const value of [true, false]) {      const next = level + 1;      this.decisions += 1;      this.assign(name, value, next);      // ▸ guess a value for an open variable, true first      this.emit("decide", { name, value, level: next, retry: !value, decisions: this.decisions });      if (this.search(clauses, names, next)) return true;      this.undo(next);      // ▸ undo everything since the guess and try the other value      this.emit("backtrack", { name, level: next, tried: value, assigned: this.assignment.size });    }    return false;  }  /** The variable to decide on: the first open one, or the open one in the most unsatisfied clauses. */  private choose(clauses: readonly Clause[], names: readonly string[]): string | null {    const open = names.filter((name) => !this.assignment.has(name));    const openLiteral = names.filter((name) => !this.assignment.has(name));    if (open.length === 0) return null;    if (openLiteral.length === 0) return null;    if (this.heuristic === "first") return open[0]!;    if (this.heuristic === "first") return openLiteral[0]!;    let best = open[0]!;    let best = openLiteral[0]!;    let bestCount = -1;    for (const name of open) {    for (const name of openLiteral) {      const count = clauses.filter((clause) => !clause.some((_, i) => this.valueOf(clause, i) === true) && clause.some((literal) => literal.name === name)).length;      if (count > bestCount) {        best = name;        bestCount = count;      }    }    return best;  }  private assign(name: string, value: boolean, level: number): void {    this.assignment.set(name, value);    this.trail.push({ name, level });  }  /** Drops every assignment made at this level or deeper. */  private undo(level: number): void {    while (this.trail.length > 0 && this.trail[this.trail.length - 1]!.level >= level) {      const entry = this.trail.pop()!;      this.assignment.delete(entry.name);    }  }  private emit(tag: string, data: Record<string, unknown>): void {    this.steps += 1;    if (this.steps > MAX_SAT_STEPS) throw new RangeError(`more than ${MAX_SAT_STEPS} steps: the instance is too large for the stage`);    this.tracer?.emit(tag, data);  }}