九章の関係プログラミングにおいて、より実用的な探索には制約プログラミングを用いるとした。ここでその方法の基本的な考え方を見る。
制約プログラミング自体は、何らかの論理的な制約(constarint)を満たす解を求める技法の集合である。制約プログラミングでは解を求めるにあたって、力ずくの探索を可能な限り避けて（探索量を減らす）賢く問題を解こうとする。言語に実装されていることもあれば、ライブラリとして提供されることもある。その意味で、宣言的プログラミング、並行プログラミング、オブジェクト思考といったこれまで扱ってきたプログラミングパラダイムとはやや質的に異なる。
制約プログラミングにおいては探索を次のような戦略で行う。
- 部分的な情報を蓄えていく
- （それらを最大限活用して）局所的な演繹を行う
- 局所的演繹に行き詰まったらちょっと探索を行い（これで問題が分割され、部分的な情報が得られた）、それぞれに対して再び局所的演繹を行う
これがどういうことか、具体例で見てみよう。探索がほとんど行われないことに注目。
これは、x*y = 24と2*(x+y) = 20という式になるだろう。例を簡単にするためにx≦yという式も加えておく。これらが制約である。次にみるように、こういう制約が色々な情報を伝播していくため、「伝播子(propagater)」という。
次に、必ず必要というわけではないが、変数のありうる値の情報（基本的制約）を与えておく。これは大体において可能で、かつ問題を解くのを簡単にする。この場合、x∈{0,...,9}, y∈{0,...,9} と簡単に分かる。
これら３つの伝播子と２つの基本的制約を次のように表す（OzではX*Y=:24のようにして伝播子を表し、X::1#9のように基本的制約を表せる）。
S_1 : X*Y=:24 X+Y=:10 X=<:Y || X::1#9 Y::1#9
すぐに分かるが制約プログラミングでは各探索が計算空間にカプセル化されて行われる。上では計算空間S_1の中にXとYに関する伝播子と基本的制約がある。
ここで例えばXとYの全ての組について制約を満たすかどうかを調べれば確実に答えはでる（generate-and-test方式）が、制約プログラミングはそうしない。次のようにして求める。
伝播子X*Y=:24と基本的制約Y::1#9からXは少なくとも3より大きく、8より小さい。Yについても同様。よって、
S_1 : X*Y=:24 X+Y=:10 X=<:Y || X::3#8 Y::3#8
となる（局所的演繹）。次に伝播子X+Y=:10から、
S_1 : X*Y=:24 X+Y=:10 X=<:Y || X::3#7 Y::3#7
となる。さらに戻ってX*Y=:24から
S_1 : X*Y=:24 X+Y=:10 X=<:Y || X::4#6 Y::4#6
となる。もうどの伝播子もこれ以上情報を追加できない。ここで初めて探索が行われる。X=4とX::5#6に分岐する。探索のためにそれぞれ別の計算空間が用意される。
S_2 : X*Y=:24 X+Y=:10 X=<:Y || X=4 Y::4#6
S_3 : X*Y=:24 X+Y=:10 X=<:Y || X::5#6 Y::4#6
S_2は伝播子X*Y=:24の演繹によりY=6と出る。S_3は伝播子X*Y=:24によりX=6 Y=4を演繹するが、別の伝播子X=<:Yに反するため、失敗となる。よって、X=4 Y=6のみが解となる。
見返すと、解を求めるにあたって探索を二通りしか行わなかったことが分かる。実行は「計算空間」の中で行われ、1) 安定するまで伝播子による局所的演繹, 2) 分配して探索 の二つのフェーズを交互に行う。2) はまず計算空間の２つのコピーが作られ、候補を二つの部分に分解（上だとX=4とX::5#6）する。定式的に書けば問題PをP∧CとP∧¬Cに分けることである。
ここで抽象化される部分が二つある。一つめがPをP∧CとP∧¬Cに分けるその分け方で、「分配戦略」と言う。分け方が決まると木構造ができるが、それをどう探索するのか、ということが出てくる（「探索戦略」）。制約プログラミングでは分配戦略と探索戦略を別々に指定できる。
X::4#6といった基本的制約をこれまでのモデルと整合するように扱う。そのために、「部分値」という概念を思い出す。部分値とはまだ束縛されていないような（直感的に言えば部分的にしか情報がないような）値のことである。例えば宣言されただけの変数は部分値だし、X=person(Y)においてXの値はperson(？)という構造を持つことが分かっている部分値である。これを踏まえると、X::4#6は「4,5,6のいずれかの値である」という部分的な情報を持つ値（すなわち部分値）とみなせ、実行を進めることで正確な値が定まる、とみれる。
探索を行うということは、ある変数Xについてそれが1なのか2なのかといった別々の可能性を試すということである。宣言的モデルでは、別々の箇所でX=1とX=2が実行されるということになり、当然それは失敗となるので、そういうことはできない。つまり、ある局限した空間の中で可能性を試せる（かつそれは外から見えない）ような機構の元で行う必要がある。それが計算空間である。
最初に見たように、計算空間はいくつかの解くべき変数と、その伝播子からなる。計算空間内では、各伝播子がスレッドとして並行的に変数に情報を追加していく。それ以上演繹できなくなれば（安定状態になれば）。、外部に「N個の分配先がありますよ」といったメッセージを返す（そういう外部の問い合わせに対して）。
計算空間はそれ自体は探索しない。局所的演繹を行い安定状態に達したら指示を待つ。全体の探索を木として考えると、一つの計算空間は一つのノードにおける計算を行い、「子ノードがN個生成された」（あるいは「制約を満たし結果が出た」）といった結果を外部に返すだけである。こういう風になっているので、探索エンジンは自由にプログラムできる。例えば、深さ優先探索するのか、幅優先探索にするのか、全ての解を出すのか、最初の一個で終えるのか、など。探索エンジンは探索の分岐の際の計算空間のコピーなども行う必要がある。
分配戦略については、例えば{FD.distribute naive sol(X Y)}とすればXとYについてnaiveという戦略を選ぶ、という風に指定できる（具体的にどうプログラムするかについては本では踏み込んでいない）。
関係プログラミングにおいてchoise文の実行が計算モデル上どのようになっているかについて触れなかったが、実際はchoise文はこの制約ベース計算モデルを使った言語抽象になっている。