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).

The on-line accompaniment to the book Introduction to Evolutionary Computing