Constraint Satisfaction

Fill in a Sudoku. Build a school timetable so no teacher is in two rooms at once. Color a map so no two neighbors share a color. These feel like different puzzles, but they are the same problem wearing different clothes.

Strip away the theme and each one is a constraint satisfaction problem (CSP): a set of variables, a domain of values each variable may take, and a set of constraints — rules that say which combinations of values are allowed. A solution is an assignment of one value to every variable that breaks no rule.

That tiny vocabulary — variables, domains, constraints — is enough to describe an astonishing range of real tasks. It is also enough to capture problems we believe no fast algorithm can ever crack.

Here is a tiny CSP: color each region of the map so that no two touching regions share a color. The variables are the regions, the domain is the three colors, and each shared border is a constraint.

<p class="hint">{{hint}}</p>
<div class="map" id="map"></div>
<div class="domains" id="domains"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="propagate" type="button">{{btn_propagate}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.map { display: grid; grid-template-columns: repeat(2, 120px); grid-template-rows: repeat(2, 70px);
       gap: 6px; margin: .4rem 0 .8rem; }
.region { display: flex; flex-direction: column; align-items: center; justify-content: center;
          border: 2px solid #1d3557; border-radius: 10px; font-weight: 700; cursor: pointer;
          background: #eef2f6; color: #1d3557; user-select: none; transition: background .15s; }
.region small { font-weight: 600; font-size: .72rem; opacity: .8; }
.region.R { background: #e63946; color: #fff; border-color: #c92f3c; }
.region.G { background: #2a9d4a; color: #fff; border-color: #218038; }
.region.B { background: #3a6ea5; color: #fff; border-color: #2c5580; }
.domains { display: flex; flex-wrap: wrap; gap: .5rem; margin: 0 0 .6rem; font-size: .85rem; }
.domains .dom { background: #f1f4f7; border: 1px solid #d3dce4; border-radius: 6px; padding: .2rem .5rem; }
.domains .dom b { color: #1d3557; }
.swatch { display: inline-block; width: .7em; height: .7em; border-radius: 2px; margin: 0 1px -1px; }
.sw-R { background: #e63946; } .sw-G { background: #2a9d4a; } .sw-B { background: #3a6ea5; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Propagate to run arc consistency: it walks the borders and erases any color from a region that has no compatible choice left in a neighbor. Watch domains shrink before a single full guess is made. Then press Solve to let backtracking search the rest — the step counter shows how much work propagation saved. The same machinery solves Sudoku, where "propagation" is exactly the pencil-mark elimination you already do by hand.

How hard is constraint satisfaction? It depends on what you ask.

• Checking a finished assignment is trivial: walk every constraint once and confirm none is broken. That puts the decision problem squarely in NP.
• The general CSP is NP-complete. Asking "does this CSP have any solution?" is as hard as any problem in NP. The clean way to see it: Boolean SAT is a CSP (variables true/false, clauses as constraints), and SAT was the first problem proven NP-complete by Stephen Cook and Leonid Levin in 1971. Conversely any CSP encodes into SAT — so the two rise and fall together.
• Backtracking assigns variables one at a time and backs up when a constraint fails. In the worst case it still explores an exponential tree of dᵛ assignments (d values, v variables).
• Arc consistency tames, it does not solve. Alan Mackworth's AC-3 algorithm (1977) repeatedly prunes any value that no neighbor can match. It runs in polynomial time and often collapses the search dramatically — but it can finish with non-empty domains and still no global solution. Propagation is a powerful filter, not a polynomial-time oracle.

So the status is settled and stark: deciding solvability of a general CSP is NP-complete, and unless P vs NP is resolved in P's favor, no algorithm beats exponential worst-case time. Propagation just makes the typical case bearable.

Once you can say "variables, domains, constraints," you start seeing CSPs everywhere:

• Scheduling and timetabling: assign classes to rooms and slots so nothing collides — a CSP whose close cousin is graph coloring.
• Configuration: car options, software builds and product bundles that must respect compatibility rules.
• Compilers: register allocation maps variables to a limited set of CPU registers — literally a coloring CSP.
• Logistics and planning: crew rostering, frequency assignment for radios, and layout problems all reduce to satisfying many local rules at once.
• Puzzle engines: the Sudoku and nonogram generators on your phone run constraint propagation under the hood.

Constraint programming languages (MiniZinc, OR-Tools, Gecode) let engineers state the rules and hand the search to a solver — the same arc-consistency-plus-backtracking idea, scaled up. Learn the CSP frame and you have met the engine behind SAT and a thousand real schedules.

Constraint satisfaction is one of the great unifiers of computer science: variables, domains, constraints, and the simple demand that every rule hold at once. Sudoku, timetables and map coloring stop being separate puzzles and become a single question with a single, hard answer.

That answer is NP-complete. Arc consistency and backtracking make most everyday instances solvable in a blink, but the worst case still hides an exponential search — and behind it, once more, stands P vs NP. The next time a Sudoku resists every pencil mark, you are not stuck on a game. You are bumping into the limits of computation itself.