What does The Cliff of Stacked Rules conclude, in numbers, about “DPLL with the Standard Library: Unit Propagation, Branching and "Easy, Hard, Easy"”?

Answer: DPLL decides whether a rulebook has a solution by simplification, unit propagation and branching with backtracking, and the steps of unit propagation are themselves a readable account of a deadlock. p21 shows a rulebook of only eight switches whose ratio after one new rule in week 2 is just 1.375, yet seven steps of unit propagation prove deadlock, because single-switch hard requirements pin the other rules down. p22 reproduces "easy, hard, easy": the median number of dead ends climbs from 0.0 to 26.5 and falls back to 9.0. p23 shows that unit propagation cuts the work by two orders of magnitude. But where exactly is the cliff, and can a bound be computed without experiments? The next chapter answers with the expected number of solutions, the exact threshold of 2-SAT and the length of clauses.

Scope of the numbers: The rulebooks and data are illustrative; every calculation is generated by the book's programs; the book offers general business method, not legal, compliance or business-decision advice. Chapter 4 checks an illustrative rulebook of 24 switches: bare ratio 0.958, load 0.475, a median clause ratio at deadlock of only 1.292, and a minimal conflict core spanning three rule families.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.0, 26.5, 9.0

n = 50, 60 formulas per ratio; medians and 90th percentiles
alphaP(sat)guessesdead endsdead ends p90max
2.01.00024.00.00.00
3.01.00018.00.01.04
3.61.00016.01.09.948
4.00.83318.55.538.556
4.30.60022.516.046.964
4.60.30027.026.544.663
5.00.01725.026.038.944
6.00.00016.017.025.030
8.00.0009.510.514.019
10.00.0008.09.011.915
Show the full program
# Chapter 2. p22: easy-hard-easy - search effort peaks at the cliff
# Model: random 3-SAT on n = 50 switches, 60 formulas per ratio
# (illustrative), DPLL with unit propagation and a weighted branching
# rule. Effort = number of guesses (branch points) the solver opens.
# Under-constrained sets are solved almost without guessing, heavily
# over-constrained sets are refuted quickly, and the median effort
# peaks near the 50 per cent point (Mitchell et al. 1992).

import random
import statistics
from collections import Counter

N, TRIALS = 50, 60
ALPHAS = [2.0, 3.0, 3.6, 4.0, 4.3, 4.6, 5.0, 6.0, 8.0, 10.0]


def assign(cls, lit):
    out = []
    for c in cls:
        if lit in c:
            continue
        if -lit in c:
            c = [x for x in c if x != -lit]
            if not c:
                return None
        out.append(c)
    return out


def dpll(cls, st):
    while True:
        unit = next((c[0] for c in cls if len(c) == 1), None)
        if unit is None:
            break
        cls = assign(cls, unit)
        if cls is None:
            st[1] += 1
            return False
    if not cls:
        return True
    st[0] += 1
    w = Counter()
    for c in cls:
        for x in c:
            w[x] += 1 << max(0, 6 - len(c))
    lit = max(w, key=lambda x: (w[x] + w[-x], w[x], -abs(x), x))
    for b in (lit, -lit):
        nxt = assign(cls, b)
        if nxt is None:
            st[1] += 1
        elif dpll(nxt, st):
            return True
    return False


rng = random.Random(20261115)
print("n = %d, %d formulas per ratio; medians and 90th percentiles"
      % (N, TRIALS))
print("alpha  P(sat)  guesses  dead ends  dead ends p90  max")
for a in ALPHAS:
    m = round(a * N)
    efforts, dead, ok = [], [], 0
    for _ in range(TRIALS):
        f = []
        for _ in range(m):
            vs = rng.sample(range(1, N + 1), 3)
            f.append([v if rng.random() < 0.5 else -v for v in vs])
        st = [0, 0]
        if dpll(f, st):
            ok += 1
        efforts.append(st[0])
        dead.append(st[1])
    q = statistics.quantiles(dead, n=10)
    print("%5.1f  %6.3f  %7.1f  %9.1f  %13.1f  %4d"
          % (a, ok / TRIALS, statistics.median(efforts),
             statistics.median(dead), q[-1], max(dead)))

Single source and citation

Fan, Y. (2026). Boolean Satisfiability Phase Transitions: the Critical Constraint Ratio at Which Stacked Promotion, Compliance and Gate Rules Deadlock, and How to See It Coming (Version 1.0.0), Chapter 2: DPLL with the Standard Library: Unit Propagation, Branching and "Easy, Hard, Easy". 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-252 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026252,
  author    = {Fan, Yafu},
  title     = {Boolean Satisfiability Phase Transitions: the Critical Constraint Ratio at Which Stacked Promotion, Compliance and Gate Rules Deadlock, and How to See It Coming},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book