Description

1 Written Portion (21 points)
1.1 AC-3 and CSPs
Suppose you are tasked with coming up with a coloring scheme for family homes. Their requirements are that no two adjacent rooms are the same color. They also want to keep the paint job relatively cheap, so they have agreed to only use 3 colors of paint: X, Y, and Z. The floor plan of the first home is below:

1. Cast this problem as a CSP, what are the variables, constraints, and corresponding domains?
3. This seems a little inefficient, especially if you were to scale this to a more complicated floor plan. Youdecide to try modifying your heuristic function. What would the tree be if you used most constraining variable first? Any ties are broken by lexigraphical ordering.
4. What about if you did most constraining variable combined with least constraining value?
5. What would the table be if you tried to use forward checking?
6. After hearing about the wonders of the AC-3 algorithm, you decide to run the algorithm on thisquestion. What happens when you run AC-3 on this problem as is (all domains have all possibilities still)? Do you arrive at a full solution? Why or why not?
1
7. The owner of the house says that room A should be Y and room B should be color X. If we run AC-3
this time with the arc queue [(A,H),(H,A),(B,C),(C,B),(B,D),(D,B),(C,D),(D,C),(C,H),(H,C),(D,H),(H,D)…] which variables have reduced domains? What are their corresponding domains now? Which arcs are added to the queue and in what order?
2 Code Portion (20 points)
2.1 AC-3
• Modify the SudokuBoard class from HW1 such that the board is a dictionary, mapping each board location, such as (0,0), to a set of possible values, such as set([1,2]). When reading in the board, this can be implemented by mapping the location of each “*” to set(range(1,10)), and the location of each number x to a singleton set, set([x]).
• Create a structure mapping each constraint to a set of its uncertain members. For example, for sudokuboard2.txt, this structure would initially map the top row constraint set([(0,0), (0,1), (0,2),
(0,3), (0,4), (0,5), (0,6), (0,7), (0,8)]) to set([(0,3), (0,4), (0,5), (0,6), (0,7)]).
Test AC-3 on the boards sudoku-board1.txt through sudoku-board5.txt. AC-3 should only be able to solve one of these boards. Report which of these boards your implementation of AC-3 was able to solve, and print its solution.
2.2 Singularity of Values
Augment your Sudoku solver (which is currently just the AC-3 algorithm) with this other type of inference. Now which of the 5 boards can it solve? For each of the boards it’s able to solve, print its solution. To make it easier for us to check your solutions, Please submit 3 files:
1. a file .pdf or .txt answering the above questions
2. a file .py or .zip with the code you wrote
3. A file called solutions.txt. In this file, include the solutions this Sudoku solver found. Format of the solutions should be just like that of the input board files (9 lines with 9 numbers per line, no spaces), with a blank line between each of the different board solutions.
2