mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +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]>
566 lines
28 KiB
HTML
566 lines
28 KiB
HTML
<!doctype html>
|
|
<html lang="en"><head>
|
|
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
|
<title>formal-backtracking-search</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-backtracking-search.md">
|
|
|
|
<link rel="icon" href="/favicon.svg">
|
|
<link rel="canonical" href="https://hanzoskills.com/formal-backtracking-search">
|
|
</head>
|
|
<!-- Reading this with a machine? Every page here is also plain markdown.
|
|
This one: https://hanzoskills.com/formal-backtracking-search.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-backtracking-search</h1><p class="lede">Implementing CSP solvers with systematic search</p><h1>Backtracking Search</h1>
|
|
<p><strong>Scope</strong>: Backtracking search for CSPs, variable ordering heuristics, value ordering, optimization <strong>Lines</strong>: ~320 <strong>Last Updated</strong>: 2025-10-18</p>
|
|
<h2>When to Use This Skill</h2>
|
|
<p>Activate this skill when:</p>
|
|
<ul><li>Implementing CSP solvers with systematic search</li><li>Finding all solutions to constraint problems</li><li>Optimizing search with variable/value ordering heuristics</li><li>Solving scheduling, assignment, or configuration problems</li><li>Building puzzle solvers requiring exhaustive search</li><li>Implementing constraint-based optimization</li><li>Understanding CSP search performance tuning</li></ul>
|
|
<h2>Core Concepts</h2>
|
|
<h3>Backtracking Framework</h3>
|
|
<p><strong>Basic algorithm</strong>: Depth-first search with constraint checking</p>
|
|
<ol><li>Select unassigned variable</li><li>Try each value in variable's domain</li><li>Check if assignment consistent with constraints</li><li>Recurse on remaining variables</li><li>Backtrack if no consistent assignment found</li></ol>
|
|
<p><strong>Completeness</strong>: Explores entire search tree</p>
|
|
<ul><li>Guaranteed to find solution if one exists</li><li>Can prove unsatisfiability by exhausting search space</li></ul>
|
|
<p><strong>Performance</strong>: Exponential worst case O(d^n)</p>
|
|
<ul><li>n variables, d domain size</li><li>Heuristics critical for practical performance</li></ul>
|
|
<h3>Variable Ordering Heuristics</h3>
|
|
<p><strong>Minimum Remaining Values (MRV)</strong>: Choose variable with fewest legal values</p>
|
|
<ul><li>"Most constrained variable" or "fail-first" heuristic</li><li>Detects failures earlier, prunes search tree</li><li>Example: Sudoku cell with only 2 candidates vs cell with 7</li></ul>
|
|
<p><strong>Degree heuristic</strong>: Tiebreaker for MRV</p>
|
|
<ul><li>Choose variable involved in most constraints with unassigned variables</li><li>Reduces branching factor in future choices</li></ul>
|
|
<p><strong>Dynamic ordering</strong>: Recompute best variable at each step</p>
|
|
<ul><li>More expensive but more effective than static ordering</li><li>Standard approach in modern CSP solvers</li></ul>
|
|
<h3>Value Ordering Heuristics</h3>
|
|
<p><strong>Least Constraining Value (LCV)</strong>: Try value leaving most choices for other variables</p>
|
|
<ul><li>Choose value that rules out fewest values in other domains</li><li>"Most likely to succeed" heuristic</li><li>Useful when finding any solution (not all solutions)</li></ul>
|
|
<p><strong>Random ordering</strong>: No heuristic</p>
|
|
<ul><li>Useful for unstructured problems</li><li>Simpler to implement</li></ul>
|
|
<hr>
|
|
<h2>Patterns</h2>
|
|
<h3>Pattern 1: Basic Backtracking Search</h3>
|
|
<pre><code class="lang-python">def backtracking_search(variables, domains, constraints):
|
|
"""
|
|
Find solution to CSP using backtracking.
|
|
|
|
Returns:
|
|
Assignment (dict) if solution found, None otherwise
|
|
"""
|
|
return backtrack({}, variables, domains, constraints)
|
|
|
|
def backtrack(assignment, variables, domains, constraints):
|
|
"""Recursive backtracking with constraint checking."""
|
|
# Base case: assignment complete
|
|
if len(assignment) == len(variables):
|
|
return assignment
|
|
|
|
# Select unassigned variable
|
|
var = select_unassigned_variable(variables, assignment)
|
|
|
|
# Try each value in domain
|
|
for value in order_domain_values(var, domains):
|
|
# Check if assignment consistent
|
|
if is_consistent(var, value, assignment, constraints):
|
|
# Add to assignment
|
|
assignment[var] = value
|
|
|
|
# Recurse
|
|
result = backtrack(assignment, variables, domains, constraints)
|
|
if result is not None:
|
|
return result
|
|
|
|
# Backtrack: remove assignment
|
|
del assignment[var]
|
|
|
|
return None # No solution found
|
|
|
|
def is_consistent(var, value, assignment, constraints):
|
|
"""Check if var=value consistent with current assignment."""
|
|
for other_var, other_value in assignment.items():
|
|
# Check constraint between var and other_var
|
|
if (var, other_var) in constraints:
|
|
constraint = constraints[(var, other_var)]
|
|
if not constraint(value, other_value):
|
|
return False
|
|
|
|
# Check reverse constraint
|
|
if (other_var, var) in constraints:
|
|
constraint = constraints[(other_var, var)]
|
|
if not constraint(other_value, value):
|
|
return False
|
|
|
|
return True</code></pre>
|
|
<p><strong>When to use</strong>:</p>
|
|
<ul><li>Simple CSP problems</li><li>Educational implementations</li><li>Baseline for comparing optimizations</li></ul>
|
|
<h3>Pattern 2: MRV (Minimum Remaining Values) Heuristic</h3>
|
|
<pre><code class="lang-python">def select_unassigned_variable_mrv(variables, assignment, domains):
|
|
"""
|
|
Select variable with MRV heuristic.
|
|
Choose variable with fewest remaining legal values.
|
|
"""
|
|
unassigned = [v for v in variables if v not in assignment]
|
|
|
|
# Count remaining values for each variable
|
|
def count_values(var):
|
|
# If using domain reduction, count current domain size
|
|
return len(domains[var])
|
|
|
|
# Choose variable with minimum remaining values
|
|
mrv_var = min(unassigned, key=count_values)
|
|
|
|
return mrv_var
|
|
|
|
def select_unassigned_variable_mrv_degree(
|
|
variables, assignment, domains, constraints
|
|
):
|
|
"""
|
|
MRV with degree heuristic as tiebreaker.
|
|
Degree = number of constraints with unassigned variables.
|
|
"""
|
|
unassigned = [v for v in variables if v not in assignment]
|
|
|
|
def mrv_degree_key(var):
|
|
# Primary: MRV (fewer values better, so positive count)
|
|
mrv = len(domains[var])
|
|
|
|
# Secondary: Degree (more constraints better, so negative count)
|
|
degree = -sum(
|
|
1 for other_var in unassigned
|
|
if other_var != var and (
|
|
(var, other_var) in constraints or
|
|
(other_var, var) in constraints
|
|
)
|
|
)
|
|
|
|
return (mrv, degree)
|
|
|
|
return min(unassigned, key=mrv_degree_key)
|
|
|
|
# Example usage
|
|
variables = ['A', 'B', 'C', 'D']
|
|
domains = {
|
|
'A': {1, 2, 3}, # 3 values
|
|
'B': {1, 2}, # 2 values (MRV chooses this)
|
|
'C': {1, 2, 3, 4}, # 4 values
|
|
'D': {1, 2, 3} # 3 values
|
|
}
|
|
assignment = {}
|
|
|
|
var = select_unassigned_variable_mrv(variables, assignment, domains)
|
|
print(var) # 'B'</code></pre>
|
|
<p><strong>Benefits</strong>:</p>
|
|
<ul><li>Prunes search tree earlier</li><li>10-100x speedup on many problems</li><li>Nearly always beneficial</li></ul>
|
|
<h3>Pattern 3: LCV (Least Constraining Value) Heuristic</h3>
|
|
<pre><code class="lang-python">def order_domain_values_lcv(var, assignment, domains, constraints):
|
|
"""
|
|
Order values using LCV heuristic.
|
|
Try value that rules out fewest choices for other variables first.
|
|
"""
|
|
def count_conflicts(value):
|
|
"""Count how many values ruled out in other domains."""
|
|
conflicts = 0
|
|
|
|
for other_var in domains:
|
|
if other_var in assignment or other_var == var:
|
|
continue # Skip assigned and self
|
|
|
|
# Count values in other_var ruled out by var=value
|
|
for other_value in domains[other_var]:
|
|
if (var, other_var) in constraints:
|
|
constraint = constraints[(var, other_var)]
|
|
if not constraint(value, other_value):
|
|
conflicts += 1
|
|
|
|
return conflicts
|
|
|
|
# Sort values by number of conflicts (ascending)
|
|
values = sorted(domains[var], key=count_conflicts)
|
|
return values
|
|
|
|
# Example
|
|
def backtrack_with_heuristics(assignment, variables, domains, constraints):
|
|
"""Backtracking with MRV and LCV."""
|
|
if len(assignment) == len(variables):
|
|
return assignment
|
|
|
|
# MRV: Select most constrained variable
|
|
var = select_unassigned_variable_mrv(variables, assignment, domains)
|
|
|
|
# LCV: Try least constraining values first
|
|
values = order_domain_values_lcv(var, assignment, domains, constraints)
|
|
|
|
for value in values:
|
|
if is_consistent(var, value, assignment, constraints):
|
|
assignment[var] = value
|
|
result = backtrack_with_heuristics(
|
|
assignment, variables, domains, constraints
|
|
)
|
|
if result is not None:
|
|
return result
|
|
del assignment[var]
|
|
|
|
return None</code></pre>
|
|
<p><strong>When to use</strong>:</p>
|
|
<ul><li>Finding single solution (not all solutions)</li><li>Domains have many values</li><li>Constraints are tight</li></ul>
|
|
<h3>Pattern 4: Backtracking with Forward Checking</h3>
|
|
<pre><code class="lang-python">def backtrack_fc(assignment, domains, variables, constraints):
|
|
"""Backtracking with forward checking (domain pruning)."""
|
|
if len(assignment) == len(variables):
|
|
return assignment
|
|
|
|
var = select_unassigned_variable_mrv(variables, assignment, domains)
|
|
|
|
for value in domains[var]:
|
|
if is_consistent(var, value, assignment, constraints):
|
|
# Save current domains
|
|
saved_domains = {v: d.copy() for v, d in domains.items()}
|
|
|
|
# Assign and forward check
|
|
assignment[var] = value
|
|
domains[var] = {value}
|
|
|
|
# Prune domains of unassigned variables
|
|
pruned = forward_check(var, value, domains, constraints, assignment)
|
|
|
|
if pruned: # No domain wipeout
|
|
result = backtrack_fc(
|
|
assignment, domains, variables, constraints
|
|
)
|
|
if result is not None:
|
|
return result
|
|
|
|
# Restore domains and backtrack
|
|
domains.update(saved_domains)
|
|
del assignment[var]
|
|
|
|
return None
|
|
|
|
def forward_check(var, value, domains, constraints, assignment):
|
|
"""
|
|
Prune domains after assigning var=value.
|
|
Returns False if any domain becomes empty.
|
|
"""
|
|
for other_var in domains:
|
|
if other_var in assignment or other_var == var:
|
|
continue
|
|
|
|
if (var, other_var) in constraints:
|
|
constraint = constraints[(var, other_var)]
|
|
|
|
# Remove inconsistent values from other_var
|
|
to_remove = []
|
|
for other_value in domains[other_var]:
|
|
if not constraint(value, other_value):
|
|
to_remove.append(other_value)
|
|
|
|
for v in to_remove:
|
|
domains[other_var].discard(v)
|
|
|
|
# Check for domain wipeout
|
|
if len(domains[other_var]) == 0:
|
|
return False
|
|
|
|
return True</code></pre>
|
|
<p><strong>Benefits</strong>:</p>
|
|
<ul><li>Detects failures earlier than plain backtracking</li><li>Reduces search tree size significantly</li><li>Standard optimization in CSP solvers</li></ul>
|
|
<h3>Pattern 5: Finding All Solutions</h3>
|
|
<pre><code class="lang-python">def find_all_solutions(variables, domains, constraints):
|
|
"""Find all solutions to CSP."""
|
|
solutions = []
|
|
|
|
def backtrack_all(assignment):
|
|
if len(assignment) == len(variables):
|
|
# Found complete assignment
|
|
solutions.append(assignment.copy())
|
|
return
|
|
|
|
var = select_unassigned_variable_mrv(variables, assignment, domains)
|
|
|
|
for value in domains[var]:
|
|
if is_consistent(var, value, assignment, constraints):
|
|
assignment[var] = value
|
|
backtrack_all(assignment) # Don't return early
|
|
del assignment[var]
|
|
|
|
backtrack_all({})
|
|
return solutions
|
|
|
|
# Example: All 4-Queens solutions
|
|
variables = list(range(4))
|
|
domains = {i: {0, 1, 2, 3} for i in range(4)}
|
|
|
|
def no_attack_constraint(col1, col2, row1, row2):
|
|
"""Queens don't attack each other."""
|
|
return (col1 != col2 and # Different columns
|
|
abs(row1 - row2) != abs(col1 - col2)) # Not diagonal
|
|
|
|
constraints = {
|
|
(i, j): (lambda c1, c2, r1=i, r2=j:
|
|
no_attack_constraint(c1, c2, r1, r2))
|
|
for i in range(4) for j in range(i + 1, 4)
|
|
}
|
|
|
|
all_solutions = find_all_solutions(variables, domains, constraints)
|
|
print(f"Found {len(all_solutions)} solutions") # 2 solutions</code></pre>
|
|
<p><strong>When to use</strong>:</p>
|
|
<ul><li>Generating all puzzle solutions</li><li>Enumerating configurations</li><li>Checking solution uniqueness</li></ul>
|
|
<hr>
|
|
<h2>Quick Reference</h2>
|
|
<h3>Heuristic Combinations</h3>
|
|
<p>| Variable Order | Value Order | Use Case | Performance | |----------------|-------------|----------|-------------| | Static | Static | Baseline | Worst | | MRV | Static | Medium problems | Good | | MRV + Degree | Static | Tight constraints | Better | | MRV | LCV | Single solution | Best | | MRV + Degree | LCV | Complex CSPs | Best |</p>
|
|
<h3>Search Enhancements</h3>
|
|
<pre><code>Technique | Overhead | Benefit | When to Use
|
|
------------------------|----------|----------------|------------------
|
|
Forward Checking | Low | Medium | Always
|
|
Maintaining Arc-3 | Medium | High | Tight constraints
|
|
Conflict Backjumping | Medium | High | Deep search trees
|
|
Symmetry Breaking | Low | Problem-dep | Symmetric problems
|
|
Randomization + Restart | Low | Problem-dep | Heavy-tailed dist</code></pre>
|
|
<h3>Implementation Tips</h3>
|
|
<pre><code>✅ DO: Use MRV heuristic (almost always helps)
|
|
✅ DO: Implement forward checking
|
|
✅ DO: Copy domains when backtracking (not references)
|
|
✅ DO: Use degree heuristic as MRV tiebreaker
|
|
❌ DON'T: Recompute static information in loops
|
|
❌ DON'T: Use LCV when finding all solutions (overhead wasted)
|
|
❌ DON'T: Forget to restore state when backtracking
|
|
❌ DON'T: Use recursion depth for very large problems (use iterative)</code></pre>
|
|
<hr>
|
|
<h2>Anti-Patterns</h2>
|
|
<p>❌ <strong>Static variable ordering</strong></p>
|
|
<pre><code class="lang-python"># Inefficient: Always tries variables in same order
|
|
for var in variables:
|
|
if var not in assignment:
|
|
return var</code></pre>
|
|
<p>✅ Use MRV to choose most constrained variable</p>
|
|
<p>❌ <strong>No domain pruning</strong></p>
|
|
<pre><code class="lang-python"># Slow: Checks all constraints at assignment time only
|
|
if is_consistent(var, value, assignment, constraints):
|
|
assignment[var] = value</code></pre>
|
|
<p>✅ Use forward checking to prune domains early</p>
|
|
<p>❌ <strong>Computing LCV for all solutions</strong></p>
|
|
<pre><code class="lang-python"># Wasteful: LCV overhead without benefit
|
|
def backtrack_all(assignment):
|
|
# ... finding all solutions
|
|
values = order_domain_values_lcv(var, ...) # Wasted work</code></pre>
|
|
<p>✅ Use LCV only when finding single solution</p>
|
|
<p>❌ <strong>Modifying shared domain objects</strong></p>
|
|
<pre><code class="lang-python"># Bug: Modifying domain affects all branches
|
|
domains[var].remove(value) # Side effect!
|
|
backtrack(assignment, domains, ...)</code></pre>
|
|
<p>✅ Copy domains before modification</p>
|
|
<p>❌ <strong>Deep recursion without iterative alternative</strong></p>
|
|
<pre><code class="lang-python"># Risk: Stack overflow on large problems
|
|
def backtrack(assignment, ...):
|
|
return backtrack(assignment, ...) # 1000+ levels</code></pre>
|
|
<p>✅ Implement iterative version or increase stack limit</p>
|
|
<hr>
|
|
<h2>Related Skills</h2>
|
|
<ul><li><code>csp-modeling.md</code> - Defining CSP problems and variables</li><li><code>constraint-propagation.md</code> - Domain reduction techniques</li><li><code>sat-solving-strategies.md</code> - Boolean constraint solving</li><li><code>optimization-algorithms.md</code> - Optimization with constraints</li><li><code>graph-algorithms.md</code> - Graph coloring and constraint graphs</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-backtracking-search.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
|
</footer>
|
|
</div></body></html> |