Constraint Logic Programming, A First Look
A lighter chapter than the last — a first look, not an exhaustive tour — at a genuinely practical extension: constraint logic programming over finite domains, CLP(FD). It's exactly the right tool for problems shaped like puzzles — Sudoku, N-Queens, scheduling — and it previews the technique this course's own capstone will lean on.
The Problem With Plain Backtracking Search
Ordinary Prolog can solve this — between/3 generates candidate values one at a time, and =:= checks the constraint after both values are already committed to. That's fine here, but the pattern doesn't scale: for a harder problem with many variables and many constraints, this "generate first, test after" approach can waste enormous effort fully constructing candidates that were doomed from the very first choice, only discovering that on the very last check.
CLP(FD) — Constraints Applied Before Values Are Chosen
X in 1..9 declares X as a domain variable — not yet a number, but a variable whose eventual value is constrained to that range. Posting X + Y #= 10 and X #< Y immediately narrows both domains through constraint propagation, before either variable has been assigned any specific value at all — the underlying CLP(FD) solver actively removes impossible values from consideration up front, rather than waiting for backtracking to stumble onto them one by one.
#= vs. is vs. = — A Fourth Operator, Genuinely Different Again
prolog1-7 distinguished is, =, and ==. CLP(FD) adds a fourth, #=, distinct from all three: unlike is/2, which demands its right-hand side already be fully ground arithmetic or raises an error, #= can be posted between variables whose values aren't known yet — it behaves bidirectionally, immediately constraining both sides' domains relative to each other, rather than requiring one side to already be a concrete number.
is/2 fails outright with an unbound Y. #= instead immediately derives a constrained domain for X from whatever domain Y already has — real, useful information, produced before any concrete value has been chosen for either variable.
label/1 — Forcing Concrete Values
A domain variable stays exactly that — a range of still-possible values, narrowed by propagation — until something forces the search to actually commit to specific numbers. label(Vars) does that: it backtracks through concrete values for each variable in Vars, but only within whatever each domain has already been narrowed down to by constraint propagation, not the original full range.
| When constraints apply | Values required | |
|---|---|---|
| Plain Prolog (is/2, =:=) | only after values are fully instantiated | ground numbers on both sides, or an error |
| CLP(FD) (in, #=, #<, ...) | immediately, propagating across domains before any value is chosen | none — works over still-unbound domain variables |
prolog2-8) leans directly on this chapter's in/#=/label pattern for exactly that reason.
is/2 or real/floating-point arithmetic. And forgetting to load library(clpfd), or forgetting to call label/1 at the end of a query, is a genuinely common beginner mistake — without label, the query reports the narrowed domains rather than concrete numbers, which can look like an answer while not actually being one.
Coding Challenges
Load library(clpfd), declare three domain variables X, Y, Z each in 1..5, post the constraint X + Y + Z #= 9, and use label/1 to find all combinations satisfying it.
📄 View solutionWrite a query using #= where one variable's domain is derived from another's before either is labeled (similar to the chapter's X #= Y + 1 example), show the resulting narrowed domains, and explain in a comment why the equivalent is/2 version would raise an error at that point.
📄 View solutionWrite a short comment explaining what a query like X in 1..9, Y in 1..9, X + Y #= 10 actually reports if label([X, Y]) is left off the end, and why that result isn't yet a usable concrete answer.
📄 View solutionChapter 7 Quick Reference
- :- use_module(library(clpfd)). loads CLP(FD) support
- X in Low..High declares a finite-domain variable, not yet a concrete number
- #=, #<, #>, ... post constraints that propagate across domains immediately, before any value is chosen
- #= differs from is/2 by working over unbound variables — is/2 demands ground arithmetic or errors
- label(Vars) forces concrete values, searching only within each variable's already-narrowed domain
- CLP(FD) is finite-domain integers specifically — not a general is/2 replacement
- The natural fit for genuine constraint-satisfaction puzzles — N-Queens, Sudoku, scheduling — and the technique this course's own capstone builds on