Make delicious recipes!

Constraint Satisfaction problems


Constraint Satisfaction problems (CSPs) are problems where:
  1. There is a set of variables,
  2. Each variable has a set of values it can be assigned to and
  3. There are some constraints which must be satisfied to arrive at the solution.

For example: consider the case of finding all permutations of a string.
  1. Set of variables is the array positions where a character can be placed.
  2. Set of values for each position is the legal values it can take (example: all characters must belong to the original string).
  3. Constraint here is that the character once assigned, should not repeat.


CSPs are solved by backtracking -
  1. Choose a starting point,
  2. Assign one of the values to that variable from its admissible set,
  3. Filter out values from all other variables
  4. Repeat above for the second variable.
  5. If at any point in time, any variable is left without a possible set of values (due to filtering from above operations), then the set of values chosen already is incorrect. Backtrack one level at a time and check for other values.



Two things need to be kept in mind here.

MCV: Most constrained variable
When assigning values to variables, always choose that variable which has minimum number of values left in its set.

LCV: Least constrained value
When assigning values to a variable, always choose a value which will cause minimum constraint to the system.


The reason for MCV is that all variables must be assigned a value sooner or later.
So its best to assign a value to a variable which is most constrained so that chances of it falling into no-values-left trap are minimized.

The reason for LCV is exactly opposite that of MCV i.e. all values in a variable's set need not be analyzed to find a solution.
So its best to choose those values from the set which will allow others maximum chances of survival.



Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal