COMP 590-096 Assignment 2

COMP 590-096 Fall 2010

Assignment 2: Search

Due date: October 7, 11:59 PM

Instructions

The goal of this assignment is to implement the various search algorithms we have covered in class so far. You will need to turn in the following:

A report in PDF or Word Document format. The report should briefly describe your implemented solution and fully answer all the following questions. Your description should focus on the most "interesting" aspects of your solution, i.e., any non-obvious implementation choices and parameter settings, and what you have found to be especially important for getting good performance. Feel free to include pseudocode or figures if they are needed to clarify your approach. Your report should be self-contained and it should (ideally) make it possible for us to understand your solution without having to run your source code.

The name of the report file should be lastname_firstname_assignment2.pdf or lastname_firstname_assignment2.doc.
Your source code compressed to a single ZIP file. The code should be well commented, and it should be easy to see the correspondence between what's in the code and what's in the report. You don't need to include executables or various supporting files (e.g., utility libraries) whose content is irrelevant to the assignment. If we find it necessary to run your code in order to evaluate your solution, we will get in touch with you.

The name of the code archive should be lastname_firstname_assignment2.zip.

Submit your report and code files through Blackboard using the same instructions as in Assignment 1.

Late policy: You lose 25% of the points for every day the assignment is late. If you have a compelling reason for not being able to submit the assignment on time and would like to make a special arrangement, you must let me know ahead of the due date.

WARNING: We are well aware that the following are popular computer science problems and that numerous solutions are available on the Web in numerous programming languages. You should approach the main part of this assignment in good faith and refrain from consulting the Web (if you do, you will probably have to do lots of busywork to keep us from finding out, and you'll just be ruining your own fun, anyway). For the extra credit part (see bottom of this page), feel free to search the Web for ideas and/or code snippets. As per class policy, whenever you use outside code or references, please be sure to acknowledge them in your report.

Problem 1: 8-puzzle

The 8-puzzle was introduced in this lecture. Implement the following search algorithms for solving 8-puzzle instances:

Depth-first search.
Breadth-first search.
Greedy best-first search.
A* search.

For each of these algorithms, feel free to set a reasonable execution limit -- e.g., quit after some maximum number of nodes have been expanded. Take care to avoid getting stuck in infinite loops. For greedy best-first and A* search, use the two heuristics defined in this lecture:

h1 = number of misplaced tiles
h2 = sum of Manhattan distances between every tile's current and desired position

For each problem instance in this file and each search algorithm, report the following:

Number of steps (path cost) of the solution (if found).
Number of nodes expanded.
Maximum tree depth searched.
Maximum size of the fringe.

Next, generate 50 random 8-puzzle instances by starting from the goal state and shuffling for some sufficiently large number of steps. Solve each of these instances using the A* algorithm with heuristics h1 and h2 and report the averages of the four above performance statistics. Analyze the dependence of the number of nodes expanded on solution depth (a scatter plot would be a good tool for this purpose).

Problem 2: n-queens

Implement hill-climbing search to generate legal n-queens configurations. Use the formulation from this lecture: start by placing a queen in a random location in each column, and at each step, try to move a queen within its column to reduce the number of conflicts. Experiment with a few simple ways of selecting the successor state and escaping local minima until you get an algorithm that works reasonably well. Report on your implementation choices and their relative performance.

Start with n = 4 and keep increasing n as far as you can (the values don't have to be consecutive). For each n you tried, report the average number of uphill moves and restarts needed to successfully generate an n-queens instance. Empirically, how does the complexity of your implementation scale as a function of n? Once again, a scatter plot would be a good way to answer this question.

Problem 3: Sudoku as a Constraint Satisfaction Problem

Implement backtracking search with forward checking to solve Sudoku puzzles (see this lecture). Use the minimum remaining values (MRV) heuristic for choosing the next variable to assign. Forward checking should take the following simple form: every time you assign a value to a variable, eliminate that value from the list of possible values for the variables in the same row, column, and 3x3 unit. If the list of possible values for any variable becomes empty, report failure and backtrack.

Apply your algorithm to the Sudoku puzzles in this file. For each puzzle, report the solution and the number of variable assignments attempted in the course of finding the solution.

Finally, try to "break" your algorithm by replacing the MRV heuristic by something "dumber" (fixed order of assigning variables, random order, maximum remaining values). How does this affect the number of attempted assignments? (As with Problem 1, feel free to cut off the search after some maximum number of attempted assignments.)

For Extra Credit

Feel free to try out and report on various extensions or improvements based on information from the textbook or from the Web. Here are some possible ideas:

Test alternative heuristics for the 8-puzzle (e.g., see questions 3.31 and 3.32 in the 3rd edition of the textbook).
Tackle the 15-puzzle or the 24-puzzle.
Solve n-queens by systematic search or constraint satisfaction instead of local hill-climbing search.
Try to solve Sudoku using local search instead of constraint satisfaction.

The amount of credit will be determined based on multiple factors (difficulty level of task, quality of results, quality of writeup, amount of extra credit attempted by other students in the class).