Exercise 3        Name __________________        Score __/10

  1. The assignment {WA=red, NT=red} is inconsistent under the problem constraints. Why?

    Adjacent
     
  2. The assignment {WA=red, NSW=red} is inconsistent. Why?

    Forces NT=blue, Q=green, SA violates constraints.

    Use the Python code below:
     

  3. What is returned by: Australia()?

    A CSP containing variables, domains, neighbors and constraints.
     
  4. What is returned by: BACKTRACKING_SEARCH(Australia())?

    An assignment of all variables to consistent values.
     
  5. What purpose is the assignment variable below?

    The list of variables and consistent values assigned.
     
  6. What purpose is the var variable below?

    The variable being explored for assignment.
     
  7. Suppose:

    ORDER_DOMAIN_VALUES( var, assignment, csp)

    returns [R, G, B]

    What will value be?

    R, G, B
     

  8. What would the following do?

    if CONSISTENT(Q, R, {NT:B, NSW:G}, csp.CONSTRAINTS, [NT,SA,NSW]) :         
          assignment[var]=value

    CONSISTENT returns True
     

  9. What is assignment variable now?

    {NT:B, NSW:G, Q:R}
     
  10. Assuming var is the same as in Question 9, what is assignment after the following?

          del assignment[var]

    {NT:B, NSW:G}

def RECURSIVE_BACKTRACKING( assignment, csp) :
   if COMPLETE(assignment, csp.VARIABLES ) : return assignment
   var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
   for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
      if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
         assignment[var]=value
         result = RECURSIVE_BACKTRACKING(assignment,csp)
         if result != 'failure' : return result
         del assignment[var]
   return 'failure'

def Australia() : # Return a CSP instance of the Map Coloring of Australia.
   WA,Q,T,V,SA,NT,NSW = 'WA','Q','T','V','SA','NT','NSW'
   values = ['R', 'G', 'B']
   vars = [WA, Q, T, V, SA, NT, NSW]
   domains = {SA: values[:], WA:values[:], NT:values[:],
                     Q:values[:], NSW:values[:], V:values[:], T:values[:]}
   neighbors = {WA: [SA, NT], Q: [SA, NT, NSW], T: [],V: [SA, NSW],
                        SA: [WA, NT, Q, NSW, V], NT: [SA, WA, Q], NSW: [SA, Q, V]}
   constraints = {SA: constraint, WA:constraint, NT:constraint, Q:constraint,
                         NSW:constraint, V:constraint, T:constraint}
   return CSP(vars, domains, neighbors, constraints)