a constraint satisfaction problem

Many puzzles have the same shape: you have a set of blanks to fill, each blank can hold one of a few values, and some rules say which combinations are allowed. Sudoku (81 cells, values 1-9, no repeat in a row, column, or box), map coloring (each region gets a color, neighbors must differ), and scheduling (each task gets a time slot, conflicting tasks must not overlap) are all the same kind of problem dressed up differently. That common shape is a constraint satisfaction problem.

Formally a CSP has three parts: a set of variables, a domain of allowed values for each variable, and a set of constraints, each forbidding certain combinations of values on some of the variables. A solution is an assignment of one value to every variable so that no constraint is violated. The natural brute force is complete enumeration over all assignments — if there are n variables each with d possible values, that is d^n combinations, which is exponential. But CSPs are the home turf of backtracking: assign variables one at a time, and after each assignment check the constraints that have become fully determined; if any is violated, prune and backtrack. Because a single bad assignment can rule out a huge block of completions, feasibility pruning is dramatically effective here.

CSPs matter because the framing is everywhere — N-queens, graph coloring, cryptarithmetic, type inference, and timetabling are all CSPs — and because the framing comes with a rich toolbox beyond plain backtracking: constraint propagation (deduce forced values before guessing, like pencil-marking a Sudoku), and variable- and value-ordering heuristics (assign the most-constrained variable first to fail fast). The honest truth is that the general CSP is NP-hard, so no method is fast on every instance; the heuristics make the typical, structured instances tractable, not all of them.