Exercise 3        Name __________________        Score __/10

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

    Use the Python code below:
     

  3. What is returned by: Australia()?
  4. What is returned by: BACKTRACKING_SEARCH(Australia())?
  5. What purpose is the assignment variable below?
  6. What purpose is the var variable below?
  7. Suppose:

    ORDER_DOMAIN_VALUES( var, assignment, csp)

    returns [R, G, B]

    What will value be?

     

  8. What would the following do?

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

  9. What is assignment variable now?
  10. Assuming var is the same as in Question 9, what is assignment after the following?

          del assignment[var]

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)