1    Introduction

The aim of this assignment is to familiarise you with Constraint Satisfaction Problems  (CSPs) and the basic algorithms that are used to solve them.  You will implement, use and evaluate CSPs and their algorithms using Haskell.

The files you are going to use can be downloaded from the Inf2D Learn website. Go to Assessment → Coursework 1 - Constraint Satisfaction Problems. You should download the file coursework1 .tar.gz which contains the code template you will use to write your solution.

Use the command tar  -xvf  coursework1 .tar .gz to extract the files contained within. This will create a directory named coursework1/ containing three files:  CSPframework.hs, Examples .hs, and Inf2d.hs.

You will submit a version of the Inf2d.hs file containing your implemented functions and a small report.

Submission details can be found in Section 2.

There will be a lecture discussing this assignment on Thursday 28th of January 2022 at the standard lecture time and venue. There will also be weekly drop-in labs on Fridays 11am-1pm (weeks 4-9), in Appleton Tower 6.06, where a demonstrator will be available to answer your questions and provide appropriate help.

The assignment will build upon a framework for CSPs in Haskell. This framework consists of datatypes and functions that you will use in your implementation, as well as the simple Backtracking (BT) algorithm (R&N Fig:6.5 / NIE Ch.7 Fig:5).  The code for the framework can be found in the CSPframework.hs  file.  A reference manual for the framework is also available on the Inf2D web page:

https://www.learn.ed.ac.uk/bbcswebdav/xid-25602804_1

The following CSPs are already implemented for this framework and are available to help you understand the CSP framework and test and evaluate your various implementations:

• The Map of Australia (R&N §6.1.1 / NIE Ch.7 § 1.1)

• The Map of Scotland

• The 3x3 Magic Square

• A Sudoku problem (R&N Fig:6.4 / NIE Ch.7 Fig:4 )

The description of these problems can be found in the CSP framework reference manual. You can use this code to

gain a better understanding of the framework and as a starting point for your own implementation. The assignment is divided into four sections:

1. In the first section you are asked to implement the “N-Queens Problem” as a CSP (10%).

2. In the second section you will implement the Forward Chaining (FC) algorithm, the Minimum Remaining Values (MRV) heuristic, and the Least Constraint Value (LCV) heuristic (45%).

3. In the third section you are asked to evaluate and compare the algorithms using the implemented CSPs (25%).

4. Finally, in the fourth section you will implement the Arc Consistency (AC-3) algorithm and add it to your evaluation (20%).

If your Haskell is quite rusty, you should revise the following topics:

• Recursion

• Currying

• Higher-order functions.

• List Processing functions such as map, filter, foldl, sortBy, etc.

• The Maybe monad

The following webpage has lots of useful information if you need to revise Haskell. There are also links to descriptions of the Haskell libraries that you might find useful:

• Haskell installation instructions: https://www.haskell.org/platform/

• Haskell resources: https://wiki.haskell.org/Haskell

• Haskell tutorials: http://learnyouahaskell.com/chapters

In particular, to read this assignment sheet, you should recall the Haskell type-definition syntax.  For example, a function foo which takes an argument of type Int and an argument of type String , and returns an argument of type Int, has the type declaration foo  ::    Int  →  String  →  Int. Most of the functions you will write have their corresponding type-definitions already given.

2    Submission

You should submit your version of the file Inf2d.hs, that contains your implemented functions, evaluation table and report. You only need to submit the Inf2d.hs file.

Submit this file via the coursework link given in Learn. This will load a submission page in CodeGrade where you can upload your file. If you have trouble please refer to the links provided in this blog post:

https://blogs.ed.ac.uk/ilts/2020/09/15/codegrade/

Your file must be submitted by 3pm on the 8th of March 2022.

You can submit more than once up until the submission deadline. All submissions are timestamped automatically. We will mark the latest submission that comes in before the deadline.

If you do not submit anything before the deadline, a late penalty will be applied to this submission, unless you have received an approved extension.

Do not email any course staff directly about extension requests. For information about late penalties and extension requests, see:

http://web.inf.ed.ac.uk/infweb/student-services/ito/admin/coursework-projects/

late-coursework-extension-requests.

3    Important Information

There are the following sources of help:

• Attend lab sessions: Fridays 11am-1pm (weeks 4-9), in Appleton Tower 6.06

• Read  “Artificial Intelligence:  A Modern Approach” Third Edition, Russell & Norvig, Prentice Hall, 2010 (R&N) Chapter 6 or Pearson New International Edition, Pearson, 2014 (NIE) Chapter 7.

• Ask any questions on Piazza.

• Haskell refresher lecture: Tuesday 2:10pm, February 1st, 2022

4    The “N-Queens Problem” CSP (10%)

The N-Queens Problem is a problem inspired by chess, where N queens have to be placed on a NxN board so that no queen attacks any other queen.   A queen moves and attacks other pieces horizontally, vertically,  and diagonally.

For N=8, we need to place 8 queens in a standard 8x8 chessboard. One possible solution is the one shown in Figure 1.

Your task is to implement this problem as a CSP within the given framework.

Figure 1: A possible solution of the N-Queens problem for N=8.

A CSP is defined by a set of variables and a set of constraints.  Each variable has a non-empty set (domain) of possible values.  Each constraint involves some subset of the variables –its scope – in a relation  that specifies the allowable combinations of values for that subset.

Read the CSP framework reference manual given in Section 1 for details on the datatypes you must use for your implementation.

You can go through the four implemented examples of CSPs, namely the Map of Australia, the Map of Scotland, the 3x3 Magic Square, and the Sudoku1. This will help you understand the proper usage of the framework’s datatypes

so that you can implement your own CSP accordingly.

The following four tasks are required:

i. Your CSP must contain a set of variables and their respective domains that accurately represent the problem. Combine the variables and their domains to create a Domains list. Your implementation must at least support any possible value of N < 15. The functions you must implement are the following:

• queenVars  ::    Int  →  [Var] This function returns the list of CSP variables for a given parameter N.

• queenDomains  ::    Int  → Domains This function returns the Domains list for a given parameter N.

Hint:   One possible  solution  is  to  number the  queens  Q1 ,  Q2 , . . .   so  that  each  queen  corresponds  to  a  different row of the  board.  Their integer values then correspond to the column they have to  be placed on.

ii. Moreover, you must implement the appropriate constraints that will properly reflect the restrictions given in

the problem. For each constraint you must reuse or implement a Relation.

You must at least implement the following function:

• diagonalRelation  ::    Relation This binary relation ensures two variables (queens) are not in the same

diagonal. Note that the scope of the corresponding constraint is assumed to always contain 2 variables.

For the rest of the problem restrictions you can use the Relation functions that are already given with the framework or implement your own.  Note that you should only use unary or binary constraints.  The only exception is the already implemented allDiff constraint.

iii. Once you have defined the variables, domains and constraints of the problem, you must combine them to form the definition of the N-Queens CSP, with the size N as an Int parameter:

queenCsp  ::    Int  →  CSP

iv. Use the implemented BT algorithm to check that you have a correctly defined CSP. If your representation is accurate, the result must be a valid assignment of all the variables that will lead to the solution of the problem. For example, to solve for N = 8 use:

bt  (queenCsp  8)

5    CSP Algorithms (45%)

Having implemented a CSP and tried the BT algorithm on it, you are now asked to implement more complex CSP algorithms.

5.1    Forward Checking (FC) algorithm (20%)

The FC algorithm is a simple inference algorithm. Whenever a variable X is assigned, the forward checking process looks at each unassigned variable Y that is a neighbour of X .  It then deletes from Y’s domain any value that is inconsistent with the value chosen for X .  X and Y are considered neighbours when they are connected by (ie. within the scope of) the same constraint. FC indicates failure if it detects that one of the variable domains becomes empty. For a more detailed explanation of the algorithm, refer to R&N §6.3.2 / NIE Ch.7 §3.2.

Read the CSP framework reference manual mentioned in the Introduction for details on the datatypes and functions involved in retrieving the neighbours of a variable and the function to delete a value from a domain.

Your task is to implement the FC algorithm for the given framework according to the description of R&N §6.3.2 / NIE Ch.7 §3.2. In particular you will need to implement the following two functions:

i. forwardcheck  ::    CSP  → Assignment  → Var  →  (CSP,  Bool) This is the forward inference function.  Its arguments are: the current CSP, the current assignment/state of the problem and the variable X that was last assigned by the algorithm. It must find all variables Y that are neighbours with X and delete from their domains any values that are inconsistent with the given assignment. It returns the CSP with an updated Domains list paired with a boolean value that indicates whether the assignment is consistent or not (ie. returns False if one of the variable domains becomes empty).

ii. fcRecursion  ::    CSP  → Assignment  →  (Maybe  Assignment,  Int) The recursion for the FC algorithm. This is the forward checking counterpart of the btRecursion function.  Every time a value is assigned to a variable it must use forwardcheck and then apply a recursion over the returned CSP rather than the original one.  It must return Just a consistent and complete assignment for the given CSP or Nothing if there is no solution, paired with the number of nodes that were visited during the search.  Examine the implementation of btRecursion to understand how the counting of the nodes is accomplished.  The algorithm should also backtrack if forwardcheck indicates failure (returns False).

5.2    Minimum Remaining Values (MRV) (10%)

The MRV heuristic is a variable ordering heuristic. It affects the order in which the algorithm selects the variables for assignment.   The aim is to have the algorithm select the variables with less available values (therefore less branching) earlier on in the execution.

Your task is to implement the MRV heuristic and use it in the FC algorithm in the given framework, resulting in the FC+MRV algorithm. In particular you will need to implement the following functions:

i. getMRVVariable  ::    Assignment  →  CSP  → Var This is the implementation of the MRV heuristic for the FC algorithm. Given a CSP and an assignment, this function returns the first unassigned variable that has the smallest domain in the CSP.

ii. fcMRVRecursion  ::    CSP  → Assignment  →  (Maybe  Assignment,  Int) This is the same as fcRecursion from Section 5.1 but with the addition of the MRV heuristic implemented as getMRVVariable.

5.3    Least Constraining Value (LCV) (15%)

The LCV heuristic is a value ordering heuristic.  It affects the order in which the algorithm selects the values to assign to the selected variable.  The aim is to have the algorithm select the value that allows the most choices for the neighbours of the variable.

Your task is to implement the LCV heuristic and use it in the FC anf FC+MRV algorithms  (resulting in the FC+LCV and FC+MRV+LCV algorithms respectively) in the given framework.  In particular you will need to implement the following functions:

i. lcvSort  ::    CSP  → Assignment  → Var  →  [Int] This function returns the domain of a given variable, sorted according to the LCV heuristic.  You should use the numChoices function to help you implement the heuristic.

ii. fcLCVRecursion  ::    CSP  → Assignment  →  (Maybe  Assignment,  Int) This is the same as fcRecursion from Section 5.1 but with the addition of the LCV heuristic implemented as lcvSort.

iii. fcMRV LCVRecursion  ::    CSP  → Assignment  →  (Maybe  Assignment,  Int) This is the same as fcMRVRecursion from Section 5.2 but with the addition of the LCV heuristic implemented as lcvSort.

6    Evaluation and Discussion (25%)

For this task you are asked to run a small evaluation on your implemented algorithms and briefly discuss the results.

The evaluation will be based on the  number  of visited  search  nodes by each of the algorithms when used to solve each of the following CSPs:  Map of Australia, Map of Scotland, 3x3 Magic Square, and 8-Queens and 12-Queens (ie. N-Queens for N = 8 and N = 12 respectively).

We consider that a new search node has been visited when a new value has been assigned to a variable, followed by the respective recursive call of the algorithm.  You should check the implementation of the btRecursion function to understand how this is accomplished.

i. According to the specification given in 5.1 and 5.2, your implemented algorithms must return the solution to the problem paired with the number of visited search nodes. You must record this number for each algorithm on each of the four CSPs.

ii. You must complete the table provided in the given Haskell file with the number of visited nodes by the algorithms BT, FC, FC+MRV, FC+LCV, and FC+MRV+LCV for each of the CSPs Map of Australia, Map of Scotland, 3x3 Magic Square, 8-Queens, and 12-Queens.

iii. You must also write a brief report on your implementation and evaluation.   Your report must include the following:

(a) A brief explanation of the values in the table and the differences observed between the algorithms. (b) A discussion about whether these were expected or not, and why.

In particular, compare and explain your results of the following pairs of algorithms:

• BT vs. FC

• FC vs. FC+MRV

• FC vs. FC+LCV

• FC+MRV vs. FC+LCV

• FC+MRV vs. FC+MRV+LCV

iv. Is there a simple  yet effective, gerneral purpose optimisation that you can apply to your implemented FC algorithm to improve its performance (esp. when considering much bigger and harder CSPs)? Give a suggestion and your arguments as to how your optimisation would improve the algorithm.

Note: The report should be no longer than one A4 page of plain text written within your version of the Haskell file, in the section indicated in the document.

7    Arc Consistency Algorithm AC-3 (20%)

Arc consistency is a fast method for constraint propagation based on checking the consistency of the arcs in the constraint graph. An arc between two variables X and Y is consistent if for every value x of variable X there is a possible value of Y that is consistent with x. If there is a value x\  such that if it is assigned to X and there is no consistent value left for Y then we remove x\  from X’s possible values (domain).

The AC-3 algorithm is an implementation of arc consistency. You can find the pseudocode of the algorithm in R&N Fig:6.3 in §6.2 / NIE Ch.7 Fig:3 §2. Your task is to implement the AC-3 algorithm and evaluate it.