Solving the n-queens puzzle with backtracking

You are given the code for solving the n-queens puzzle with backtracking. The program returns a single solution if there exists one. There may be multiple solutions, but we are NOT interested in all of them for this assignment.

You will notice that the existing implementation is not very efficient. When you test the code for n around 15 – 20, you will especially notice the drop in runtime.

Your task is to improve the algorithm so that the program runs more efficiently. First, examine the nQueens.py code carefully. Then implement in the required methods as follows:

1. (30 pts) Fill in the body of the iselect_next_variable_improved method so that it implements minimum-remaining-values (MRV) heuristic. Replace this with select_next_variable. You will see that your code is more efficient now. You should use select_next_variable for the following parts.
2. (10 pts) Fill in the body of backtrack_improved so that it implements the full backtracking algorithm with inference. Note that this method requires parts (c) or (d) to work efficiently.
3. (30 pts) Fill in the body of forward_checking to implement the forward checking algorithm. You should be able to pass the forward_checking method as a parameter to backtrack_improved.
4. (30 pts) Fill in the body of the ac3 method to implement the constraint propagation (“maintaining arc consistency”) algorithm. You should be able to pass the ac3 method as a parameter to backtrack_improved.

Notes:

– You may implement additional helper methods.

– You can use the backtrack_counter value to track the efficiency of your algorithms.

– Please refer to your textbook or the slides for constraint satisfaction (lectures 9-10) for the implementation of these algorithms.

– Please submit your code, including comments that explain your approach, by uploading a .py file to Blackboard.

– You can submit as many times as you like. Only the latest version will be evaluated.