Homework 3 -- due date Wednesday extended to Saturday March 21

This homework will be graded out of 100 points. It will count 5% of the grade.

Written questions

1. [10 points] Given a constraint satisfaction problem with (1) a finite number of variables and (2) a finite domain for each variable
   1. how does the number of variables affect the size of the search space?
   2. how does the size of the domains affect the size of the search space?
   Explain your reasoning.
2. [20 points] Show in detail how to solve the following crypto-arithmetic problem I + DID = TOO. Write the constraint equations and show the search tree explored by the backtracking algorithm.
3. [20 points] This question is on the arc consistency AC-3 algorithm
   1. Show how the arc consistency AC-3 algorithm is able to detect the inconsistency of the partial assignment {Wa=red,V=blue} in the map of Australia.
   2. Try the same AC-3 algorithm to detect the inconsistency of the partial assignment {WA=red,NSW=red}. Does the algorithm detect the inconsistency or not?
   3. If not, why AC-3 is not always capable of detecting inconsistencies?
4. [10 points] How many solutions are there for the map-coloring problem for the Australia map (textbook Figure 6.1) when using three colors? Explain your results.
5. Extra credit [20 points] Use the AC-3 algorithm to label the following figure. Explain step by step how the algorithm works.

       

Programming questions

For these questions we will use the constraint satisfaction aima software. There are two algorithms implemented, backtracking-search and forward-checking. In the test file there are examples on how to call those functions.

Here are specific instructions for how to submit the programming part. Please folllow these instructions, this will save a lot of time for the TAs and reduce the chance of missing your work. Thank you!
1. All programming related content including output, and code should be in a zip file named prog.zip. Your solution to the written problem questions should be in PDF and should NOT be part of this zip file.
2. Do NOT submit any unmodified aima functions, classes or files. Any functions that need to be called from within your code should be imported using import statements. You should only submit your own code (function, class, driver, etc).
3. Your output to the programming part should in a plain text file called output (or output.txt). Instructions for creating this output file directly from the terminal can be found in hw1. You may submit multiple output files for each programming question and name them output_1, output_2, etc. However, NO screenshot, images, PDFs will be accepted for the output. Any written answer within the programming section should also be in the output file.
4. If you have NOT attempted any part of the programming questions or have a partial solution you should submit a README file (in plain text) that has a brief description of your attempt (or just say no attempt if you have not tried them).
1. [5 points] Use the the AIMA backtracking-search function to solve the n-queens problem with 4, 12, and 20 queens.
2. [5 points] For the same n-queens problems (4, 12 and 20 queens) use instead forward-checking.
3. [5 points] Use the the AIMA backtracking-search function to solve the map-coloring problem with 3 colors shown in the textbook in Figure 6.1.
4. [5 points] Repeat the same problem on the Australia map this time using 4 colors. Is the solution different? Do you need 4 colors or are 3 enough?
5. [5 points ] What happens if you use just 2 colors to color the Australia map?
6. [5 points ] Use the AC-3 algorithm for the Australia map.
7. [10 points] Use the the AIMA backtracking-search function to solve the map-coloring problem for the USA map.