Solve a constraint problem.

Describe a timetable before searching it

A workshop has four one-hour activities: preparation A, discussion B, experiment C and demonstration D. There are three ordered time slots. Each activity must receive one slot. Some activities share a person, room or equipment, and preparation must happen before the demonstration.

A constraint satisfaction problem, or CSP, separates three ingredients. A variable is a choice still to make, such as A’s slot. Its domain is the set of allowed values, such as 3. A constraint states which combinations are acceptable, such as A and B having different slots. A complete assignment chooses a value for every variable.

This is different from the preceding lesson’s cheapest-route objective. Here we ask for any assignment that meets every active requirement. We do not rank valid timetables by convenience or cost. Finding the first feasible assignment does not make it the most desirable schedule.

Start by changing one availability checkbox. The lab allows an empty domain deliberately: if an activity has no possible slot, the stated problem is infeasible before any clever search is needed. Availability is an input requirement, not a result the solver may quietly ignore.

Read the symbols as requirements

Let A, B, C and D represent the selected slot numbers. A shared teacher gives the rule A ≠ B: “A and B must use different slots.” The preparation rule A < D means “A’s numbered slot comes before D’s.” These symbols describe the timetable, not neural-network weights.

The symbol ∈ means “is a member of.” The first expression says A must use one of its listed slots. The second relates two activities; the third uses the ordering of the periods. Renaming slots as arbitrary room IDs would invalidate that interpretation of less-than.

The lab’s three-slot workshop also requires A ≠ C, B ≠ C and C ≠ D. A candidate is A = 1, B = 2, C = 3, D = 2. Check each rule explicitly: A differs from B and C; B differs from C; C differs from D; and 1 is before 2. B and D may share slot 2 because no active rule prohibits that pair. Do not invent a global rule that all four activities need different periods.

Remove a value that has no support

Before assigning every variable, inspect what one constraint implies about the domains. Under A < D, A = 3 would require a D value greater than 3. No such value is available, so remove 3 from A’s domain. Likewise D = 1 would require an A value smaller than 1, so remove 1 from D.

A value has support on a relationship if at least one value in the other variable’s current domain can satisfy that relationship. In the reverse direction, D = 2 has support from A = 1. The same inequality must retain its original direction when checking the opposite domain: we ask whether some A is less than D, not whether D is less than A.

Press “Propagate domains only” and inspect the recorded frames. The original availability remains visible above the changing domain grid. Each deletion names the value, its neighboring domain, the rule and the number of candidate pairs inspected before concluding there was no support. This is a logical consequence of the current domains and rules, not a guessed probability that an activity will use a slot.

Constraint propagation repeats these deductions. Removing a value from one domain can remove support elsewhere. The lab uses AC-3, a queue-based algorithm that revisits affected directed relationships until no further values change or a domain becomes empty. It checks binary relationships—each involving two activities. Larger all-different, capacity and cumulative-resource constraints need their own treatment; this lab does not implement a full industrial scheduler.

Local consistency is not a solution

Load the two-slot conflict. A, B and C each allow 2, with A ≠ B, A ≠ C and B ≠ C. D is not involved in these three rules. Each individual value has support on each pair: if A is 1, B can be 2; if A is 2, B can be 1. The same reasoning works separately on the other pairs. AC-3 removes nothing.

Nevertheless, no joint assignment works. If A is 1, both B and C must be 2, contradicting B ≠ C. If A is 2, both must be 1, causing the same conflict. Three mutually conflicting activities need at least three different slots. Pairwise support was insufficient to establish global feasibility.

The independent enumerator can confirm this result by checking every complete tuple. With three values for each of four variables there are at most 3 × 3 × 3 × 3 = 81 tuples. In the two-slot fixture there are 2⁴ = 16. Search never receives the enumerator’s solutions; the enumeration is a separate reference for this tiny problem.

Make a choice, propagate, then backtrack if necessary

When propagation cannot settle the problem, search can make a tentative assignment. The lab chooses variables in fixed order A, B, C, D and tries increasing slot numbers. Both comparison methods use that same order so we can isolate propagation’s effect.

In the two-slot conflict, try A = 1. Propagation removes 1 from B and C. They are now both forced to 2, which violates their different-slot rule. One of their domains becomes empty. This rules out the branch that assumed A = 1.

Backtracking restores the domains from before that choice. The solver may then try A = 2. It must not carry forward B/C deletions whose justification depended on A = 1. The trace explicitly shows restoration before another attempt. If all permitted branches fail, the original finite problem is unsatisfiable; a failed single branch is not enough.

The baseline also backtracks, but it does not prune future domains. It checks constraints when both variables have assigned values and rejects a candidate when one fails. The propagation method spends extra work checking possible support pairs before all those future assignments are attempted.

Compare work honestly

Run both methods on the same domains, rules and assignment-attempt budget. Compare attempted choices, checks between already assigned variables, support-pair checks, deletions and branch restorations. Propagation can save choices while adding support checks. Equal assignment budgets do not mean equal total computation, and neither count is a wall-clock measurement.

The implementation computes a bounded trace immediately when requested; manual stepping only displays recorded frames. Counters therefore describe the entire computed run, not the amount revealed so far. Nothing animates automatically or continues in the background. The four-variable bound keeps required work small enough for direct CPU execution.

If the attempt budget stops a run with values still untried, feasibility remains unresolved by that run. Exhaustively ruling out all branches is a different result. An independent oracle may reveal the answer anyway, but its work is outside the solver’s budget and must not be attributed to the unfinished search.

Verify the candidate and the specification

The candidate checker reads the original availability and each explicit active rule. It does not trust a “solved” label or a pruned domain grid. You can propose an unavailable value or a timetable that violates A < D to see the exact rejection.

Even a passing candidate only satisfies the encoded problem. If someone forgot a participant’s availability, the real timetable may still be unusable. Disabling a teacher-sharing rule can make a problem feasible by changing the requirements; that is not evidence the old requirements were satisfied. Record what changed and whether the change is acceptable to the people involved.

For guided practice, explain one deletion, one branch restoration and the two-slot counterexample. For implementation practice, implement reversible domains and an AC-3 queue, then use an independently written complete-assignment checker on changed problems, including empty domains and reversed inequalities. For a decision brief, propose an availability or resource change, attach a checked timetable and state whose agreement the change needs.

Capture up to three runs and export your note before leaving. These are temporary public practice artifacts; they do not create a new project qualification or change published path completion. Human review and learner pilots remain pending.