mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-21 09:33:35 +00:00
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]>
610 lines
29 KiB
HTML
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'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 > 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>"Support": 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):
|
|
"""
|
|
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
|
|
"""
|
|
# 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):
|
|
"""
|
|
Make xi arc-consistent with xj.
|
|
Remove values from Di that have no support in Dj.
|
|
"""
|
|
revised = False
|
|
constraint = constraints[(xi, xj)]
|
|
|
|
# Check each value in xi'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 = ['X', 'Y', 'Z']
|
|
domains = {
|
|
'X': {1, 2, 3},
|
|
'Y': {1, 2, 3},
|
|
'Z': {1, 2, 3}
|
|
}
|
|
|
|
constraints = {
|
|
('X', 'Y'): lambda x, y: x != y, # X ≠ Y
|
|
('Y', 'X'): lambda y, x: x != y,
|
|
('Y', 'Z'): lambda y, z: y < z, # Y < Z
|
|
('Z', 'Y'): lambda z, y: y < z,
|
|
}
|
|
|
|
is_consistent = ac3(variables, domains, constraints)
|
|
print(f"Consistent: {is_consistent}")
|
|
print(f"Domains after AC-3: {domains}")
|
|
# 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):
|
|
"""
|
|
Apply forward checking after assigning var = value.
|
|
Prunes domains of unassigned variables.
|
|
|
|
Returns:
|
|
Updated domains if consistent, None if inconsistent
|
|
"""
|
|
# 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):
|
|
"""Backtracking search with forward checking."""
|
|
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):
|
|
"""
|
|
Backtracking with Maintaining Arc Consistency.
|
|
Runs AC-3 after each assignment.
|
|
"""
|
|
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):
|
|
"""AC-3 that respects current assignments."""
|
|
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):
|
|
"""
|
|
Enforce bounds consistency for X + Y = Z.
|
|
Updates domains to be bounds-consistent.
|
|
|
|
Args:
|
|
x_domain, y_domain, z_domain: (min, max) tuples
|
|
constraint: 'add' for X + Y = Z
|
|
|
|
Returns:
|
|
Updated (x_domain, y_domain, z_domain) or None if inconsistent
|
|
"""
|
|
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 > new_x_max or new_y_min > new_y_max or new_z_min > 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, 'add')
|
|
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):
|
|
"""
|
|
Backtracking with conflict-directed backjumping.
|
|
Jumps back to source of conflict instead of immediate predecessor.
|
|
"""
|
|
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'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):
|
|
"""Return set of variables conflicting with var=value."""
|
|
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 (< 10 values):
|
|
→ Use AC-3 or MAC
|
|
|
|
Large domains (> 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'T: Propagate after every single constraint check
|
|
❌ DON'T: Use path consistency unless necessary
|
|
❌ DON'T: Forget bidirectional arcs (X→Y and Y→X)
|
|
❌ DON'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 = {'X': 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 = {
|
|
('X', 'Y'): lambda x, y: x < y
|
|
# Missing: ('Y', 'X')
|
|
}</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> |