Interactive study tool

Constraint Satisfaction

Practice arc consistency, search heuristics, and cycle-cutset reasoning. Work through each exercise, check it instantly, and use the explanation to close any gaps.

✓ Answers stay in this browser · no network calls

The problem

A<B<C

Each variable starts with domain {1, 2, 3}. An arc X → Y is consistent when every value in D(X) has at least one supporting value in D(Y).

1. Enforce arc consistency

After AC-3 reaches a fixed point, what are the reduced domains?

Final domains

2. Search heuristics

3. Cycle-cutset reasoning

True or false: a CSP whose constraint graph has a constant number of cycles can be solved in polynomial time by conditioning on a cycle cutset.

Your verdict