Constraint Satisfaction

Search can be made easier in cases where the solution instead of corresponding to an optimal path, is only required to satisfy local consistency conditions. We call such problems Constraint Satisfaction (CS) Problems. For example, in a crossword puzzle it is only required that words that cross each other have the same letter in the location where they cross. It would be a general search problem if we require, say, that we use at most 15 vowels.