From 6.034 Wiki
This page aims to clarify the terminology that 6.034 uses for constraint propagation.
When you are solving a problem with constraint propagation, you typically have to do two things: reduce domains and search. You've already learned a variety of ways to search, and now there's a variety of ways to reduce domains as well. In addition, we give you recommendations about which methods are best at solving typical problems.
As you solve a constraint propagation problem, you typically gain information that certain options are no longer available. In a map coloring problem, for example, when you color a state red, you know that red is no longer an option for its neighboring states.
Your options here include:
You can try the Demonstrations, which allow you to compare many of these methods on a map coloring problem.
On a quiz, we'll tell you what strategy to use for domain reduction. But if you're faced with a constraint propagation problem outside of a quiz, we endorse forward checking with propagation through singletons as the method that works best on most problems.
Logic puzzles can often be solved with domain reduction alone, but in the real world you will have to try some assignments and see what works. This is a search problem! So you have some options:
Of these methods, we recommend depth first, most constrained first for most problems.
Remember the "Elevation" problem from mega-recitation? Let's do it again without the confused terminology.
You're trying to map this hill, where you know the elevations of a few grid cells, and you know that adjacent grid cells differ in height by at most 1.
How much can you conclude before you have to search?
If you're using backchecking only, then the only thing you're really doing is searching, and there's nothing you can conclude beforehand.
With forward checking, several domains become smaller. (Dashes represent ranges of possible numbers. Bold numbers have been assigned and forward-checked.)
This created some singleton domains! So you could assign those values and keep going if you use forward checking with propagation through singletons. The next step is:
Now you can propagate even more through the new singletons:
One more time:
That's all you can get before you search using propagation through singletons, but there isn't much left to search.
You could get a little more information if you chose to propagate through all reduced domains, instead of just singletons. What's that 2-4 doing toward the lower left, when it's adjacent to things that can only be 1-2? Given that information, that cell can actually be at most 3.
And from here, there's nothing left to do but search. Following the most constrained first principle, you'd start from the cell labeled "2-3", because it's not on the edge, and therefore it has four constraints while the others have three.