What does The Cliff of Stacked Rules conclude, in numbers, about “Signals on the Eve of Deadlock: Solution Counts, the Backbone and the Hazard of the Next Rule”?

Answer: Chapter 6 proves that the hazard of the next random rule depends only on the size of the backbone, and shows the backbone jumping from 6 to 23 while the campaign count falls smoothly.

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: 23

n = 30 switches, one growing rule set
rulesalphalog2 solsbackbonehazardP(deadlock in next 15)
150.5026.9400.00000.000
301.0024.3400.00000.000
451.5020.8900.00000.000
602.0017.6400.00000.000
752.5014.8900.00000.000
903.0011.1600.00000.000
1053.509.1900.00000.000
1204.007.1260.00060.009
1354.502.81230.05450.569
1505.002.81230.05450.569
1655.500.00300.12500.865
1806.00deadlock

Key formula

\[h_3=\frac{\binom{b}{3}}{\binom{n}{3}}\cdot\frac{1}{8}.\]
Show the full program
# Chapter 6. p61: warning signs while one rule set fills up
# Model: random 3-rules added one at a time to n = 30 switches. Every
# 15 rules: log2 of the exact number of solutions (counting DPLL),
# the backbone b (switches that take the same value in every
# solution), and the exact hazard that one more random 3-rule
# deadlocks the set. A new rule kills every solution only if its 3
# switches are all in the backbone and all 3 signs point the wrong
# way, so hazard = C(b, 3) / C(n, 3) / 8. Illustrative; fixed seed.
# Frozen variables: Monasson et al. 1999; clusters between 3.921 and
# 4.267: Mezard, Parisi and Zecchina 2002.

import math
import random
from collections import Counter

N, STEP = 30, 15


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 model(cls, path):
    while True:
        unit = next((c[0] for c in cls if len(c) == 1), None)
        if unit is None:
            break
        path = path + [unit]
        cls = assign(cls, unit)
        if cls is None:
            return None
    if not cls:
        return path
    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 not None:
            got = model(nxt, path + [b])
            if got is not None:
                return got
    return None


def full(path, n):
    val = {abs(x): x > 0 for x in path}
    return [val.get(v, False) for v in range(1, n + 1)]


def count(cls, free):
    if not cls:
        return 1 << free
    w = Counter(abs(x) for c in cls for x in c)
    v = max(w, key=lambda x: (w[x], -x))
    total = 0
    for b in (v, -v):
        nxt = assign(cls, b)
        if nxt is not None:
            total += count(nxt, free - 1)
    return total


def backbone(cls, n):
    s = full(model([list(c) for c in cls], []), n)
    free = [False] * n
    for v in range(n):
        if free[v]:
            continue
        flip = -(v + 1) if s[v] else v + 1
        got = model([list(c) for c in cls] + [[flip]], [])
        if got is not None:
            t = full(got, n)
            for u in range(n):
                if t[u] != s[u]:
                    free[u] = True
            free[v] = True
    return n - len([f for f in free if f])


def hazard(b, n):
    return math.comb(b, 3) / math.comb(n, 3) / 8.0


rng = random.Random(20261123)
rules = []
print("n = %d switches, one growing rule set" % N)
print("rules  alpha  log2 sols  backbone  hazard  P(deadlock in next 15)")
while True:
    for _ in range(STEP):
        vs = rng.sample(range(1, N + 1), 3)
        rules.append([v if rng.random() < 0.5 else -v for v in vs])
    k = count([list(c) for c in rules], N)
    if k == 0:
        print("%5d  %5.2f  deadlock" % (len(rules), len(rules) / N))
        break
    b = backbone(rules, N)
    h = hazard(b, N)
    print("%5d  %5.2f  %9.2f  %8d  %6.4f  %22.3f"
          % (len(rules), len(rules) / N, math.log2(k), b, h,
             1.0 - (1.0 - h) ** STEP))

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 6: Signals on the Eve of Deadlock: Solution Counts, the Backbone and the Hazard of the Next Rule. 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