CSP for N-Queens
a) [5 points] Implement backtrack() (part a) according to the pseudocode.
b)
c)
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()).
[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).
[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.
2 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.
[10 points] 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!)
&
d)
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.
Submission (IMPORTANT THINGS! READ THREE TIMES)
- – Submit your code, only one file: submission.py, through e-learning in one zip file with name “pj2-<student_id>.zip”. E.g. “pj2-16307110235.zip”
- – Project 2 is due on November 13th, Wed, 11:55pm, 2019.
- – If you have any questions about this project, please contact [email protected].
