DATA130008.01- Project 2: N-Queens Solved

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.  


 

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)      [5 points] Implement backtrack() (part a) according to the pseudocode.  

  

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 40 (optimal) assignments with exactly 552 operations (number of calls to backtrack()).  

 

b)      [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. You should get 92 (optimal) assignments for 𝑛=8 with exactly 2057 operations.  

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

 

c)    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.  

Ø  In BacktrackingSearch, if var has been assigned a value, you can retrieve it using assignment[var]. Otherwise var is not in assignment.  

d)      The previous heuristics looked only at the local effects of a variable or value. Let's now implement arc consistency (AC-3) that we discussed in lecture. After we set variable 𝑋& to value 𝑎, we remove the values 𝑏 of all neighboring variables 𝑋) that could cause arc-inconsistencies. If 𝑋)'s domain has changed, we use 𝑋)'s domain to remove values from the domains of its neighboring variables. This is repeated until no domains have changed. After applying AC-3, either every arc is arc-consistent (then arc_consistency_check() should return True), or some variable has an empty domain, indicating that the CSP cannot be solved (then arc_consistency_check() should return False). Note that this may significantly reduce your branching factor, although at some cost. Your job is to fill in arc_consistency_check() and then the backtrack() (part d) compatible with AC-3. (Implement the BacktrackingSearch strictly under the pseudocode!) 

  

With AC-3 enabled, it should take you 583 operations only to find all optimal assignments to 8 queens CSP.  

Take a deep breath! This part requires time and effort to implement — be patient.  

Hint 1: documentation for CSP.add_unary_factor() and CSP.add_binary_factor() can be helpful. Hint 2: although AC-3 works recursively, you may implement it iteratively. Using a queue might be a good idea. li.pop(0) removes and returns the first element for a python list li.