Constraints

This is Unit Four of Artificial Intelligence: constraints. This unit changes the shape of the problem. In Unit Two an agent moved from a start toward a goal, building paths. Here nothing travels at all — there is a set of variables, a set of values each may take, and rules forbidding certain combinations. A solution is not a route but a state of affairs: an assignment where every requirement holds at once. It gets found somewhere in the space of possible assignments rather than reached by a sequence of moves. And the counting law from Unit Two applies here too, which means trying every assignment is as impossible as trying every plan. So the method is different in kind: instead of testing candidates, it deletes values that could not appear in any solution — and each deletion is a small proof rather than a guess. The unit closes on a genuinely surprising result about what makes a problem hard. By the end you will be able to do five things. One: say how a constraint problem differs in shape from a search problem. Two: say what propagation does and why its deletions are safe. Three: say why a puzzle solver does not try grids. Four: say why more rules can make solving easier. Five: say what these methods buy, and the price.

Three entries establishing the shape. Three ingredients, a solution that is a state rather than a route, and a scope declaration — the unit handles rules that make things flatly legal or illegal, and sets preferences aside for later.

The three ingredients.

AI 0181 The Constraint Problem

The variables, the values each may take, and the rules forbidding certain combinations. Nothing travels anywhere — a different picture from the start-and-goal problems of Unit Two.

What counts as a solution.

AI 0182 A Solution Is a State of Affairs

An assignment where every requirement holds simultaneously, found somewhere in the space of possible assignments. The multiplication that priced search trees prices this space too — it is equally unreachable by exhaustion.

The declared scope.

AI 0183 Hard Constraints Only, For Now

Hard rules make a combination flatly permitted or forbidden; soft ones merely prefer. This unit handles the hard kind, and preference gets its own arithmetic later — a declared scope rather than an omission.

One procedure, and it deserves its own topic because everything downstream inherits it. Turning a described situation into variables, values and rules is the step every later method depends on being right.

The translation.

AI 0184 The Festival, Modeled

Turning a situation's mess into variables, the values they can take, and the rules constraining them. Every answer produced later inherits this translation — a mistranslated rule produces confident wrong answers.

Three entries on the straightforward approach: assign one variable at a time and retreat the moment something breaks. It works, and the worked run is included specifically to expose how much of its effort is wasted.

The method.

AI 0185 Backtracking Search

Assign variables one at a time, retreating as soon as the assignment so far violates a rule. Retreat changes the most recent choice first, and the method is exhaustive.

The improvement.

AI 0186 The Early Check

Test each rule the moment all its variables have values, so a doomed branch dies as early as any rule can detect it. Note the precision — this prunes branches rather than possibilities.

Run whole.

AI 0187 Backtracking at the Festival

A complete run solving the problem, and showing work a better method will delete entirely. One doomed region was visible from a single rule alone — and the method explored it anyway.

Three entries on the different approach. Rather than testing assignments, shrink the problem by removing values that no solution could use — and the second entry is what makes that trustworthy.

The method.

AI 0188 Propagation

Shrink the sets of possible values before and during search, removing any value no solution could use. It narrows the problem and does not always finish it.

Why it is trustworthy.

AI 0189 Elimination Is Safe

Only values appearing in no solution get deleted, so every removal is a small proof and nothing legal is ever lost. The safety belongs to the deletions — a wrong rule in the model is a separate problem.

Run on the same case.

AI 0190 Propagation at the Festival

Propagation cuts twelve candidates to eight and demolishes the doomed region before any assignment is attempted. Every deletion was pure logic — no schedule tried, nothing guessed.

Three entries. An error about how puzzle solvers work, the move when deletion runs out of proofs, and a complete answer — which turns out to be three answers rather than one.

The error.

AI 0191 "It Tries Every Grid"

A puzzle solver does not try grids — nine candidates across eighty-one cells produces a number with seventy-eight digits. Its speed is the speed of ruling out, not the speed of trying.

When deletion stalls.

AI 0192 Split and Propagate

Split one variable's possibilities into cases and propagate each separately. This is case analysis rather than a guess — both branches get their own full treatment, so nothing is being assumed.

The capstone. Run to the end.

AI 0193 Finishing the Festival

Propagating and splitting to completion finds every legal arrangement — three of them, from eight surviving candidates. A complete method reports all of them, which a method that stops at the first would not.

Three entries closing the unit, and the middle one is genuinely counterintuitive. More rules make a problem harder to satisfy and can make it easier to solve — because every rule announces an impossibility the solver can act on.

Rules as fuel.

AI 0194 Constraints Are Information

To a solver, rules are what deletions run on — each one licenses removing possibilities. So more rules can ease the solving while making satisfaction harder. Those are two different axes.

The counterintuitive result.

AI 0195 "More Rules Make It Harder"

More rules can mean fewer solutions exist and less work to find one, because every rule announces an impossibility. The genuinely hard region is the middle — enough rules to kill most assignments, not enough to point at the survivors.

And the price.

AI 0196 The Modeling Price

These methods buy wholesale elimination and charge for it in modeling — a mistranslated rule eliminates the true answer with exactly the same confidence. When a solver reports that nothing is possible, check the translation before believing it.

Five things you can now do. You can say how a constraint problem differs in shape: variables, values and forbidden combinations, with a solution found as a state rather than reached as a route. You can say what propagation does and why it is safe — it removes only values appearing in no solution, so each deletion is a small proof. You can say why a puzzle solver does not try grids: the number of grids has seventy-eight digits, and the solver's speed is the speed of ruling out. You can say why more rules can make solving easier while making satisfaction harder, because every rule announces an impossibility a solver can act on. And you can say what the method costs: it charges in modeling, and a mistranslated rule eliminates the truth as confidently as a falsehood.