Files
skills/public/formal-constraint-propagation.html
zeekayandHanzo Dev 9e10c1c10e Each llms index points at the other two
hanzoskills.com/llms.txt now opens with the install line, the API
reference index and the company index, so an agent that lands on any
one of the three can find the rest.

robots.txt claimed 537 documents while llms.txt counts 920. The number
is gone from robots.txt; llms.txt derives it.

public/ is regenerated from scripts/site.py, which it had fallen
behind: the copy-prompt menu and agent bar were in the generator and
not in the committed pages. tests/site.mjs passes against the result.

Co-authored-by: Hanzo Dev <[email protected]>
2026-09-11 00:27:59 -07:00

610 lines
29 KiB
HTML

<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>formal-constraint-propagation</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="alternate" type="text/markdown" href="/formal-constraint-propagation.md">
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/formal-constraint-propagation">
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/formal-constraint-propagation.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>formal-constraint-propagation</h1><p class="lede">Pruning search space before backtracking search</p><h1>Constraint Propagation</h1>
<p><strong>Scope</strong>: Constraint propagation algorithms, arc consistency, domain reduction, inference <strong>Lines</strong>: ~340 <strong>Last Updated</strong>: 2025-10-18</p>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Pruning search space before backtracking search</li><li>Implementing CSP solvers with preprocessing</li><li>Detecting inconsistencies early in constraint problems</li><li>Reducing domains to simplify problem solving</li><li>Building efficient SAT/CSP solvers</li><li>Implementing forward checking in search</li><li>Understanding arc consistency algorithms (AC-3, AC-4)</li></ul>
<h2>Core Concepts</h2>
<h3>Consistency Levels</h3>
<p><strong>Node consistency</strong>: Unary constraints satisfied</p>
<ul><li>Each variable&#x27;s domain contains only values satisfying unary constraints</li><li>Simplest form: Remove invalid values from domains</li><li>Example: X ∈ {1, 2, 3, 4, 5}, constraint X &gt; 3 → domain {4, 5}</li><li>Achieved in O(nd) time (n variables, d domain size)</li></ul>
<p><strong>Arc consistency</strong>: Binary constraints satisfied</p>
<ul><li>For each pair (Xi, Xj) with constraint, every value in Di has support in Dj</li><li>&quot;Support&quot;: Value vj ∈ Dj that satisfies constraint with vi ∈ Di</li><li>Most common consistency level in practice</li><li>AC-3 algorithm: O(ed³) worst case (e edges, d domain size)</li></ul>
<p><strong>Path consistency</strong>: Extends arc consistency</p>
<ul><li>For any values in two variables, there exists consistent values for intermediate variables</li><li>More expensive than arc consistency</li><li>Rarely used in practice (high cost, modest benefit)</li></ul>
<p><strong>Bounds consistency</strong>: For ordered domains</p>
<ul><li>Only check bounds (min/max) instead of all values</li><li>Useful for large integer domains</li><li>Example: X + Y = 10, X ∈ [1..9], Y ∈ [1..9] → X ∈ [1..9], Y ∈ [1..9]</li><li>Much faster than full arc consistency for numerical domains</li></ul>
<h3>Propagation vs Search</h3>
<p><strong>Pure propagation</strong>: No search, only inference</p>
<ul><li>Reduces domains using constraints</li><li>May solve problem completely (if propagation is strong enough)</li><li>May leave problem partially solved (domains still have multiple values)</li></ul>
<p><strong>Propagation + Search</strong>: Hybrid approach</p>
<ul><li>Propagate to reduce domains</li><li>Search (backtracking) when propagation stops</li><li>Propagate again after each assignment</li><li>Standard approach in CSP solvers</li></ul>
<p><strong>Trade-offs</strong>:</p>
<ul><li>More propagation = less search (but higher overhead per node)</li><li>Less propagation = more search (but faster per node)</li><li>Arc consistency usually good balance</li></ul>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: AC-3 Algorithm (Arc Consistency)</h3>
<pre><code class="lang-python">from collections import deque
def ac3(variables, domains, constraints):
&quot;&quot;&quot;
AC-3 algorithm for enforcing arc consistency.
Args:
variables: List of variable names
domains: Dict mapping variable to set of values
constraints: Dict mapping (Xi, Xj) to binary constraint function
Returns:
True if consistent, False if inconsistent (no solution)
Modifies domains in place
&quot;&quot;&quot;
# Initialize queue with all arcs
queue = deque()
for (xi, xj) in constraints:
queue.append((xi, xj))
while queue:
(xi, xj) = queue.popleft()
if revise(xi, xj, domains, constraints):
# Domain of xi was revised
if len(domains[xi]) == 0:
return False # Inconsistent (no solution)
# Add arcs (xk, xi) for all xk ≠ xi, xj
for xk in variables:
if xk != xi and xk != xj:
if (xk, xi) in constraints:
queue.append((xk, xi))
return True # Consistent
def revise(xi, xj, domains, constraints):
&quot;&quot;&quot;
Make xi arc-consistent with xj.
Remove values from Di that have no support in Dj.
&quot;&quot;&quot;
revised = False
constraint = constraints[(xi, xj)]
# Check each value in xi&#x27;s domain
for vi in list(domains[xi]):
# Find support: value in Dj satisfying constraint
has_support = False
for vj in domains[xj]:
if constraint(vi, vj):
has_support = True
break
if not has_support:
domains[xi].remove(vi)
revised = True
return revised
# Example usage
variables = [&#x27;X&#x27;, &#x27;Y&#x27;, &#x27;Z&#x27;]
domains = {
&#x27;X&#x27;: {1, 2, 3},
&#x27;Y&#x27;: {1, 2, 3},
&#x27;Z&#x27;: {1, 2, 3}
}
constraints = {
(&#x27;X&#x27;, &#x27;Y&#x27;): lambda x, y: x != y, # X ≠ Y
(&#x27;Y&#x27;, &#x27;X&#x27;): lambda y, x: x != y,
(&#x27;Y&#x27;, &#x27;Z&#x27;): lambda y, z: y &lt; z, # Y &lt; Z
(&#x27;Z&#x27;, &#x27;Y&#x27;): lambda z, y: y &lt; z,
}
is_consistent = ac3(variables, domains, constraints)
print(f&quot;Consistent: {is_consistent}&quot;)
print(f&quot;Domains after AC-3: {domains}&quot;)
# Output: X: {1,2,3}, Y: {1,2}, Z: {2,3}</code></pre>
<p><strong>When to use</strong>:</p>
<ul><li>Before backtracking search (preprocessing)</li><li>After each assignment during search</li><li>When domains are small/medium size</li></ul>
<h3>Pattern 2: Forward Checking</h3>
<pre><code class="lang-python">def forward_check(var, value, domains, constraints, assignment):
&quot;&quot;&quot;
Apply forward checking after assigning var = value.
Prunes domains of unassigned variables.
Returns:
Updated domains if consistent, None if inconsistent
&quot;&quot;&quot;
# Create copy to allow backtracking
new_domains = {v: d.copy() for v, d in domains.items()}
new_domains[var] = {value} # Assign variable
# Check constraints with assigned variable
for other_var in domains:
if other_var in assignment or other_var == var:
continue # Skip assigned variables
if (var, other_var) in constraints:
constraint = constraints[(var, other_var)]
# Remove values from other_var with no support
for other_value in list(new_domains[other_var]):
if not constraint(value, other_value):
new_domains[other_var].remove(other_value)
# Check for domain wipeout
if len(new_domains[other_var]) == 0:
return None # Inconsistent
return new_domains
# Example in backtracking search
def backtrack_with_fc(assignment, domains, variables, constraints):
&quot;&quot;&quot;Backtracking search with forward checking.&quot;&quot;&quot;
if len(assignment) == len(variables):
return assignment # Complete assignment
# Select unassigned variable
var = select_unassigned_variable(variables, assignment, domains)
for value in domains[var]:
# Try assignment
new_assignment = assignment.copy()
new_assignment[var] = value
# Forward check
new_domains = forward_check(
var, value, domains, constraints, new_assignment
)
if new_domains is not None:
# Recursive call with pruned domains
result = backtrack_with_fc(
new_assignment, new_domains, variables, constraints
)
if result is not None:
return result
return None # No solution</code></pre>
<p><strong>Benefits</strong>:</p>
<ul><li>Cheaper than full arc consistency (only checks assigned variables)</li><li>Detects failures earlier than plain backtracking</li><li>Good performance/cost trade-off</li></ul>
<h3>Pattern 3: Maintaining Arc Consistency (MAC)</h3>
<pre><code class="lang-python">def mac(assignment, domains, variables, constraints):
&quot;&quot;&quot;
Backtracking with Maintaining Arc Consistency.
Runs AC-3 after each assignment.
&quot;&quot;&quot;
if len(assignment) == len(variables):
return assignment
var = select_unassigned_variable(variables, assignment, domains)
for value in domains[var]:
new_assignment = assignment.copy()
new_assignment[var] = value
# Create new domains with assignment
new_domains = {v: d.copy() for v, d in domains.items()}
new_domains[var] = {value}
# Run AC-3 on remaining variables
if ac3_with_assignment(
variables, new_domains, constraints, new_assignment
):
result = mac(
new_assignment, new_domains, variables, constraints
)
if result is not None:
return result
return None
def ac3_with_assignment(variables, domains, constraints, assignment):
&quot;&quot;&quot;AC-3 that respects current assignments.&quot;&quot;&quot;
queue = deque()
# Only add arcs between unassigned variables
for (xi, xj) in constraints:
if xi not in assignment and xj not in assignment:
queue.append((xi, xj))
while queue:
(xi, xj) = queue.popleft()
if xi in assignment or xj in assignment:
continue # Skip if now assigned
if revise(xi, xj, domains, constraints):
if len(domains[xi]) == 0:
return False
# Re-add affected arcs
for xk in variables:
if xk not in assignment and xk != xi and xk != xj:
if (xk, xi) in constraints:
queue.append((xk, xi))
return True</code></pre>
<p><strong>When to use</strong>:</p>
<ul><li>Problems where propagation is very effective</li><li>When search tree is large and pruning saves time</li><li>Trade-off: Higher cost per node, fewer nodes explored</li></ul>
<h3>Pattern 4: Bounds Consistency for Arithmetic</h3>
<pre><code class="lang-python">def bounds_consistency_add(x_domain, y_domain, z_domain, constraint):
&quot;&quot;&quot;
Enforce bounds consistency for X + Y = Z.
Updates domains to be bounds-consistent.
Args:
x_domain, y_domain, z_domain: (min, max) tuples
constraint: &#x27;add&#x27; for X + Y = Z
Returns:
Updated (x_domain, y_domain, z_domain) or None if inconsistent
&quot;&quot;&quot;
x_min, x_max = x_domain
y_min, y_max = y_domain
z_min, z_max = z_domain
# X bounds from Z - Y
new_x_min = max(x_min, z_min - y_max)
new_x_max = min(x_max, z_max - y_min)
# Y bounds from Z - X
new_y_min = max(y_min, z_min - x_max)
new_y_max = min(y_max, z_max - x_min)
# Z bounds from X + Y
new_z_min = max(z_min, x_min + y_min)
new_z_max = min(z_max, x_max + y_max)
# Check consistency
if new_x_min &gt; new_x_max or new_y_min &gt; new_y_max or new_z_min &gt; new_z_max:
return None # Inconsistent
return (
(new_x_min, new_x_max),
(new_y_min, new_y_max),
(new_z_min, new_z_max)
)
# Example
x_domain = (1, 10)
y_domain = (5, 15)
z_domain = (10, 20)
result = bounds_consistency_add(x_domain, y_domain, z_domain, &#x27;add&#x27;)
print(result)
# ((5, 10), (5, 15), (10, 20))
# X narrowed to [5, 10] because Z - Y_max = 20 - 15 = 5</code></pre>
<p><strong>When to use</strong>:</p>
<ul><li>Large integer domains (thousands of values)</li><li>Arithmetic constraints (add, multiply, etc.)</li><li>Linear programming relaxations</li></ul>
<h3>Pattern 5: Conflict-Directed Backjumping</h3>
<pre><code class="lang-python">def backjump(assignment, domains, variables, constraints):
&quot;&quot;&quot;
Backtracking with conflict-directed backjumping.
Jumps back to source of conflict instead of immediate predecessor.
&quot;&quot;&quot;
if len(assignment) == len(variables):
return assignment, set()
var = select_unassigned_variable(variables, assignment, domains)
for value in domains[var]:
new_assignment = assignment.copy()
new_assignment[var] = value
# Check conflicts
conflict_set = get_conflicts(var, value, assignment, constraints)
if not conflict_set:
# No conflict: recurse
result, conf = backjump(
new_assignment, domains, variables, constraints
)
if result is not None:
return result, set()
# Conflict deeper in tree
conflict_set = conf
# If conflict doesn&#x27;t involve current variable, backjump
if var not in conflict_set:
return None, conflict_set
# All values failed: return conflict set
return None, get_all_conflicts(var, assignment, constraints)
def get_conflicts(var, value, assignment, constraints):
&quot;&quot;&quot;Return set of variables conflicting with var=value.&quot;&quot;&quot;
conflicts = set()
for other_var, other_value in assignment.items():
if (var, other_var) in constraints:
constraint = constraints[(var, other_var)]
if not constraint(value, other_value):
conflicts.add(other_var)
return conflicts</code></pre>
<p><strong>Benefits</strong>:</p>
<ul><li>Avoids redundant search in branches</li><li>Particularly effective on structured problems</li><li>Can dramatically reduce search tree size</li></ul>
<hr>
<h2>Quick Reference</h2>
<h3>Consistency Algorithms Comparison</h3>
<p>| Algorithm | Time Complexity | Space | Strength | Use Case | |-----------|----------------|-------|----------|----------| | Node Consistency | O(nd) | O(nd) | Weakest | Preprocessing | | AC-3 | O(ed³) | O(e) | Medium | General CSPs | | AC-4 | O(ed²) | O(ed²) | Medium | Static CSPs | | Forward Checking | O(d²) per node | O(nd) | Weak | During search | | MAC | O(ed³) per node | O(nd) | Strong | Tight constraints | | Bounds Consistency | O(1) per propagation | O(n) | Medium | Arithmetic constraints |</p>
<h3>Propagation Strategy Selection</h3>
<pre><code>Small domains (&lt; 10 values):
→ Use AC-3 or MAC
Large domains (&gt; 1000 values):
→ Use bounds consistency
Sparse constraint graph:
→ Forward checking sufficient
Dense constraint graph:
→ MAC more effective
Real-time requirements:
→ Forward checking (lower overhead)
Offline solving:
→ MAC (fewer nodes searched)</code></pre>
<h3>Implementation Checklist</h3>
<pre><code>✅ DO: Implement revise() separately for reuse
✅ DO: Use queue for AC-3 (not recursion)
✅ DO: Copy domains when backtracking
✅ DO: Check domain wipeout immediately
❌ DON&#x27;T: Propagate after every single constraint check
❌ DON&#x27;T: Use path consistency unless necessary
❌ DON&#x27;T: Forget bidirectional arcs (X→Y and Y→X)
❌ DON&#x27;T: Re-add arcs unnecessarily to queue</code></pre>
<hr>
<h2>Anti-Patterns</h2>
<p>❌ <strong>No propagation before search</strong></p>
<pre><code class="lang-python"># Inefficient: Start search with full domains
def solve_csp(variables, domains, constraints):
return backtrack({}, domains, variables, constraints)</code></pre>
<p>✅ Run AC-3 preprocessing first</p>
<p>❌ <strong>Wrong consistency level for domain size</strong></p>
<pre><code class="lang-python"># Slow: Full arc consistency on huge domains
domains = {&#x27;X&#x27;: set(range(1, 1000000))} # 1 million values
ac3(variables, domains, constraints) # Very slow</code></pre>
<p>✅ Use bounds consistency for large integer domains</p>
<p>❌ <strong>Forgetting to add reverse arcs</strong></p>
<pre><code class="lang-python"># Bug: Only one direction
constraints = {
(&#x27;X&#x27;, &#x27;Y&#x27;): lambda x, y: x &lt; y
# Missing: (&#x27;Y&#x27;, &#x27;X&#x27;)
}</code></pre>
<p>✅ Add both (Xi, Xj) and (Xj, Xi) to constraints</p>
<p>❌ <strong>Modifying domains during iteration</strong></p>
<pre><code class="lang-python"># Bug: Modifying set while iterating
for value in domains[var]: # Set iteration
domains[var].remove(value) # Modifies set</code></pre>
<p>✅ Iterate over copy: <code>for value in list(domains[var])</code></p>
<p>❌ <strong>Expensive propagation in search</strong></p>
<pre><code class="lang-python"># Slow: Path consistency at every node
def backtrack_pc(assignment, domains, ...):
path_consistency(domains) # Overkill
# ... rest of search</code></pre>
<p>✅ Use lighter propagation (forward checking) during search</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>csp-modeling.md</code> - Defining CSP problems and constraints</li><li><code>backtracking-search.md</code> - Search algorithms using propagation</li><li><code>sat-solving-strategies.md</code> - Unit propagation in Boolean SAT</li><li><code>graph-algorithms.md</code> - Constraint graph analysis</li><li><code>optimization-algorithms.md</code> - Constraint-based optimization</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-18 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/formal-constraint-propagation.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>