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]>
745 lines
33 KiB
HTML
745 lines
33 KiB
HTML
<!doctype html>
|
|
<html lang="en"><head>
|
|
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
|
<title>formal-z3-solver-basics</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-z3-solver-basics.md">
|
|
|
|
<link rel="icon" href="/favicon.svg">
|
|
<link rel="canonical" href="https://hanzoskills.com/formal-z3-solver-basics">
|
|
</head>
|
|
<!-- Reading this with a machine? Every page here is also plain markdown.
|
|
This one: https://hanzoskills.com/formal-z3-solver-basics.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-z3-solver-basics</h1><p class="lede">Out of Scope: - Low-level C++ API (use Python bindings) - Custom theory development - Advanced proof engineering (see lean-theorem-proving.md) - SAT-only solving (see sat-solving-strategies.md)</p><h1>Z3 Solver Basics</h1>
|
|
<h2>Metadata</h2>
|
|
<ul><li><strong>Skill ID</strong>: z3-solver-basics</li><li><strong>Category</strong>: Formal Methods / SMT Solving</li><li><strong>Complexity</strong>: Intermediate</li><li><strong>Prerequisites</strong>: Python programming, basic logic, constraint satisfaction</li><li><strong>Last Updated</strong>: 2025-10-18</li></ul>
|
|
<h2>Overview</h2>
|
|
<h3>Purpose</h3>
|
|
<p>Master Z3 SMT solver for constraint solving, program verification, symbolic execution, and optimization problems using the Python API.</p>
|
|
<h3>Scope</h3>
|
|
<p><strong>In Scope</strong>:</p>
|
|
<ul><li>Z3 Python API fundamentals</li><li>SMT theory selection (QF_LIA, QF_BV, arrays, reals)</li><li>Constraint modeling and encoding</li><li>Solver modes (satisfiability, optimization)</li><li>Tactics and strategies</li><li>Unsat cores and proof extraction</li></ul>
|
|
<p><strong>Out of Scope</strong>:</p>
|
|
<ul><li>Low-level C++ API (use Python bindings)</li><li>Custom theory development</li><li>Advanced proof engineering (see lean-theorem-proving.md)</li><li>SAT-only solving (see sat-solving-strategies.md)</li></ul>
|
|
<h3>When to Use This Skill</h3>
|
|
<p><strong>Primary Use Cases</strong>:</p>
|
|
<ul><li>Solving constraint satisfaction problems</li><li>Program verification and bug finding</li><li>Test input generation</li><li>Scheduling and planning problems</li><li>Symbolic execution</li><li>Configuration validation</li></ul>
|
|
<p><strong>Choose Z3 When</strong>:</p>
|
|
<ul><li>Need theories beyond Boolean (integers, bitvectors, arrays)</li><li>Require optimization (maximize/minimize objectives)</li><li>Want integrated theory reasoning</li><li>Need unsat core extraction</li><li>Prefer Python API for rapid prototyping</li></ul>
|
|
<p><strong>Alternatives</strong>:</p>
|
|
<ul><li><strong>MiniSat/CryptoMiniSat</strong>: Pure Boolean SAT (faster for SAT-only)</li><li><strong>CVC5</strong>: Alternative SMT solver with different strengths</li><li><strong>Yices2</strong>: Fast for linear arithmetic</li><li><strong>Constraint programming</strong>: Use OR-Tools for discrete optimization</li></ul>
|
|
<h2>Core Concepts</h2>
|
|
<h3>1. SMT Theories Hierarchy</h3>
|
|
<pre><code>SMT (Satisfiability Modulo Theories)
|
|
├── QF_UF (Uninterpreted Functions)
|
|
├── QF_LIA (Linear Integer Arithmetic)
|
|
├── QF_LRA (Linear Real Arithmetic)
|
|
├── QF_BV (Bitvectors)
|
|
├── QF_AUFLIA (Arrays + UF + Linear Integer Arithmetic)
|
|
├── QF_AUFBV (Arrays + UF + Bitvectors)
|
|
└── Non-quantifier-free theories (with ∀, ∃)</code></pre>
|
|
<p><strong>Theory Selection Guide</strong>:</p>
|
|
<ul><li><strong>QF_LIA</strong>: Integer variables, linear constraints (<code>x + 2*y <= 10</code>)</li><li><strong>QF_LRA</strong>: Real-valued variables, linear constraints</li><li><strong>QF_BV</strong>: Fixed-width integers, bitwise operations</li><li><strong>Arrays</strong>: Index-value mappings, read/write operations</li><li><strong>QF_UF</strong>: Functions without interpretation (symbolic functions)</li></ul>
|
|
<h3>2. Z3 Architecture</h3>
|
|
<pre><code>User Code (Python)
|
|
↓
|
|
Z3 Python Bindings (z3-solver)
|
|
↓
|
|
Z3 Core Engine (C++)
|
|
├── Preprocessor (simplification)
|
|
├── Theory Solvers (LIA, BV, Arrays)
|
|
├── SAT Solver (CDCL core)
|
|
└── Tactic Framework (strategies)
|
|
↓
|
|
Result: sat, unsat, unknown</code></pre>
|
|
<h3>3. Solver Modes</h3>
|
|
<p><strong>Standard Mode</strong> (check):</p>
|
|
<pre><code class="lang-python">from z3 import *
|
|
|
|
s = Solver()
|
|
x = Int('x')
|
|
s.add(x > 0)
|
|
s.add(x < 10)
|
|
result = s.check() # sat, unsat, unknown
|
|
if result == sat:
|
|
print(s.model()) # Solution: x = 1 (or any value in [1, 9])</code></pre>
|
|
<p><strong>Optimization Mode</strong> (Optimize):</p>
|
|
<pre><code class="lang-python">opt = Optimize()
|
|
x = Int('x')
|
|
y = Int('y')
|
|
opt.add(x + y <= 10)
|
|
opt.add(x >= 0, y >= 0)
|
|
opt.maximize(x + 2*y) # Objective function
|
|
if opt.check() == sat:
|
|
print(opt.model()) # x=0, y=10 (maximizes objective)</code></pre>
|
|
<h3>4. Constraint Types</h3>
|
|
<p><strong>Arithmetic Constraints</strong>:</p>
|
|
<pre><code class="lang-python">x, y = Ints('x y')
|
|
constraints = [
|
|
x + y == 10, # Linear equality
|
|
2*x - 3*y <= 5, # Linear inequality
|
|
x * y == 24, # Nonlinear (switches to NRA theory)
|
|
x % 2 == 0, # Modulo (integer division)
|
|
]</code></pre>
|
|
<p><strong>Bitvector Constraints</strong>:</p>
|
|
<pre><code class="lang-python">x = BitVec('x', 32) # 32-bit bitvector
|
|
y = BitVec('y', 32)
|
|
constraints = [
|
|
x & y == 0, # Bitwise AND
|
|
x | y == 0xFFFFFFFF, # Bitwise OR (all bits set)
|
|
x >> 2 == y, # Logical right shift
|
|
SignExt(16, x) == y, # Sign extension
|
|
]</code></pre>
|
|
<p><strong>Array Constraints</strong>:</p>
|
|
<pre><code class="lang-python">A = Array('A', IntSort(), IntSort()) # Array: Int -> Int
|
|
i, j = Ints('i j')
|
|
constraints = [
|
|
Store(A, i, 10)[i] == 10, # Write then read
|
|
Select(A, i) == Select(A, j), # Same values at i, j
|
|
]</code></pre>
|
|
<h2>Implementation Patterns</h2>
|
|
<h3>Pattern 1: Basic Constraint Solving</h3>
|
|
<pre><code class="lang-python">from z3 import *
|
|
|
|
# Problem: Find x, y such that x^2 + y^2 = 25 and x > y
|
|
def solve_pythagorean():
|
|
s = Solver()
|
|
x = Int('x')
|
|
y = Int('y')
|
|
|
|
s.add(x*x + y*y == 25)
|
|
s.add(x > y)
|
|
|
|
if s.check() == sat:
|
|
m = s.model()
|
|
print(f"Solution: x={m[x]}, y={m[y]}")
|
|
# Output: x=5, y=0 or x=4, y=3 or x=3, y=-4, etc.
|
|
else:
|
|
print("No solution")
|
|
|
|
solve_pythagorean()</code></pre>
|
|
<h3>Pattern 2: Multiple Solutions with Blocking Clauses</h3>
|
|
<pre><code class="lang-python">def find_all_solutions(solver, variables, max_solutions=10):
|
|
"""Find multiple solutions by blocking previous ones"""
|
|
solutions = []
|
|
|
|
for _ in range(max_solutions):
|
|
if solver.check() != sat:
|
|
break
|
|
|
|
m = solver.model()
|
|
solution = {v: m[v] for v in variables}
|
|
solutions.append(solution)
|
|
|
|
# Block this solution
|
|
block = Or([v != m[v] for v in variables])
|
|
solver.add(block)
|
|
|
|
return solutions
|
|
|
|
# Example: Find all x, y pairs where x + y = 5, 0 <= x,y <= 5
|
|
s = Solver()
|
|
x, y = Ints('x y')
|
|
s.add(x + y == 5)
|
|
s.add(x >= 0, x <= 5)
|
|
s.add(y >= 0, y <= 5)
|
|
|
|
solutions = find_all_solutions(s, [x, y])
|
|
for sol in solutions:
|
|
print(f"x={sol[x]}, y={sol[y]}")
|
|
# Output: (0,5), (1,4), (2,3), (3,2), (4,1), (5,0)</code></pre>
|
|
<h3>Pattern 3: Optimization with Multiple Objectives</h3>
|
|
<pre><code class="lang-python">def solve_multiobjective():
|
|
"""Lexicographic optimization: prioritize objectives"""
|
|
opt = Optimize()
|
|
x, y = Ints('x y')
|
|
|
|
# Constraints
|
|
opt.add(x + y <= 10)
|
|
opt.add(x >= 0, y >= 0)
|
|
|
|
# Primary objective: maximize x
|
|
h1 = opt.maximize(x)
|
|
|
|
# Secondary objective: maximize y (given optimal x)
|
|
h2 = opt.maximize(y)
|
|
|
|
if opt.check() == sat:
|
|
print(f"x={opt.model()[x]}, y={opt.model()[y]}")
|
|
print(f"Objective 1: {opt.lower(h1)} <= x <= {opt.upper(h1)}")
|
|
print(f"Objective 2: {opt.lower(h2)} <= y <= {opt.upper(h2)}")
|
|
# Output: x=10, y=0 (maximizes x first, then y)
|
|
|
|
solve_multiobjective()</code></pre>
|
|
<h3>Pattern 4: Unsat Core Extraction</h3>
|
|
<pre><code class="lang-python">def analyze_conflicting_constraints():
|
|
"""Find minimal subset of constraints that cause unsat"""
|
|
s = Solver()
|
|
x = Int('x')
|
|
|
|
# Create named constraints
|
|
c1 = x > 10
|
|
c2 = x < 5
|
|
c3 = x >= 0
|
|
c4 = x <= 100
|
|
|
|
# Add with tracking
|
|
s.assert_and_track(c1, 'c1')
|
|
s.assert_and_track(c2, 'c2')
|
|
s.assert_and_track(c3, 'c3')
|
|
s.assert_and_track(c4, 'c4')
|
|
|
|
if s.check() == unsat:
|
|
core = s.unsat_core()
|
|
print(f"Conflicting constraints: {core}")
|
|
# Output: [c1, c2] (x > 10 and x < 5 conflict)
|
|
|
|
analyze_conflicting_constraints()</code></pre>
|
|
<h3>Pattern 5: Theory-Specific Tactics</h3>
|
|
<pre><code class="lang-python">def solve_with_tactics():
|
|
"""Use tactics for performance tuning"""
|
|
x, y = Ints('x y')
|
|
formula = And(x + y == 10, x - y == 2)
|
|
|
|
# Strategy: simplify, then solve with LIA solver
|
|
tactic = Then('simplify', 'qflia') # Quantifier-free LIA
|
|
solver = tactic.solver()
|
|
solver.add(formula)
|
|
|
|
if solver.check() == sat:
|
|
print(solver.model())
|
|
# Output: x=6, y=4
|
|
|
|
solve_with_tactics()</code></pre>
|
|
<h3>Pattern 6: Incremental Solving</h3>
|
|
<pre><code class="lang-python">def incremental_solving():
|
|
"""Efficient solving with push/pop for backtracking"""
|
|
s = Solver()
|
|
x, y = Ints('x y')
|
|
|
|
# Base constraints
|
|
s.add(x + y <= 10)
|
|
|
|
# Try scenario 1: x > 5
|
|
s.push()
|
|
s.add(x > 5)
|
|
if s.check() == sat:
|
|
print(f"Scenario 1: {s.model()}")
|
|
s.pop()
|
|
|
|
# Try scenario 2: y > 5 (independent of scenario 1)
|
|
s.push()
|
|
s.add(y > 5)
|
|
if s.check() == sat:
|
|
print(f"Scenario 2: {s.model()}")
|
|
s.pop()
|
|
|
|
incremental_solving()</code></pre>
|
|
<h3>Pattern 7: Array Reasoning</h3>
|
|
<pre><code class="lang-python">def verify_array_swap():
|
|
"""Verify swap operation using array theory"""
|
|
A = Array('A', IntSort(), IntSort())
|
|
i, j = Ints('i j')
|
|
|
|
# Swap operation
|
|
A_swap = Store(Store(A, i, Select(A, j)), j, Select(A, i))
|
|
|
|
# Verify: after swap, A[i] == old_A[j] and A[j] == old_A[i]
|
|
s = Solver()
|
|
s.add(Select(A_swap, i) != Select(A, j)) # Should be unsat
|
|
|
|
if s.check() == unsat:
|
|
print("Swap verified correct")
|
|
else:
|
|
print(f"Bug found: {s.model()}")
|
|
|
|
verify_array_swap()</code></pre>
|
|
<h3>Pattern 8: Bitvector Reasoning</h3>
|
|
<pre><code class="lang-python">def check_overflow():
|
|
"""Detect integer overflow in bitvector arithmetic"""
|
|
x = BitVec('x', 8) # 8-bit unsigned integer
|
|
y = BitVec('y', 8)
|
|
|
|
s = Solver()
|
|
s.add(x + y > 255) # Overflow condition
|
|
s.add(ULT(x + y, x)) # Result < x (overflow check)
|
|
|
|
if s.check() == sat:
|
|
m = s.model()
|
|
print(f"Overflow: {m[x]} + {m[y]} = {m.evaluate(x + y)}")
|
|
# Example: 200 + 100 = 44 (mod 256)
|
|
|
|
check_overflow()</code></pre>
|
|
<h2>Quick Reference</h2>
|
|
<h3>Installation</h3>
|
|
<pre><code class="lang-bash"># Python Z3
|
|
pip install z3-solver
|
|
|
|
# Or with uv
|
|
uv add z3-solver
|
|
|
|
# Verify
|
|
python -c "import z3; print(z3.get_version_string())"</code></pre>
|
|
<h3>Common Types</h3>
|
|
<pre><code class="lang-python"># Integer variables
|
|
x = Int('x')
|
|
x, y, z = Ints('x y z')
|
|
|
|
# Real variables
|
|
r = Real('r')
|
|
|
|
# Boolean variables
|
|
b = Bool('b')
|
|
|
|
# Bitvectors
|
|
bv = BitVec('bv', 32) # 32-bit
|
|
|
|
# Arrays
|
|
A = Array('A', IntSort(), IntSort()) # Int -> Int
|
|
B = Array('B', BitVecSort(32), IntSort()) # BitVec(32) -> Int</code></pre>
|
|
<h3>Constraint Operations</h3>
|
|
<pre><code class="lang-python"># Logical
|
|
And(c1, c2, c3)
|
|
Or(c1, c2)
|
|
Not(c)
|
|
Implies(c1, c2)
|
|
Xor(c1, c2)
|
|
|
|
# Arithmetic
|
|
x + y, x - y, x * y, x / y # Division is integer division for Int
|
|
x % y # Modulo
|
|
x ** 2 # Exponentiation (switches to nonlinear)
|
|
|
|
# Comparison
|
|
x == y, x != y
|
|
x < y, x <= y, x > y, x >= y
|
|
|
|
# Bitvector
|
|
x & y, x | y, x ^ y # Bitwise AND, OR, XOR
|
|
~x # Bitwise NOT
|
|
x << n, x >> n # Shifts
|
|
ZeroExt(n, x), SignExt(n, x) # Extension
|
|
Extract(high, low, x) # Bit extraction
|
|
|
|
# Array
|
|
Select(A, i) # Read A[i]
|
|
Store(A, i, v) # Write A[i] = v</code></pre>
|
|
<h3>Solver API</h3>
|
|
<pre><code class="lang-python">s = Solver()
|
|
s.add(constraint) # Add constraint
|
|
s.check() # Returns sat, unsat, or unknown
|
|
s.model() # Get model if sat
|
|
s.push() # Save state
|
|
s.pop() # Restore state
|
|
s.reset() # Clear all constraints
|
|
|
|
# Optimization
|
|
opt = Optimize()
|
|
opt.add(constraint)
|
|
h = opt.maximize(expr) # or minimize(expr)
|
|
opt.check()
|
|
opt.model()
|
|
opt.lower(h), opt.upper(h) # Objective bounds</code></pre>
|
|
<h3>Tactics</h3>
|
|
<pre><code class="lang-python"># Common tactics
|
|
tactics = [
|
|
'simplify', # Algebraic simplification
|
|
'solve-eqs', # Gaussian elimination
|
|
'qflia', # Quantifier-free linear integer arithmetic
|
|
'qfbv', # Quantifier-free bitvectors
|
|
'qfnra', # Quantifier-free nonlinear real arithmetic
|
|
'sat', # SAT solver
|
|
'smt', # Full SMT solver
|
|
]
|
|
|
|
# Use tactic
|
|
tactic = Then('simplify', 'qflia')
|
|
solver = tactic.solver()</code></pre>
|
|
<h3>Performance Tips</h3>
|
|
<pre><code class="lang-python"># 1. Set timeout (milliseconds)
|
|
s = Solver()
|
|
s.set('timeout', 5000) # 5 seconds
|
|
|
|
# 2. Enable parallel mode
|
|
set_param('parallel.enable', True)
|
|
|
|
# 3. Use appropriate theory
|
|
# QF_LIA faster than general arithmetic
|
|
# Use bitvectors for bounded integers
|
|
|
|
# 4. Simplify before solving
|
|
from z3 import simplify
|
|
formula = simplify(complex_formula)
|
|
s.add(formula)
|
|
|
|
# 5. Incremental solving with push/pop
|
|
s.push()
|
|
s.add(temporary_constraint)
|
|
s.check()
|
|
s.pop()</code></pre>
|
|
<h2>Anti-Patterns</h2>
|
|
<h3>Anti-Pattern 1: Over-Constraining</h3>
|
|
<p><strong>Problem</strong>: Adding redundant or conflicting constraints.</p>
|
|
<pre><code class="lang-python"># BAD: Redundant constraints slow down solver
|
|
s = Solver()
|
|
x = Int('x')
|
|
s.add(x > 0)
|
|
s.add(x > 1) # Implies x > 0 (redundant)
|
|
s.add(x >= 2) # Also redundant</code></pre>
|
|
<p><strong>Solution</strong>: Simplify constraints first.</p>
|
|
<pre><code class="lang-python"># GOOD: Minimal constraint set
|
|
s = Solver()
|
|
x = Int('x')
|
|
s.add(x >= 2) # Sufficient (implies x > 0 and x > 1)</code></pre>
|
|
<h3>Anti-Pattern 2: Wrong Theory Selection</h3>
|
|
<p><strong>Problem</strong>: Using nonlinear arithmetic when linear suffices.</p>
|
|
<pre><code class="lang-python"># BAD: Nonlinear (slower)
|
|
x, y = Reals('x y')
|
|
s = Solver()
|
|
s.add(x * y == 10) # Nonlinear</code></pre>
|
|
<p><strong>Solution</strong>: Reformulate as linear when possible.</p>
|
|
<pre><code class="lang-python"># GOOD: Linear (if y is constant)
|
|
x = Real('x')
|
|
y_value = 2.0
|
|
s = Solver()
|
|
s.add(x == 10 / y_value) # Linear</code></pre>
|
|
<h3>Anti-Pattern 3: Ignoring Solver Status</h3>
|
|
<p><strong>Problem</strong>: Accessing model without checking satisfiability.</p>
|
|
<pre><code class="lang-python"># BAD: May crash if unsat
|
|
s = Solver()
|
|
s.add(False)
|
|
m = s.model() # Error: solver is unsat</code></pre>
|
|
<p><strong>Solution</strong>: Always check status first.</p>
|
|
<pre><code class="lang-python"># GOOD: Check before model access
|
|
if s.check() == sat:
|
|
m = s.model()
|
|
else:
|
|
print("No solution exists")</code></pre>
|
|
<h3>Anti-Pattern 4: Inefficient Blocking Clauses</h3>
|
|
<p><strong>Problem</strong>: Expensive enumeration of solutions.</p>
|
|
<pre><code class="lang-python"># BAD: Blocks each variable separately (exponential clauses)
|
|
for _ in range(100):
|
|
if s.check() == sat:
|
|
m = s.model()
|
|
for v in variables:
|
|
s.add(v != m[v]) # Wrong: adds 1 clause per variable</code></pre>
|
|
<p><strong>Solution</strong>: Block entire solution at once.</p>
|
|
<pre><code class="lang-python"># GOOD: Single blocking clause per solution
|
|
for _ in range(100):
|
|
if s.check() == sat:
|
|
m = s.model()
|
|
s.add(Or([v != m[v] for v in variables])) # 1 clause</code></pre>
|
|
<h3>Anti-Pattern 5: Not Using Push/Pop</h3>
|
|
<p><strong>Problem</strong>: Recreating solver for each scenario.</p>
|
|
<pre><code class="lang-python"># BAD: Recreates solver (slow)
|
|
for scenario in scenarios:
|
|
s = Solver() # New solver each time
|
|
s.add(base_constraints)
|
|
s.add(scenario)
|
|
s.check()</code></pre>
|
|
<p><strong>Solution</strong>: Use incremental solving.</p>
|
|
<pre><code class="lang-python"># GOOD: Reuse solver with push/pop
|
|
s = Solver()
|
|
s.add(base_constraints)
|
|
for scenario in scenarios:
|
|
s.push()
|
|
s.add(scenario)
|
|
s.check()
|
|
s.pop()</code></pre>
|
|
<h2>Real-World Applications</h2>
|
|
<h3>Application 1: Sudoku Solver</h3>
|
|
<pre><code class="lang-python">def solve_sudoku(grid):
|
|
"""Solve 9x9 Sudoku using Z3"""
|
|
cells = [[Int(f"c_{i}_{j}") for j in range(9)] for i in range(9)]
|
|
|
|
s = Solver()
|
|
|
|
# Each cell in [1, 9]
|
|
for i in range(9):
|
|
for j in range(9):
|
|
s.add(And(cells[i][j] >= 1, cells[i][j] <= 9))
|
|
|
|
# Row constraints
|
|
for i in range(9):
|
|
s.add(Distinct([cells[i][j] for j in range(9)]))
|
|
|
|
# Column constraints
|
|
for j in range(9):
|
|
s.add(Distinct([cells[i][j] for i in range(9)]))
|
|
|
|
# 3x3 box constraints
|
|
for box_i in range(3):
|
|
for box_j in range(3):
|
|
box = [cells[i][j]
|
|
for i in range(box_i*3, box_i*3+3)
|
|
for j in range(box_j*3, box_j*3+3)]
|
|
s.add(Distinct(box))
|
|
|
|
# Add initial grid values
|
|
for i in range(9):
|
|
for j in range(9):
|
|
if grid[i][j] != 0:
|
|
s.add(cells[i][j] == grid[i][j])
|
|
|
|
if s.check() == sat:
|
|
m = s.model()
|
|
return [[m.evaluate(cells[i][j]).as_long() for j in range(9)]
|
|
for i in range(9)]
|
|
return None</code></pre>
|
|
<h3>Application 2: Program Verification</h3>
|
|
<pre><code class="lang-python">def verify_binary_search(arr_size=10):
|
|
"""Verify binary search finds element if present"""
|
|
A = Array('A', IntSort(), IntSort())
|
|
target = Int('target')
|
|
low, high, mid = Ints('low high mid')
|
|
|
|
s = Solver()
|
|
|
|
# Array is sorted
|
|
for i in range(arr_size - 1):
|
|
s.add(Select(A, i) <= Select(A, i+1))
|
|
|
|
# Target exists at some index
|
|
exists_idx = Int('exists_idx')
|
|
s.add(And(exists_idx >= 0, exists_idx < arr_size))
|
|
s.add(Select(A, exists_idx) == target)
|
|
|
|
# Binary search logic (simplified)
|
|
s.add(low == 0)
|
|
s.add(high == arr_size - 1)
|
|
s.add(mid == (low + high) / 2)
|
|
|
|
# After one iteration, mid should narrow search
|
|
found = Select(A, mid) == target
|
|
go_left = Select(A, mid) > target
|
|
go_right = Select(A, mid) < target
|
|
|
|
# Check: we always make progress
|
|
s.add(Not(Or(found, And(go_left, exists_idx < mid),
|
|
And(go_right, exists_idx > mid))))
|
|
|
|
if s.check() == unsat:
|
|
print("Binary search verified: always makes progress")
|
|
else:
|
|
print(f"Bug found: {s.model()}")
|
|
|
|
verify_binary_search()</code></pre>
|
|
<h2>Related Skills</h2>
|
|
<ul><li><strong>sat-solving-strategies.md</strong>: Pure Boolean SAT solving, CDCL algorithms</li><li><strong>smt-theory-applications.md</strong>: Advanced SMT applications, theory combinations</li><li><strong>constraint-propagation.md</strong>: CSP techniques, arc consistency</li><li><strong>lean-theorem-proving.md</strong>: Interactive theorem proving</li><li><strong>program-analysis.md</strong>: Static analysis, abstract interpretation</li></ul>
|
|
<h2>References</h2>
|
|
<ul><li>Z3 Tutorial: https://ericpony.github.io/z3py-tutorial/guide-examples.htm</li><li>Z3 API Docs: https://z3prover.github.io/api/html/namespacez3py.html</li><li>SMT-LIB Standard: http://smtlib.cs.uiowa.edu/</li><li>Book: "Decision Procedures" by Kroening & Strichman</li></ul>
|
|
<h2>Troubleshooting</h2>
|
|
<p><strong>Problem</strong>: Solver returns "unknown"</p>
|
|
<ul><li><strong>Cause</strong>: Nonlinear constraints, quantifiers, or timeout</li><li><strong>Fix</strong>: Simplify formula, increase timeout, or use approximations</li></ul>
|
|
<p><strong>Problem</strong>: Slow solving</p>
|
|
<ul><li><strong>Cause</strong>: Wrong theory, over-constraining, or poor variable ordering</li><li><strong>Fix</strong>: Use tactics, simplify constraints, or enable parallel mode</li></ul>
|
|
<p><strong>Problem</strong>: Unexpected model values</p>
|
|
<ul><li><strong>Cause</strong>: Under-constrained problem (multiple solutions)</li><li><strong>Fix</strong>: Add more constraints or enumerate all solutions</li></ul>
|
|
<p><strong>Problem</strong>: ImportError for z3</p>
|
|
<ul><li><strong>Cause</strong>: Not installed or wrong environment</li><li><strong>Fix</strong>: <code>pip install z3-solver</code> or <code>uv add z3-solver</code></li></ul>
|
|
<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-z3-solver-basics.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
|
</footer>
|
|
</div></body></html> |