(very) Quick overview of CSP/SAT concepts

• Constraint Satisfaction Problem (CSP)

  • Given
    • A set of discrete variables
    • Legal domains for each of the variables
    • A set of constraints on values groups of variables can take
  • Find an assignment of values to all the variables so that none of the constraints are violated

• SAT Problem = CSP with boolean variables

x,y,u,v: {A,B,C,D,E}

w: {D,E} l : {A,B}

x=A ??w?E

y=B ??u?D

u=C ??l?A

v=D ??l?B

A solution:

x=B, y=C, u=D, v=E, w=D, l=B

Previous slide

Next slide

Back to first slide

View graphic version