Introduction

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.

Solve a CSP

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">Color the four regions so that <b>no two touching regions share a color</b>.
    Variables = regions, domain = {Red, Green, Blue}, constraints = the shared borders.
    Run <b>Propagate</b> (arc consistency) to prune impossible colors, then <b>Solve</b>
    (backtracking) to finish — and see how many search steps propagation saved.</p>
<div class="map" id="map"></div>
<div class="domains" id="domains"></div>
<div class="status" id="status">Pick a region color, or just press Propagate / Solve.</div>
<div class="btns">
  <button id="propagate" type="button">Propagate (AC-3)</button>
  <button id="solve" type="button">Solve (backtracking)</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A constraint satisfaction problem (CSP): variables = 4 map regions, domain =
    // {R,G,B}, constraints = "adjacent regions must differ". Deciding whether a CSP
    // has any solution is NP-complete (via SAT; Cook-Levin 1971). Here we (1) run
    // arc consistency / AC-3 (Mackworth 1977) to prune values, then (2) backtracking
    // search to find a full assignment, counting steps so propagation's effect shows.
const COLORS = ['R', 'G', 'B'];
const NAMES = { R: 'Red', G: 'Green', B: 'Blue' };
const VARS = ['A', 'B', 'C', 'D'];
// Adjacency: A-B, A-C, B-C, B-D, C-D  (A and D do NOT touch).
const EDGES = [['A','B'],['A','C'],['B','C'],['B','D'],['C','D']];
const neighbors = v => EDGES.filter(e => e.includes(v)).map(e => e[0] === v ? e[1] : e[0]);

let domains, assigned;
function init() {
  domains = {}; assigned = {};
  VARS.forEach(v => { domains[v] = COLORS.slice(); assigned[v] = null; });
}
init();

// AC-3: for each arc (X,Y), drop any value of X that no value of Y can satisfy.
    // Constraint here is "different color", so X-value x is unsupported only when Y's
    // domain is exactly {x}. Returns false if some domain becomes empty (no solution).
function arcConsistency() {
  const queue = [];
  EDGES.forEach(([x, y]) => { queue.push([x, y]); queue.push([y, x]); });
  let removed = 0;
  while (queue.length) {
    const [x, y] = queue.shift();
    let changed = false;
    domains[x] = domains[x].filter(vx => {
      const supported = domains[y].some(vy => vy !== vx); // exists a different color
      if (!supported) { changed = true; removed++; }
      return supported;
    });
    if (domains[x].length === 0) return { ok: false, removed };
    if (changed) neighbors(x).forEach(n => { if (n !== y) queue.push([n, x]); });
  }
  return { ok: true, removed };
}

// Backtracking search over the (possibly pruned) domains. Counts assignments tried.
function backtrack() {
  let steps = 0;
  const result = {};
  function rec(i) {
    if (i === VARS.length) return true;
    const v = VARS[i];
    for (const c of domains[v]) {
      steps++;
      const clash = neighbors(v).some(n => result[n] === c);
      if (clash) continue;
      result[v] = c;
      if (rec(i + 1)) return true;
      delete result[v];
    }
    return false;
  }
  const ok = rec(0);
  return { ok, steps, result };
}

function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }
function render() {
  const m = document.getElementById('map'); m.innerHTML = '';
  VARS.forEach(v => {
    const d = document.createElement('div');
    d.className = 'region' + (assigned[v] ? ' ' + assigned[v] : '');
    d.innerHTML = '<span>' + v + '</span><small>' + (assigned[v] ? NAMES[assigned[v]] : 'click to set') + '</small>';
    d.addEventListener('click', () => {
      const cur = assigned[v];
      const next = cur === null ? 'R' : cur === 'R' ? 'G' : cur === 'G' ? 'B' : null;
      assigned[v] = next;
      domains[v] = next ? [next] : COLORS.slice();
      render();
      setStatus(fmt('Region %v%%v2%. Press Propagate or Solve.', { v: v, v2: next ? ' set to ' + NAMES[next] : ' cleared' }), '');
    });
    m.appendChild(d);
  });
  const dd = document.getElementById('domains'); dd.innerHTML = '';
  VARS.forEach(v => {
    const sw = domains[v].map(c => '<span class="swatch sw-' + c + '"></span>').join('');
    const el = document.createElement('div'); el.className = 'dom';
    el.innerHTML = '<b>' + v + '</b>: ' + sw + ' ' + domains[v].length;
    dd.appendChild(el);
  });
}

document.getElementById('propagate').addEventListener('click', () => {
  const r = arcConsistency();
  render();
  if (!r.ok) setStatus('A domain went empty — these choices have no solution.', 'bad');
  else if (r.removed === 0) setStatus('Arc consistency removed nothing more; search still needed.', '');
  else setStatus(fmt('Arc consistency pruned %removed% value(s). Domains are smaller — now Solve.', { removed: r.removed }), 'ok');
});
document.getElementById('solve').addEventListener('click', () => {
  const r = backtrack();
  if (!r.ok) { setStatus('No coloring satisfies the constraints.', 'bad'); return; }
  VARS.forEach(v => { assigned[v] = r.result[v]; });
  render();
  setStatus(fmt('Solved in %steps% search step(s): %map%.', { steps: r.steps, map: VARS.map(v => v + '=' + r.result[v]).join(', ') }), 'ok');
  console.log('Solution', r.result, '| backtracking steps', r.steps);
});
document.getElementById('reset').addEventListener('click', () => { init(); render(); setStatus('Reset. Pick a region color, or press Propagate / Solve.', ''); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/csp/Content licensed under CC BY-NC 4.0.