Encoding constraints Assume: Variables Courses. Domains term-slots At least Constraints term Prerequisite→ 16.41 For pairs of courses that must be ordered AAt least term after Courses offered only during certain terms " Filter domain Term-slots not equal Limit# courses→ Use term-slots only once for all pairs of vars. term not equal Avoid time conflicts→ For course pairs offered at same or overlapping times Good News/ Bad News Good News -very general interesting classes of problems Bad News includes NP-Hard (intractable) problems13 Encoding Constraints Assume: Variables = Courses, Domains = term-slots Prerequisite ¨ must be ordered. 16.070 16.410 At least term before At least term after Limit # courses ¨ Use term-slots only once for all pairs of vars. Term-slots not equal term not equal Avoid time conflicts ¨ For course pairs offered at same or overlapping times Courses offered only during certain terms ¨ Filter domain Constraints: 14 Good News / Bad News Good News - - very general & interesting classes of problems Bad News includes NP-Hard (intractable) problems For pairs of courses that