CS827: Adv. Artificial Intelligence

Unit 3: Constraint Satisfaction Problems (Assignment 3)


Ch.6

Exercise 6.5

Question:

Answer:

Variables:

Domains:

Constraints:

Variables assignment:

    F O U R T W | C3  C2  C1
    1 5 3 0 7 6 | 1   1   1


      T W O
    + T W O
    -------
    F O U R


    1 1 1
      7 6 5
    + 7 6 5
    -------
    1 5 3 0

Note: from what I understood C1, C2, C3 has no restriction to be distinct.

Exercise 6.9

Question:

Answer:

The heuristic of choosing the most constrained variable (MCV) —also called "minimum-remaining value, MRV or in other words: the variable with fewest 'legal' values— is good because it is most likely to cause a failure soon, thereby pruning the search tree.

While the reason for least-constraining-value heuristic is to leave the maximum flexibility for subsequent variable assignments. see AIMA: 6.3.1