6.034 Tutorial: Constraint Propagation
Fall 2014
Problems Covered:
Time-Traveler's from Q2 2009
Zoo from Q2 2011
Errata:
How to order from most to least constrained:
Reduced domain size does not matter, take only edge constraints into account
Time-Traveler's problem did not ask for DFS tree size (Zoo problem did, but the 2 problems have the same # of variables and the same # of values and 1 singleton each, so we get the same result coincidentally)
Should not include eliminated parts of domains in DFS tree size calculations
The way I propagated constraints is correct, but the algorithm we expect you to know and use for the quiz is a bit different and will cause discrepancies for problems asking you to fill out a chart of 'variable checked, domain eliminated, backtracked' columns. I will try to upload another video covering this algorithm as soon as I get the chance.