---

Did you check the short description of "Secretaries' Nightmare"? If not, click here.

---

There are two orthogonal ways of constraint satisfaction problem solving. The one is backtracking and the other is constraint propagation. Backtracking always finds solution if exist, but less efficient than constraint propagation. Constraint propagation(arc-consistency) is efficient, but does not guarantee solutions. Constraint propatation result is consistency sets, which can be solutions but we lost intermediate steps why the domain elements should be eliminated In general, backtracking is complete but inefficient and constraint propagation is efficient but incomplete. There are several methods for each of the algorithms, but I am introducing the most popular methods, dependency directed backtracking(backtracking) and arc-consistency(constraint propagation, AC-3).

---

---

This method is backtracking(dependency directed backtracking). In backtracking method, we first decide parameter values. Then test if the values are consistent. If not, select another values and test until a solution is found. To avoid thrashing, DDB records future nogoods and decides the culprit, usually the farthest nodes from current dead-lock node, and jump to the culprit.

• First step : MD1 <---< 4>, Axel1 <---< 4>, Dirk1 <--- < 5>. Because "MD1" to "Dirk1" and "Axel1" to "Dirk1" values are inconsistent, test other values of Dirk's. But dead lock will occur because Dirk1 does not have <4>. Record {MD1,4} and {Axel1,4} as future nogoods and jump to the farthest node, "MD1".

• Second step : Try <5>. As the same as the first step, {MD1,5}, {Axel1,5} and {Dirk1,5} will be recorded as future nogoods and jump to "MD1".

• Third step : Try <6>. Nearly the same as the first step. Record {MD1,6}, {Axel1,6} as future nogoods and jump to "MD1".

• Fourth step : Try <7>. Found solution.

---

---

This method is constraint propagation(arc-consistency, AC-3). If we use constraint propagation, we can eliminate inconsistent domain values before making a decision.

• First round(red slash) : We can eliminate several MD1's dates using relationship("=") between MD1 and Axel1

• Second round(blue cross) : Using relationship("=") between MD1 and Dirk, we can eliminate several MD1's dates and a Dirk's date. Because MD1 is connected Axel1, we can delete Axel's dates, too.

• Third round(green bar) : Using relationship("=") between MD1 and Brigitt1, we can eliminate inconsistent values of MD1 and Brigitt1. As the same as previous round, we can delete Axel's and Dirk's dates,too.

• Eventually, we can get consistent sets as { 7, 8, 25 }

---

Heecheol Jeon : jhc@cdr.stanford.edu