CMPT 317

Introduction to Artificial Intelligence

Assignment 3

Constraint Satisfaction Problems

General Instructions

• This assignment is individual work. You may discuss questions and problems with anyone, but

the work you hand in for this assignment must be your own work.

• Each question indicates what to hand in.

• Do not submit folders, or zip ?les, even if you think it will help.

• Assignments must be submitted to Moodle.

Version History

• 23/10/2018: Added requirement to submit execution instructions.

• 18/10/2018: released to students

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

Overview

A Latin Square of order N is a N × N matrix containing the integers 1, . . . , N, such that each value appears

exactly once in a row, and exactly once in a column. Another way to express this is that each row and column

is a permutation of the numbers 1, . . . , N. For example, the following is a Latin Square of order 5:

1 2 5 3 4

3 5 1 4 2

5 4 3 2 1

2 1 4 5 3

4 3 2 1 5

These are similar to the popular Sudoku puzzles (after the puzzle is ?nished), but a little simpler, as they do

not have “block constraints.” As you may already have guessed, there are many Latin Squares of order N, and

many di?erent values of N we can use.

If we take a Latin Square and erase some of the values, we create a kind of a puzzle (again, similar to a

Sudoku puzzle). For example, here’s a partially ?lled in 5×5 matrix, with the _ symbol representing a blank cell:

_ 2 _ _ 4

3 _ 1 _ _

_ 4 _ _ 1

2 _ _ _ 3

_ _ 2 1 _

This matrix was created by deleting values from the Latin Square, above, so we know it can be completed. We

can call this an incomplete Latin Square.

The Latin Square Completion Problem is to ?ll in the the blank cells of an incomplete Latin Square, using

the values from 1, . . . , N, to create a complete Latin Square. This problem was often used by researchers as

a source of solvable problem instances of various sizes (N) and di?culty levels (the number of blanks), to test

and evaluate the performance of their constraint satisfaction algorithms.

Example problems

A number of example ?les, containing one or more incomplete Latin Squares, are available to you on the

Moodle page. All the examples given in the examples ?le are solvable (and were constructed by a program to

generate solvable instances). Some of them may have more than one completion. All we need is to ?nd one

of them. Some of the data ?les have just one example. One of the ?les has many examples. Each example has

the same format, as follows.

• The ?rst line in the ?le contains a single integer, indicating the number of examples in the ?le. The rest of

the ?le consists of examples, as follows.

• The ?rst line of an example is the order, i.e., the value for N.

• Exactly N rows with N values, separated by spaces. The value _ indicates a blank.

• There is always exactly one blank line after every example.

You’ll be asked to apply your implementations to a ?le containing 56 examples, which are generally increasing

in di?culty. Once you notice your program is not solving problems of a certain size, you can terminate the

program to save some of your time.

Page 2

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

Coding hints

The simplest way to deal with the data ?les is to write a single function that can read in the ?le, and produce a

list of “squares”, i.e., a 2-dimensional list (or array) of integers (or strings). Once you have one or more of these

“squares” in a list, you have a lot of ?exibility. You can implement a Problem class code ti initialize a Problem

given any single square. This will prevent a lot of needless recoding as you move from ?les with 1 example to

?les with several examples.

The constraints in this problem are called “global” in the text, because they involve whole rows (and columns).

For example, the constraint on a row is that each row is a permutation of the numbers 1, . . . , N. However, and

this is important, all global constraints can be re-written using multiple binary constraints (i.e., constraints between 2 variables). In our case, a row is a sequence of cells, and each cell can be a variable. Furthermore, the

permutation constraint can be rewritten as a so-called “all-di?erent” constraint involving all the cells on the

row, which in turn can be rewritten in terms of multiple “not equal to” constraints between all pairs of variables.

The point is, don’t over think the constraints, and don’t over think the goal test.

A problem made up entirely of not-equals constraints is as straightforward as it gets (it’s like searching a

map with A∗ using straight-line distance as your heuristic — really well suited for the problem and a good

teaching example, but not representative of the variety of problems to be solved). We can get a pretty good

understanding of constraint solving using these simple constraints, but keep in mind that there are constraint

problems involving other kinds of constraints.

Execution instructions

The markers may or may not wish to run your program, to verify your results. To help them, you should provide

brief instructions on what to do to get your program running. Include:

• Programming language used (including version, e.g., Java 8 or Python 3)

• A simple example of compiling and/or running the code from a UNIX shell would be best.

Keep it brief, and name it with the question number as the following example: a3q1_EXECUTION.txt. If your

assignment uses third party libraries, they have to be included in your submission.

Page 3

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

Question 1 (15 points):

Purpose: To apply the techniques of AIMA Chapter 3 (Assignment 1) to this problem.

Degree of Di?culty: 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 a?ect 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 de?nitely 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 speci?cation 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.

Page 4

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

• 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

re?ects Chapter 3. Your program does not have to solve all problems.

• 9 marks. Your answers to the questions are plausible and supported by evidence.

Page 5

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

Question 2 (15 points):

Purpose: To implement the Constraint Satisfaction Problem concept of State as variables with domains.

Degree of Di?culty: 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 identi?er, 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 identi?ers.

– Each variable needs an identi?er, 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 identi?er is used to ?nd the variable by name, without having to store

multiple references (Using references as variable identi?ers 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 identi?ers to help avoid searching for unassigned

variables. Don’t store your actual variables in two di?erent 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 de?nitely 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.

Page 6

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

• 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.

Page 7

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

Question 3 (5 points):

Purpose: To demonstrate the power of the very simplest of improvements to the previous implementation.

Degree of Di?culty: 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.

Page 8

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

Question 4 (15 points):

Purpose: To implement the Constraint Satisfaction Problem concept of forward checking.

Degree of Di?culty: 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 di?erent 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 a?ect 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 simpli?es 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)?

Page 9

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

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.

Page 10

Department of Computer Science

176 Thorvaldson Building

110 Science Place, Saskatoon, SK, S7N 5C9, Canada

Telephine: (306) 966-4886, Facimile: (306) 966-4884

CMPT 317

Fall 2018

Introduction to Artificial Intelligence

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 signi?cant

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