Exercises for Chapter 13: Constraint Handling

1. Specify the eight-queens problem as a CSP.
2. Is it true that solving a COP with an EA always implies indirect constraint handling?
3. Is it true that solving a CSP with an EA never involves direct constraint handling?
4. Design an EA for solving a 3-SAT problem. In a propositional
satisfiability problem (SAT) a propositional formula is given,
and a truth assignment for its variables is sought that makes
the formula true. Without loss of generality it can be assumed
that the given formula is in conjunctive normal form
(CNF), i.e., it is a conjunction of clauses where a clause is a
disjunction of literals. In the 3-SAT version of this problem it
is also assumed that the clauses consist of exactly three
literals. In the common notation, a formula has l clauses
(L_1, \dots, L_l) and n variables (v1, …, vn).