Homework 03: Local Search for CSPs

The goal of this homework assignment is to implement local search for a constraint satisfaction problem: namely the 8-queens problem.

For this assignment, record your responses to the following activities in the README.md file in the homework03 folder of your assignments GitLab repository and push your work by 11:59 PM Wednesday, October 9.

Activity 0: Branching

As discussed in class, each homework assignment must be completed in its own git branch; this will allow you to separate the work of each assignment and for you to use the merge request workflow.

To create a homework03 branch in your local repository, follow the instructions below:

$ cd path/to/cse-40171-fa19-assignments                                                     # Go to assignments repository

$ git remote add upstream https://gitlab.com/wscheirer/cse-40171-fa19-assignments           # Switch back over to the main class repository

$ git fetch upstream                                                                        # Toggle the upstream branch

$ git pull upstream master                                                                  # Pull the files for homework03

$ git checkout -b homework03                                                                # Create homework03 branch and check it out

$ cd homework03                                                                             # Go into homework03 folder

Once these commands have been successfully performed, you are now ready to add, commit, and push any work required for this assignment.

Activity 1: Local Search for the 8-queens Game (100 Points)

According to Sec. 3.2 of Russell and Norvig, "The goal of the 8-queens problem is to place eight queens on a chessboard such that no queens attacks any other". Recall from the proper game of chess that a queen attacks any piece in the same row, column, or diagonal. The figure below shows one of the possible solutions for this problem.



Write a Python program that generates random boards for the 8-queens problem. Then implement a solver that makes use of local search (see Figs. 6.8 and 6.9 in Russell and Norvig). The solver should calculate the number of conflicts for each potential valid move of a queen, and make moves to a minimum cost position. Ties can be broken in random fashion. Incorporate an additional heuristic that assumes adjacent queens in a row, column or diagonal all contribute to the conflict value for positions within proximity (i.e., if there are two queens in the same row, they contribute a conflict cost of 2 together). Add a comment to your code that identifies the lines performing local search operations.

The program should be callable from the command line without any arguments: $ python eightqueens.py

The output of your program should look like the following:



On average, how many turns does it take to solve this problem? Record the answer to this question in your README.md.

Feedback

If you have any questions, comments, or concerns regarding the course, please provide your feedback at the end of your README.md.

Submission

To submit your assignment, please commit your work to the homework03 folder of your homework03 branch in your assignment's GitLab repository:

$ cd path/to/cse-40171-fa19-assignments   # Go to assignments repository
$ git checkout master                     # Make sure we are in master branch
$ git pull --rebase                       # Make sure we are up-to-date with GitLab
$ git checkout -b homework03              # Create homework03 branch and check it out
$ cd homework03                           # Go to homework03 directory
...
$ $EDITOR README.md                       # Edit appropriate README.md
$ git add README.md                       # Mark changes for commit
$ git commit -m "homework03: complete"    # Record changes
...
$ git push -u origin homework03           # Push branch to GitLab

Procedure for submitting your work: create a merge request by the process that is described here, but make sure to change the target branch from wscheirer/cse-40567-sp19-assignments to your personal fork's master branch so that your code is not visible to other students. Additionally, assign this merge request to our TA (sabraha2) and add wscheirer as an approver (so all class staff can track your submission).