Type your name here
Consider the problem of placing $k$ black and $k$ white knights on an $n \times n$ chess board such that no two knights of the same color are attacking each other. We'll call it the k-knights problem. Your task is to solve this problem by considering it as a constraint satisfaction problem.
Task 1: Formulate the problem as a constraint satisfaction problem with binary constraints. Describe the variables, their domains, and the constraints.
Task 2:
Implement a class called knights
that is a sub-class of csp.CSP
(this refers to the class CSP
within the module csp.py
in the code library provided with the textbook). Your implementation of the class needs to allow you to solve the problem with any of the solvers implemented in the csp
module.
Task 3: Solve the k-knights problem using backtracking search with the various heuristics we have studied in class and compare their effectiveness quantified by the number of variable assignments required to get to a solution.
In your experiments, use values of $k$ and $n$ that provide these methods a challenge and takes sufficient time so that you can obtain some resolution for the comparison of the different heuristics (i.e. $n$ sufficiently large, and $k$ chosen such that it's not too easy to find a solution).
Task 4: The AC3 algorithm. In some cases this algorithm is able to solve constraint satisfaction problems, or at least make some progress towards the solution. Is this the case here? If not, explain why, and if yes, does it lead to solutions that require a smaller number of variable assignments when used in conjunction with backtracking search?
Task 1 Formulation of the k-knights problem.
Your answer here
Task 2 Implementation
# complete the implementation of the following class so it is able
# to solve the k-knights problem.
import csp
class knights(csp.CSP) :
def __init__(self, k, n) :
self.k = k
self.n = n
Task 3 Experiments on the k-knights problem.
# code for solving the k-knights problem as a CSP problem.
Show your results and discuss them here
Task 4 The AC3 algorithm
Your answer here
Answer the questions in the cells reserved for that purpose. Submit your report as a Jupyter notebook via Canvas. Running the notebook should generate all the results in your notebook. Leave the output of your notebook intact so we don't have to run it to see the results.
Grading will be based on the following criteria: