Description

Adapted from the Course Scheduling of Stanford CS221
Introduction
In this project, you are going to construct a CSP for N-Queens problem. You will be given several python files.
Files you’ll edit:
submission.py Where you need to fill in codes in three places.
Files you need to look at: test.py You can use this file to grade your program.
run.py You can use this file to run your program to see results.
csp.py The important class CSP is provided in this file.

Files to Edit and Submit: You will fill in portions of submission.py during the assignment. You should submit this file with your code and comments. Please do NOT change the other files in this distribution or submit any of our original files other than these files.

Evaluation: Your code will be auto-graded for technical correctness. Please do NOT change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation — not the auto-grader’s judgements — will be the final judge of your score. We will review and grade assignments individually to ensure that you receive correct credit for your work.

CSP for N-Queens
A basic backtracking search BacktrackingSearch is already implemented in submission.py. The function will help you solve the CSP. You should read it carefully to make sure that you understand how the backtracking search is working.
a) [5 points] Let’s create a CSP to solve the N-Queens problem: Given an 𝑛×𝑛 board, we’d like to place 𝑛 queens on this board such that no 2 queens are on the same row, column, or diagonal. Implement create_n_queens_csp() by adding n variables and some number of binary factors. Note that the solver collects some basic statistics on the performance of the algorithm. You should take advantage of these statistics for debugging and analysis. You should get 92 (optimal) assignments for 𝑛=8 with exactly 2057 operations (number of calls to backtrack()).
Hint: If you get a larger number of operations, make sure your CSP is minimal. Try to define the variables such that the size of domain is O(n).
b) [5 points] You might notice that our search algorithm explores quite a large number of states even for the 8×8 board. Let’s see if we can do better. One heuristic we discussed in class is using most constrained variable (MCV): To choose an unassigned variable, pick the 𝑋& that has the fewest number of values 𝑎 which are consistent with the current partial assignment (𝑎 for which check_factor() on 𝑋& =𝑎 returns True). Implement this heuristic in get_unassigned_variable() under the condition self.mcv = True. It should take you exactly 1361 operations to find all optimal assignments for 8 queens CSP — that’s 30% fewer!
Some useful fields:
Ø csp.unary_factors[var][val] gives the unary factor value.
Ø csp.binary_factors[var1][var2][val1][val2] gives the binary factor value.
 Here, var1 and var2 are variables and val1 and val2 are their corresponding values.
With AC-3 enabled, it should take you 769 operations only to find all optimal assignments to 8 queens CSP — That is almost 45% fewer even compared with MCV!
Take a deep breath! This part requires time and effort to implement — be patient.
Submission (IMPORTANT THINGS! READ THREE TIMES)