Description
Question 1 (15 points):
Purpose: To apply the techniques of AIMA Chapter 3 (Assignment 1) to this problem.
Degree of Diculty: Easy.
To truly understand how bad the techniques of Chapter 3 (Assignment 1) are for this problem, we’re going
to implement it. It should not take too long, provided you understand the interfaces involved. The result
will be a fairly easy program to write, but it will be very slow, except for very small problem instances.
You may use your own implementation of DFS from your search strategies for Assignment 1, or you can
make use of the solutions provided (in Python only, sorry). In any case, your work should be focussed on
the Problem classes, and none of what you do needs to aect the search strategies. DFS is not going to
change!
You’ll need to implement:
• State: Represent the problem naively, as a 2-dimensional list (or array) of integers (the blank in the le
could be stored as a zero). You could add a list of blank locations by giving the row and column as
integer pairs (e.g., (2, 3) ). This would help speed up some of the other functions.
• Problem is_goal(state): Checks if state array is a true Latin Square. Note that if there is a blank (a
zero), it’s denitely not a completed Latin Square; you don’t have to keep checking if there are any
blanks in your list of blanks.
• Problem actions(state): A blank can be lled in with any number 1, . . . , N. You can specify which
blank to ll in, or you can assume it will be the rst blank in your list of blanks. But don’t actually ll in
the blank yet. That’s the work of result().
• Problem result(state, action): Creates a new State object with the blank lled in, as described in
action. Make sure you copy your lists/arrays, and change the copy.
Note: Don’t try to add anything clever to the code to make it faster. Your program does not have to solve
all the problems! Just implement the simplest version of actions() and result(). We’ll be more clever
in later questions. This is a straw-man implementation of an idea that seemed pretty good in Chapter 3,
but is really not very good here. You need to see it to believe it. So be quick about getting the simplest
implementation of the above specication as possible.
Questions to answer
Apply your implementation to the examples in the given data le LatinSquares.txt. Use a time-limit of 10
seconds for each problem.
Answer the following questions and submit them:
1. How many of the problems did your implementation solve within 10 seconds?
2. Consider the largest N that your implementation as able to solve. Do a rough, back-of-the-envelope
calculation to predict how much time it would take to solve the next largest problem in the le, and
the very largest problem in the le. Submit your rough calculations, and your predictions.
What to Hand In
• A le named a3q1_EXECUTION.txt containing brief instructions for compiling and/or running your
code. See page 1.
• A le named a3q1.LANG containing your implementation of the State and Problem classes. Use the
le extension appropriate for your choice of programming language, e.g., .py or .java.
ce
• A le named a3q1.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the
responses to the above questions.
Be sure to include your name, NSID, student number, and course number at the top of all documents.
Evaluation
• 6 marks: Your implementation of the State and Problem class captures the problem in a way that
reects Chapter 3. Your program does not have to solve all problems.
• 9 marks. Your answers to the questions are plausible and supported by evidence.
Question 2 (15 points):
Purpose: To implement the Constraint Satisfaction Problem concept of State as variables with domains.
Degree of Diculty: Moderate. The transition from A3Q1 to A3Q2 will take the most time of all questions.
In this question, you’ll replace the State from the previous question. It will involve making changes to
your State and Problem classes, just to change the State representation from 2-dimensional lists/arrays,
to a collection of CSP variables with domains. This is a preliminary step towards applying more advanced
algorithms, but essentially, your implementation of a3q2 will explore the same set of combinations as the
previous question. We won’t get advanced performance in this question.
You should only need to change the Problem and State classes.
• Variable: A variable should be an object with a current value, and a list or set of domain values. If the
variable is not assigned a value yet, the current value can be NULL or None. When the variable is
assigned a value, the domain should be set to an empty list or set. A variable does not need to know
its own identier, but it could.
• State: In this question, your State should consist of a collection of Variables.
– The collection could be a list, or a 2-dimensional list, or a dictionary indexed by variable identiers.
– Each variable needs an identier, and for some problems a string would work ne. But here, it
might be easiest to use a pair of numbers representing the row-column index of the variable’s
location in the square. The identier is used to nd the variable by name, without having to store
multiple references (Using references as variable identiers is possible but not advised. The programmer time spent debugging is not worth the speed increase you’d see. Leave that kind of
optimization for your code that matters more. We’re experimenting.)
– Remember that variables start out unassigned, and are assigned as the search goes on. Your
state could have a list of unassigned variable identiers to help avoid searching for unassigned
variables. Don’t store your actual variables in two dierent lists, unless you enjoy headaches and
frustration.
• Problem is_goal(state): Checks if the State is a solution to the Latin Square completion problem.
Note that if there is any unassigned variable, it’s denitely not a completed Latin Square; you don’t
have to keep checking if there are any variables still unassigned. You could adapt your code for
A3Q1.is_goal(state) to implement this function. You may need to combine the information contained in the given “square” with the values assigned in your state.
• Problem actions(state): Here, choose an unassigned variable and create an action for each allowable domain value. But don’t actually make the assignment yet. That’s still the work of result()
• Problem result(state, action): Creates a new State, with the variable assigned the given value, as
provided by action(). Make sure you copy the variables appropriately, and change the copy.
Notes:
• Your Problem class constructor should take a “square” as an input argument, and from that square.
You can have another method called initial_state() that uses the square to create a State object.
• For this question, the domain for every blank cell in the square should start out with all the values
1, . . . , N, i.e., don’t remove values that appear on the same row and column. We’ll x that in the next
question.
• In class we said it was possible to represent this problem 2 ways: Every cell (lled or blank) could be
a variable; or only the blank cells are variables. It’s slightly more advantageous to make variables
for only the blank cells. It complicates the goal test a bit.
• The is_goal(state) function is also a bit hard to get right, but test it with examples, not by applying
your search algorithms.
• The action() and result() functions should be straight-forward, once you have everything else settled.
• Test your is_goal(state), action(), and result() functions before trying them out with search. A
test script that you can re-run when you make changes to your code will save you lots of time!
Questions to answer
Apply your implementation to the examples in the given data le LatinSquares.txt. Use a time-limit of 10
seconds for each problem.
Answer the following questions and submit them:
1. How many of the problems did your implementation solve within 10 seconds? How does this compare
to the previous implementation (A3Q1)?
2. Consider the largest N that your implementation as able to solve. Do a rough, back-of-the-envelope
calculation to predict how much time it would take to solve the next largest problem in the le, and
the very largest problem in the le. Submit your rough calculations, and your predictions.
What to Hand In
• A le named a3q2_EXECUTION.txt containing brief instructions for compiling and/or running your
code. See page 3.
• A le named a3q2.LANG containing your implementation of the State and Problem classes. Use the
le extension appropriate for your choice of programming language, e.g., .py or .java.
• A le named a3q2.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the
responses to the above questions.
Be sure to include your name, NSID, student number, and course number at the top of all documents.
Evaluation
• 6 marks: Your implementation of the State and Problem class uses a collection of variables and domain values. Your program does not have to solve all problems.
• 9 marks. Your answers to the questions are plausible and supported by evidence.
Question 3 (5 points):
Purpose: To demonstrate the power of the very simplest of improvements to the previous implementation.
Degree of Diculty: Easy.
In the previous question, the domains were deliberately left as the values 1, . . . , N. In this question, change
your problem class code so that each variable’s domain is restricted to value that do not appear on the
cell’s row and column. For example, consider the top left blank in the following square:
_ 2 _ _ 4
3 _ 1 _ _
_ 4 _ _ 1
2 _ _ _ 3
_ _ 2 1 _
Since the values 2, 4 appear in the row, and the values 2, 3 appear in the column, the cell cannot take those
values, and so the domain for the top left cell should be limited to just {1, 5}.
Implement this restriction by creating variables whose domains are all feasible just looking at the row and
column (probably in your initial_state() method). Don’t change anything else.
Questions to answer
Apply your implementation to the examples in the given data le LatinSquares.txt. Use a time-limit of 10
seconds for each problem.
Answer the following questions and submit them:
1. How many of the problems did your implementation solve within 10 seconds? How does this compare
to the previous implementation (A3Q2)?
2. Consider the largest N that your implementation as able to solve. Do a rough, back-of-the-envelope
calculation to predict how much time it would take to solve the next largest problem in the le, and
the very largest problem in the le. Submit your rough calculations, and your predictions.
What to Hand In
• A le named a3q3_EXECUTION.txt containing brief instructions for compiling and/or running your
code. See page 3.
• A le named a3q3.LANG containing your implementation of the State and Problem classes. Use the
le extension appropriate for your choice of programming language, e.g., .py or .java.
• A le named a3q3.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the
responses to the above questions.
Be sure to include your name, NSID, student number, and course number at the top of all documents.
Evaluation
• 2 marks: Your implementation of the domain restrictions is correct. Your program does not have to
solve all problems.
• 3 marks. Your answers to the questions are plausible and supported by evidence.
Question 4 (15 points):
Purpose: To implement the Constraint Satisfaction Problem concept of forward checking.
Degree of Diculty: Easy.
Forward checking is a process of removing values from the domains of some unassigned variables, if those
values can be determined to be inconsistent with the current partial assignment.
The way it will work in the LSCP is as follows: When a cell X is assigned the value v, we know that no other
variable in X’s row or column can also have the value v. So, if the value v is still a domain value in any
unassigned variable on X’s row or column, we can remove it in advance, so that it is never tried.
There are some complications.
1. The value v might not appear in the domain when you try to remove it. That’s perfectly ne; it might
have been removed for some other reason. This removal is more like a prevention. Only remove it if it
is still there.
2. Don’t try to remove a domain value from an assigned variable.
3. We’re exploring states that represent dierent partial assignments. You really need to make sure that
your states and domain values are copies, and not references to a common list. When you remove a
domain value in one state, it can’t aect other states by accident!
4. It could be that you’ll remove the very last possible domain value for some unassigned variable. When
that happens, there is no consistent assignment for that variable, and so the current partial assignment
(the state) is inconsistent. The best thing to do is to recognize when a domain goes empty as you’re
removing the value. The easiest way to manage it is to have a Boolean ag in your state for consistent
or inconsistent assignments. Set the ag as soon as possible.
Starting with A3Q3, implement the forward checking for LSCP:
• State: Include a boolean ag for to indicate if the state is known to be inconsistent.
• Problem is_goal(state): With forward checking, every consistent partial assignment can be extended by one more variable (at least). That means when the assignment is complete (no unassigned
variables), it must be consistent! This simplies the goal test substantially!
• Problem actions(state): Check if the current state is inconsistent. If it is not consistent, return an
empty list of actions. This prevents inconsistent states from having children.
• Problem result(state, action): The action is a variable X and a domain value v. Copy the state as
usual, make the assignment, and then remove the value v from the domain of any unassigned variable
in X’s row and column. See the note above about removing values.
Questions to answer
Apply your implementation to the examples in the given data le LatinSquares.txt, using a time-limit of
10 seconds for each problem in this le. Then apply your implementation to the examples in the given data
le harder_examples.txt, using a time-limit of 200 seconds for each problem in this le.
Answer the following questions and submit them:
1. How many of the problems did your implementation solve within the time limit? How does this compare to the previous implementation (A3Q3)?
What to Hand In
• A le named a3q4_EXECUTION.txt containing brief instructions for compiling and/or running your
code. See page 3.
• A le named a3q4.LANG containing your implementation of the State and Problem classes. Use the
le extension appropriate for your choice of programming language, e.g., .py or .java.
• A le named a3q4.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the
responses to the above questions.
Be sure to include your name, NSID, student number, and course number at the top of all documents.
Evaluation
• 10 marks: Your implementation of the domain restrictions is correct. Your program does not have to
solve all problems.
• 5 marks. Your answers to the questions are plausible and supported by evidence.
Tasks for the ambitious
It seems that forward checking is a big improvement, but it has its limits. It works really well on toy kinds of
problems (Latin squares, N-Queens). However, most CSP solvers use a stronger form of processing called arc
consistency, which has higher complexity than forward-checking, but usually results in much more signicant
domain reductions for most real-world problems. Implement a version of the AC-3 algorithm. You can use it in
initial_state() to make sure that the initial domains for your problem start o possibly highly reduced even
compared to A3Q3, and in result() as in A3Q4, to keep your domains even smaller than forward-checking.
The bigger your problem, the more the extra processing pays o!
Page 11
