Constraint Satisfaction

Question 1

Constraint satisfaction formalised

Answer 1

X = {X1,X2,..Xn} = set of variables

D = {D1,D2..Dn} = set of domains specifying the values each variable can take

C = set of constraints

Question 2

What is a state

Answer 2

An assignment of values to all or some variables

Question 3

When is a state called complete

Answer 3

If it assigns all the variables

Question 4

When is a state called consistent

Answer 4

If it does not violate the constraints

Question 5

What is a solution

Answer 5

A state which is complete and consistent

Question 6

What is the solution to constraint satisfaction problems

Answer 6

A backtracking search combining:

1. A depth-first search
2. Constraint propogation

Question 7

What are the heuristics for CSP

Answer 7

Minimum remaining values
Least constraining value

Question 8

What is MRV

Answer 8

Choose the variable with the fewest legal values

Question 9

What is LCV

Answer 9

Select the value which constrains the fewest other values