Is MAC another name for AC-3?

No. AC-3 is an arc-consistency algorithm. MAC is a backtracking strategy that invokes an appropriate consistency procedure after decisions.

Can MAC solve some instances without many guesses?

Yes. Propagation can force values or reveal contradictions, but the amount of remaining search depends on the instance.

Does a nonempty arc-consistent domain collection prove a solution exists?

No. Local support across individual constraints may still fail to combine into one globally consistent assignment.

AI Glossary / Graphs and symbolic AI / Intermediate

Maintaining Arc Consistency

Definition

Maintaining Arc Consistency, often abbreviated MAC, is a constraint-search strategy that restores arc consistency after each decision during backtracking. For a binary constraint, every remaining value of one variable must have a compatible supporting value in the other variable's current domain. Repeatedly removing unsupported values can expose contradictions before the solver makes further assignments.

What it means

A constraint satisfaction problem contains variables, possible values, and rules governing combinations. Search chooses values, while propagation reduces the remaining possibilities. MAC combines these activities: each search decision is followed by a consistency check that propagates its consequences through the constraint network.

The word “maintaining” matters. Running arc consistency once before search is preprocessing. MAC keeps reestablishing it as decisions narrow domains. The resulting information can help variable selection and avoid some failing branches, although arc consistency alone does not guarantee that a full solution exists.

How it works

When a variable is assigned, restrict its domain to the chosen value. Place affected directed constraint arcs on a work queue. For an arc from X to Y, remove a value of X if no remaining value of Y satisfies their constraint with it.

Whenever a domain shrinks, related arcs may need reconsideration because values elsewhere can lose their last support. Continue until the queue is empty or some domain becomes empty. The former indicates arc consistency at that point; the latter indicates failure of the current branch.

On backtracking, restore domains to the state appropriate for the earlier decision level. MAC can use AC-3 or another suitable arc-consistency algorithm. It names the search strategy, not one exclusive implementation of the propagation routine.

Three practical examples

1. A scheduling prototype propagates ordering and compatibility constraints after assigning one activity to a time slot, reducing the options of connected activities.

2. A configuration solver narrows component choices after a selection, then repeatedly checks whether the remaining choices still have compatible partners across the network.

3. A puzzle solver maintains compatible candidate values after each guess and backtracks immediately if propagation empties a domain, rather than continuing with an impossible branch.

Think of it this way

Think of adjusting a chain of appointments after moving one appointment later. A later start may push the next appointment's earliest feasible slot, which in turn affects another appointment.

The analogy captures cascading consequences, but arc consistency does not necessarily construct one joint schedule. It checks that individual values have local support across each constraint. The supporting choices for different constraints may not all fit together into a single global assignment.

Worked example

Consider three variables with domains X = {1,2,3}, Y = {2,3,4}, and Z = {3,4,5}. Require X < Y and Y < Z. Before a decision, these domains are arc-consistent: each value has support across its adjacent constraints.

Assign X = 3. Checking Y against X removes Y = 2 and Y = 3, because neither is greater than 3. Y's domain becomes {4}.

That reduction affects Z. Checking Z against Y removes Z = 3 and Z = 4, because neither is greater than 4. Z becomes {5}. The reverse checks preserve the remaining values, and the domains stabilize at X = {3}, Y = {4}, Z = {5}. This gives a complete satisfying assignment.

Forward checking from X alone would initially narrow Y but leave Z unchanged because X and Z have no direct constraint. MAC carries the consequence through Y's reduced domain.

If the solver later returns to the state before X = 3, it must restore Y and Z to their earlier domains. Otherwise, alternative choices for X would be explored under restrictions inherited incorrectly from the abandoned branch.

Illustrative case study

Fictional case: Cedar Timetables evaluates a search engine for small event programs with ordering constraints. The team adds MAC so a decision about one event can narrow time choices farther along a dependency chain.

Engineers create tests where propagation yields a full schedule, where it detects a conflict, and where it leaves several choices. They compare total runtime with a simpler forward-checking version and independently verify returned schedules. The team also checks backtracking restoration using branches that require different domain values. This fictional case reports no measured performance gain or production deployment result.

Common misconceptions and mistakes

Do not confuse arc consistency with a complete satisfiability test. Three variables with domains {1,2} and pairwise not-equal constraints are initially arc-consistent: every value has a different supporting value in each neighbor. Nevertheless, assigning three distinct values from only two choices is impossible.

Do not confuse MAC with the minimum-remaining-values heuristic. MAC filters domains; the heuristic chooses which variable to assign next. They can work together but perform different jobs.

Finally, sound propagation removes values lacking the required support, not merely values that seem inconvenient. Incorrect pruning or restoration can silently lose valid solutions.

Business use

MAC is useful when decisions generate enough cascading restrictions to justify stronger propagation. Its value depends on domain sizes, constraint structure, checking costs, and variable ordering.

Measure propagation work as well as explored search nodes. A smaller search tree can still take longer if consistency checking is expensive on that workload. Keep feasibility checking separate from optimization: MAC helps satisfy constraints, but finding the cheapest or best feasible result requires an objective and an appropriate search method. Clear failure reporting should distinguish proven branch contradictions from exhausted time or memory budgets.

Check your understanding

Why is Z reduced after assigning X = 3, even though X and Z are not directly constrained?

Answer: X's assignment reduces Y to {4}. That change removes support for Z = 3 and Z = 4 under Y < Z, so propagation continues through the chain.

Related terms

Learn next

Trace the arc queue for a small constraint chain and record every domain reduction. Then add a cycle and find an arc-consistent instance with no full solution, reinforcing the difference between local consistency and global feasibility.

Local consistency

Sources

Russell and Norvig, AIMA constraint-satisfaction chapter, arc consistency, AC-3, and maintaining consistency during search: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf

The ordered-variable trace, two-value counterexample discussion, and fictional timetable case are teaching illustrations. No constraint-solver execution or runtime result is claimed.

Previous: Main effect Next: Maintenance-free operating period