#!/usr/bin/env python
# coding: utf-8

# # Assignment 4
# 
# ## Constraint satisfaction problems
# 

# *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?
# 

# ## Answers

# **Task 1** *Formulation of the k-knights problem*.
# 
# *Your answer here*

# **Task 2** *Implementation*
# 

# In[ ]:


# 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*.

# In[ ]:


# 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*

# ## Submission
# 
# 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
# 
# Grading will be based on the following criteria:
# 
# * Your code solves the specified problem.
# * Overall readability and organization of the notebook.
# * Effort in making interesting observations where required.
# * Conciseness. Points may be taken off if the notebook is overly long.