EP47

EP47: Counterpoint as Constraint Satisfaction

从福克斯规则到回溯搜索：对位法的约束满足模型

▶ 4:50 CombinatoricsGraph TheoryMusicology

前置知识

EP03 Bach and Graph Connectivity EP05 Turán's Theorem and Counterpoint

Overview / 概述

Renaissance composers navigated a labyrinth of roughly forty rules — covering intervals, voice crossings, leap resolutions, and cadential formulas — each time they wrote a single bar of counterpoint. Johann Joseph Fux codified these rules in his 1725 treatise Gradus ad Parnassum, creating the canonical five-species framework that has anchored counterpoint pedagogy for three centuries. What Fux described in prose, a modern computer scientist reads as a constraint satisfaction problem (CSP): variables are the note choices at each time step, domains are the sets of legal pitches, and constraints are the rule set.

This episode builds the CSP model precisely and analyzes its computational structure. The brute-force search space for forty time steps with thirty pitch candidates per step is $30^{40}$ — astronomically large. Arc consistency pruning, together with the especially tight constraints imposed by the cadential formula at the final positions, compresses the effective search space to roughly $10^{13}$ , a size that modern backtracking algorithms can navigate in seconds. Yet the episode also asks the harder question: the algorithm finds a legal solution, but Bach found a meaningful one. The gap between the two is the gap between constraint satisfaction and aesthetic understanding.

The musical thread runs through Palestrina’s characteristic soft constraints — smooth melodic motion, step-wise recovery after large leaps, avoidance of consecutive same-direction skips — none of which are hard prohibitions, but all of which define a stylistic signature. Encoding these as a penalty function transforms the CSP into a constraint optimization problem, where the objective quantifies how “Palestrina-like” a solution is. The inverse of that problem — learning the penalty weights from a corpus of genuine Palestrina counterpoint — is an open research question in computational musicology.

中文: “文艺复兴时期的作曲家，要手动满足四十条规则，才能写出一段对位法。每条旋律的音程、方向、节奏，都受到严格约束。计算机用约束满足，零点一秒就能找到合法方案——但那缺少了什么？”

Prerequisites / 前置知识

Bach Voice-Leading Networks (EP03) — graph structure of voice-leading constraints
Graph Theory and Forbidden Subgraphs (EP05) — forbidden interval pairs as forbidden subgraphs

Definitions / 定义

Definition 47.1 (Constraint Satisfaction Problem)

A constraint satisfaction problem is a triple $(X, D, C)$ where:

$X = \{x_1, x_2, \ldots, x_n\}$ is a finite set of variables,
$D = \{D_1, D_2, \ldots, D_n\}$ is a collection of domains, with $D_i$ being the set of candidate values for $x_i$ ,
$C = \{c_1, c_2, \ldots, c_m\}$ is a set of constraints, each $c_k$ being a relation on a subset of variables.

A solution is an assignment $\sigma: X \to \bigcup_i D_i$ with $\sigma(x_i) \in D_i$ for all $i$ , satisfying every constraint simultaneously.

Counterpoint instantiation (first species, 40 steps):

CSP component	Counterpoint meaning
Variable $x_t$ , $t = 1, \ldots, 40$	Note choice at time step $t$
Domain $D_t$	Legal pitches (≈ 30 candidates per step)
Constraint set $C$	Fux’s rule set (≈ 40 rules)

A solution to the CSP is a fully legal first-species counterpoint line.

Definition 47.2 (Fux Five Species)

Johann Joseph Fux (1725) organized Palestrina-style counterpoint into five species, distinguished by the rhythmic ratio between the cantus firmus and the added voice:

Species	Rhythmic ratio	Description
First	1 : 1	One note against one note (whole notes)
Second	1 : 2	Two notes per cantus note (half notes)
Third	1 : 4	Four notes per cantus note (quarter notes)
Fourth	Syncopated	Suspensions and resolutions
Fifth	Mixed	“Florid” counterpoint, all previous species

First-species hard constraints (representative selection):

Forbidden harmonic intervals: parallel perfect fifths, parallel octaves, parallel unisons
Forbidden melodic intervals: augmented or diminished intervals
Forbidden motion types: direct (hidden) fifths and octaves by similar motion
Cadential constraint: the penultimate step must approach the final note by specific interval pairs

Each forbidden pattern corresponds to a constraint on a pair of consecutive or simultaneous variable assignments. This is structurally identical to a forbidden subgraph condition in graph coloring — see

EP05

Definition 47.3 (Arc Consistency (AC-3))

A CSP is arc consistent if for every pair of variables $(x_i, x_j)$ linked by a constraint, and for every value $a \in D_i$ , there exists at least one value $b \in D_j$ such that the assignment $(x_i = a, x_j = b)$ satisfies all constraints between $x_i$ and $x_j$ .

The AC-3 algorithm enforces arc consistency by iteratively removing values from domains that have no supporting value in a neighboring domain. Each removal may trigger further propagation along the constraint graph.

In counterpoint: if the current note $x_t$ is tentatively assigned value $a$ , arc consistency checks whether there exists any legal value for $x_{t+1}$ compatible with $a$ . If not, $a$ is pruned from $D_t$ before any recursive search begins.

Definition 47.4 (Hard and Soft Constraints)

In a constraint satisfaction or optimization problem, constraints are classified by their role:

A hard constraint is a rule that every solution must satisfy. Violating it disqualifies the candidate. In counterpoint: “no parallel octaves” is a hard constraint.
A soft constraint (or preference) is a rule that good solutions should ideally satisfy, but violation is penalized rather than forbidden. Each soft constraint contributes a penalty term to an objective function.

The constraint optimization problem (COP) extends a CSP by adding a real-valued objective $f: \text{solutions} \to \mathbb{R}$ derived from soft constraint penalties:

$f(\sigma) = \sum_{k} w_k \cdot \text{pen}_k(\sigma)$

where $w_k > 0$ is the weight of the $k$ -th soft constraint and $\text{pen}_k(\sigma)$ counts how many times $\sigma$ violates it. The optimal solution minimizes $f$ subject to all hard constraints.

Palestrina soft constraints (representative):

Soft constraint	Penalty increases when…
Smooth melodic motion	Step size of consecutive intervals exceeds a third
Post-leap recovery	A large leap is not followed by stepwise motion in the opposite direction
Avoid consecutive same-direction leaps	Two or more large leaps occur in the same direction

Main Theorems / 主要定理

Theorem 47.1 (CSP Formalization of First-Species Counterpoint)

The set of legal first-species counterpoint solutions over $T$ time steps with domain size $d$ is exactly the solution set of a binary CSP $(X, D, C)$ with:

$|X| = T, \qquad |D_t| \leq d \;\text{ for all } t, \qquad |C| \leq \binom{T}{2}$

where each constraint in $C$ involves at most two consecutive variables $(x_t, x_{t+1})$ or two simultaneous ones $(x_t, y_t)$ (cantus firmus note vs. counterpoint note). The constraint graph is a path graph augmented with cantus-firmus edges — sparse and structured.

Proof.

Every Fux rule checks either: (a) the harmonic interval between the cantus firmus and the counterpoint note at the same time step — a binary constraint on

(x_t, y_t)

where

y_t

is fixed (the cantus note) — or (b) the melodic interval or motion type between consecutive counterpoint notes

x_{t-1}

and

x_t

— a binary constraint on

(x_{t-1}, x_t)

. No rule requires comparing three non-consecutive notes simultaneously, so the arity of every constraint is at most two. Because the cantus firmus is fixed, its values act as parameters rather than variables, and all constraints reduce to unary or binary relations on the counterpoint variables

x_1, \ldots, x_T

. The structure is therefore a binary CSP, and any such problem has a solution set that backtracking search with arc-consistency can systematically enumerate.

\square

Theorem 47.2 (Cadential Constraint Dominates Pruning)

In first-species counterpoint with a fixed cadential formula, the terminal constraint

c_T

reduces the effective domain of

x_{T-1}

O(1)

candidates, independent of

d

. Backward propagation of this reduction chains through preceding time steps, yielding a pruned search tree whose total node count is exponentially smaller than the naive bound

d^T

Proof.

The cadential formula in Palestrina-style counterpoint specifies that the penultimate note

x_{T-1}

must form a specific interval (typically a major sixth or minor third below the final cantus note), and

x_T

must be the octave or unison of the cantus final. Fixing

x_T

to this unique value reduces

D_T

to a single element. Arc consistency then propagates this reduction to

D_{T-1}

: any value in

D_{T-1}

that cannot form a legal melodic interval with the single allowed

x_T

value is pruned. In practice, this reduces

|D_{T-1}|

from

\sim 30

\lesssim 5

. Further propagation to

D_{T-2}

reduces it similarly. The effect decays geometrically away from the cadence, but the multiplicative reduction at each of the last several steps compounds into exponential pruning of the suffix of the search tree.

\square

Theorem 47.3 (Solution Space Cardinality Bounds)

For first-species counterpoint with $T = 40$ time steps and domain size $d \approx 30$ :

Brute-force upper bound: $30^{40} \approx 10^{59}$ total assignments.
After arc consistency and cadential propagation: effective search space $\approx 10^{13}$ (order-of-magnitude estimate, not a tight bound).
Legal solutions: many — the CSP is highly satisfiable, and the algorithm finds one in seconds.

The key insight is that many of these $10^{13}$ paths lead to distinct valid solutions, so the problem is not hard in the worst-case sense; it is the selection of a musically meaningful solution among the valid ones that is computationally uncharacterized.

Proof.

The brute-force bound is immediate: $\log_{10}(30^{40}) = 40 \log_{10} 30 \approx 40 \times 1.477 \approx 59$ .

The post-pruning estimate of $\approx 10^{13}$ follows from the narration-script’s order-of-magnitude calculation. After cadential back-propagation reduces the last several domains by a factor of $\sim 5{-}6$ each, and arc consistency prunes incompatible values at interior steps, the effective branching factor drops from 30 to roughly 10 per step. A conservative estimate gives $10^{40}$ reduced by about $10^{27}$ through constraint propagation, landing in the $10^{13}$ range. Modern backtracking solvers exploit additional look-ahead heuristics (MRV — minimum remaining values; LCV — least constraining value) to find a solution without exhausting this space. $\square$

Prop 47.1 (Forbidden Intervals as Forbidden Subgraphs)

The hard harmonic constraints of first-species counterpoint (forbidden parallel fifths, octaves, and augmented/diminished intervals) are in bijection with a set of forbidden induced subgraphs in the constraint graph of the CSP. This is the same structure analyzed in

EP05’s graph-coloring framework

Proof.

Model the CSP constraint graph as follows: nodes are (time-step, pitch) pairs; an edge connects

(t, p)

(t+1, q)

if the melodic interval

|p - q|

is legal, and to

(t, r)

(cantus note) if the harmonic interval

|p - r|

is legal. A forbidden parallel fifth at steps

t

and

t+1

corresponds to a forbidden induced pattern: two nodes

(t, p)

and

(t+1, q)

where both form a perfect fifth with the cantus and are connected by a melodic edge. This is precisely a forbidden 4-node induced subgraph in the constraint graph — the same structure that appears in graph coloring via forbidden minors.

\square

Numerical Examples / 数值示例

Brute-force vs. pruned search:

30^{40} = (3 \times 10)^{40} = 3^{40} \times 10^{40} \approx 1.2 \times 10^{19} \times 10^{40} = 1.2 \times 10^{59}

This vastly exceeds the number of atoms in the observable universe ( $\approx 10^{80}$ ) — though note it is smaller than $10^{80}$ , making brute force merely intractable rather than physically impossible. After arc-consistency propagation and cadential pruning, the script estimates the effective search space at:

\approx 10^{13}

At $10^{9}$ node evaluations per second (a conservative modern CPU estimate), exhaustive search of $10^{13}$ nodes would take roughly $10^4$ seconds ≈ 3 hours. But backtracking with forward-checking terminates as soon as one solution is found, making the typical runtime far shorter — empirically in the seconds-to-milliseconds range for well-constrained instances.

Domain reduction at the cadence:

Suppose the cantus firmus ends on C4. The cadential rule requires:

$x_{40} \in \{\text{C3, C4, C5}\}$ (octave/unison of final) — domain size reduced from 30 to 3.
$x_{39}$ must form a major sixth below or minor third above C, approaching by step — domain size reduced from 30 to approximately 4–6 pitches.

This 5-fold reduction at step 39 and 10-fold at step 40 alone prune the suffix search tree by a factor of $\sim 50$ , compounding with further interior propagation.

Soft constraint penalty example (Palestrina style):

Suppose a candidate counterpoint solution $\sigma$ contains:

3 instances of a large leap not followed by contrary stepwise motion: penalty $3 \times w_1$
2 instances of consecutive same-direction leaps: penalty $2 \times w_2$
0 augmented melodic intervals (hard constraint satisfied): no penalty

Setting $w_1 = w_2 = 1$ , the total soft penalty is $f(\sigma) = 5$ . A solution with $f(\sigma) = 0$ would satisfy all soft constraints — a fully idiomatic Palestrina line. The optimization problem seeks to minimize $f(\sigma)$ over all hard-constraint-satisfying assignments.

Musical Connection / 音乐联系

音乐联系

From Palestrina to Backtracking: The Algebra of Style

Palestrina’s counterpoint is famously described as “vocal” — flowing, singable, economical. The motion is predominantly by step (seconds), leaps are small (thirds or fourths), and when a large leap occurs the melody immediately reverses direction. These are not rules Palestrina consciously enumerated; they are the emergent signature of a stylistic tradition internalized over years of composition. Fux formalized this tradition into explicit rules, and those rules are exactly what a CSP encodes.

The gap between the CSP model and real Palestrina counterpoint is the gap between the rule set and the aesthetic intention behind the rule set. Fux’s rules are necessary conditions for Palestrina style; they are not sufficient. A CSP solver finds any legal solution — and there are vastly many. Most of them are monotonically ascending or descending lines that happen to avoid forbidden intervals but go nowhere musically. The missing ingredient is direction: a good counterpoint line has an arc, a climax, a sense of arrival.

This distinction maps precisely onto the hard/soft constraint dichotomy. Hard constraints eliminate illegal solutions; soft constraints, with appropriate weights, steer the solver toward solutions that resemble actual Palestrina. The weights $w_k$ encode aesthetic judgment — and learning those weights from a corpus of authentic Palestrina is an instance of inverse optimization (or inverse reinforcement learning in modern terminology).

The five species as complexity levels: From a CSP perspective, the five species form a complexity hierarchy. First species is purely harmonic (one constraint per time step pair). Second and third species add rhythmic constraints (subdivisions must also avoid forbidden intervals). Fourth species introduces anticipation constraints (the suspension must resolve down by step). Fifth species combines all constraint types simultaneously, yielding the densest constraint graph and the smallest effective domain at each step.

中文: “帕莱斯特里纳风格的特点：旋律流动平稳，大跳之后反向级进，避免同方向连续大跳。这些偏好不是硬约束，而是软约束——违反不是错误，但优质解应尽量遵守。”

Bach vs. the algorithm: Bach’s counterpoint, which follows a different and somewhat looser rule set than Fux’s Palestrina-species framework, exhibits a further layer of intentionality that no pure constraint model captures: motivic coherence. Bach’s inner voices often quote or invert the subject; rhythmic patterns repeat at transposed pitch levels; the texture as a whole expresses a single generative idea. None of this is a constraint in the Fux sense. It is the difference between solving a puzzle and writing a proof — both require satisfying conditions, but the proof must also be about something.

中文: “算法找到的是合法解，巴赫找到的是有灵魂的解——两者的距离，是约束满足与意义理解的距离。”

Limits and Open Questions / 局限性与开放问题

Fux’s rules are a stylistic approximation, not a specification. Fux codified Palestrina style as he understood it in 1725, introducing some rules that Palestrina himself did not consistently follow. The CSP model of “Palestrina counterpoint” is therefore a model of Fux’s model, with its own systematic biases. Any computational study must account for the gap between the historical corpus and the pedagogical codification.
Multi-voice complexity. First-species CSPs with a single counterpoint voice are polynomial in practice (the constraint graph is a path). Adding a second or third counterpoint voice introduces cross-voice constraints, densifying the constraint graph and potentially pushing the problem toward NP-hard territory. Whether $n$ -voice free counterpoint (without a cantus firmus) is polynomial-time solvable is an open question stated explicitly in the narration.
Soft constraint weights are not uniquely determined. Different weight vectors $(w_1, w_2, \ldots)$ can produce different “optimal” solutions, all of which satisfy the hard constraints. The learned weights depend on the corpus, the feature engineering (which soft constraints are included), and the optimization method. There is no canonical set of weights for “Palestrina style.”
Aesthetic quality is not decomposable. The penalty function $f(\sigma) = \sum_k w_k \cdot \text{pen}_k(\sigma)$ assumes that aesthetic quality is a sum of independent local penalties. This is almost certainly false: a large leap followed by contrary stepwise motion is good; the same leap in a different melodic context may be awkward. The penalty for violation of one soft constraint depends on the surrounding context, violating the additive independence assumption.
The search for musical meaning is not a search problem. A CSP or COP can find solutions that minimize measurable deviations from stylistic norms. But the question “why does this counterpoint phrase feel inevitable, even beautiful?” is not reducible to constraint satisfaction. This is not a limitation of the particular algorithm; it may be a fundamental limitation of the rule-based paradigm.

Conjecture (NP-Hardness of n-Voice Free Counterpoint)

For $n \geq 3$ independent voices with no fixed cantus firmus, the problem of finding a joint assignment satisfying all pairwise Fux-style constraints — or determining that no such assignment exists — is NP-complete.

Reasoning: As the number of voices grows, the constraint graph acquires $\binom{n}{2}$ cross-voice constraint edges per time step, and the joint domain per time step scales as $d^n$ . The interaction structure between voices at different steps — where a choice at step $t$ in voice $i$ constrains not only voice $i$ at step $t+1$ but also voice $j$ at step $t$ via harmony — can in principle encode 3-SAT instances. The conjecture predicts that even deciding feasibility (existence of a legal solution) is NP-complete for sufficiently large $n$ .

Falsification criterion: Exhibit a polynomial-time algorithm for 3-voice free counterpoint with all Fux hard constraints, or prove the problem lies in P. If the constraint graph’s treewidth remains bounded as $n$ grows, tractable dynamic programming would be possible — this would disprove the conjecture.

Conjecture (Learnability of Palestrina Soft Constraint Weights)

Given a corpus of $M$ authentic Palestrina counterpoint examples, the optimal soft constraint weight vector $\mathbf{w}^* = (w_1, \ldots, w_K)$ that maximizes the average score of corpus examples relative to randomly generated legal counterpoints can be recovered by inverse optimization (or maximum margin methods) with sample complexity $O(K / \varepsilon^2)$ , independent of the length $T$ of the counterpoint.

Falsification criterion: Show that the learned $\mathbf{w}^*$ on a training corpus generates counterpoints rated by expert musicians as significantly better than those from a random legal CSP solution, on a held-out evaluation corpus. If no such improvement is found across multiple weight-learning methods and corpus sizes, the conjecture is falsified.

Academic References / 参考文献

Fux, J. J. (1725). Gradus ad Parnassum. Vienna. English translation: Mann, A. (1943). The Study of Counterpoint. W. W. Norton.
Russell, S. J., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4th ed. Pearson. Chapter 6 (Constraint Satisfaction Problems).
Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99–118. — Original arc-consistency paper.
Tsang, E. (1993). Foundations of Constraint Satisfaction. Academic Press. Free PDF: https://www.essex.ac.uk/people/tsang/books/fcs.htm
Lerdahl, F., & Jackendoff, R. (1983). A Generative Theory of Tonal Music. MIT Press. — Formalization of musical grammar as rule systems.
Ebcioglu, K. (1988). An expert system for harmonizing four-part chorales. Computer Music Journal, 12(3), 43–51. — Early rule-based counterpoint generation.
Pachet, F., & Roy, P. (2001). Musical harmonization with constraints: A survey. Constraints, 6(1), 7–19.
Anders, T., & Miranda, E. R. (2011). Constraint application with higher-order programming for modeling music theories. Computer Music Journal, 35(2), 25–41.
Farbood, M., & Schöner, B. (2001). Analysis and synthesis of Palestrina-style counterpoint using Markov chains. Proceedings of the International Computer Music Conference (ICMC).
Conklin, D. (2003). Music generation from statistical models. Proceedings of the AISB 2003 Symposium on Artificial Intelligence and Creativity in the Arts and Sciences, 30–35.
Herremans, D., & Chuan, C.-H. (2017). A functional taxonomy of music generation systems. ACM Computing Surveys, 50(5), Article 69.
Pearce, M. T., & Wiggins, G. A. (2007). Evaluating cognitive models of musical composition. Proceedings of the 4th International Joint Workshop on Computational Creativity, 73–80.
Briot, J.-P., Hadjeres, G., & Pachet, F. (2020). Deep Learning Techniques for Music Generation. Springer. Chapter 2 (Rule-based and Constraint-based Methods).
Collins, T., Laney, R., Willis, A., & Garthwaite, P. H. (2016). Developing and evaluating computational models of musical style. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 30(1), 16–43.
Huang, C.-Z. A., Cooijmans, T., Roberts, A., Courville, A., & Eck, D. (2017). Counterpoint by convolution. Proceedings of the 18th International Society for Music Information Retrieval Conference (ISMIR), 211–218.