## Constraint Satisfaction problemsConstraint Satisfaction problems (CSPs) are problems where: - There is a set of variables,
- Each variable has a set of values it can be assigned to and
- 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. - Set of variables is the array positions where a character can be placed.
- Set of values for each position is the legal values it can take (example: all characters must belong to the original string).
- Constraint here is that the character once assigned, should not repeat.
CSPs are solved by backtracking - - Choose a starting point,
- Assign one of the values to that variable from its admissible set,
- Filter out values from all other variables
- Repeat above for the second variable.
- 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. : Most constrained variableMCVWhen assigning values to variables, always choose that variable which has minimum number of values left in its set. : Least constrained valueLCVWhen 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. |

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