CS 331 Assignment #1: Uninformed and Informed Search

Out: April 6, 2012
Due: April 18, 2012 at 17:00:00
Type: Team Assignment (Groups of 2 max)

Description

The 8-puzzle consists of numbered tiles (1 through 8) and a special blank tile on a 3x3 grid. You can slide any tile adjacent to the blank tile into the blank tile's spot. The goal of the 8-puzzle is to reach the goal state from the start state. The figure below gives an example of the start state and the goal state. Note that you may not be able to get to the goal state with some start states.

In this assignment, you will write code to solve the 8-puzzle. The algorithms you will implement are breadth-first search, depth-first search, iterative deepening depth-first search and A-star search for a sliding tile 8-puzzle. Your code will print out the solution path from the start state to the goal state or a no solution found message if no such path exists. Your code will also print out the number of search nodes expanded.

Tile Puzzle File Format

The file format for the tile puzzle state is simply a set of comma-separated numbers arranged as they are in the tile puzzle. For example, the tile puzzle state

1 2 3
4 5 6
7    9

is represented in a text file as:

1,2,3
4,5,6
7,0,9

We use the number 0 to denote the blank space in the tile puzzle state. This decision was due to problems with parsing blank spaces. Your program will take as input a starting state file and a goal state file. Your code must be able to read the start and goal state files. We will only be marking your code on 3x3 puzzles.

Requirements

You may the following programming languages: Java, C, C++. If you use any other programming language, it must be available on the ENGR systems and you must contact the Teaching Assistant for approval. Your code should take the following command line arguments:
< initial puzzle state file > < goal puzzle state file > < mode > < output file >

The mode argument is either:

I. Uninformed Search

You will implement Breadth-First Search, Depth-First Search and Iterative-Deepening Depth First Search. Use the pseudocode for the GraphSearch function and the Expand function in either my slides or the textbook to help you design the algorithm. If you don't follow the GraphSearch and Expand pseudocode, your algorithms may not work properly.

There are specific requirements regarding the uniformed search algorithms that you must follow in this assignment:

  1. When generating successors for a state, do so in the order of moving the blank space up, right, down, and left. As an example, suppose we are at:

    1 2 3
    4 0 5
    6 7 8

    The successors (in order) are:

    1 0 3     1 2 3     1 2 3     1 2 3
    4 2 5     4 5 0     4 7 5     0 4 5
    6 7 8     6 7 8     6 0 8     6 7 8

  2. You will need a counter for the number of nodes expanded. Update this counter after you remove the node from the fringe and just before you call the expand function (note that if it is a goal node, you don't need to expand it and hence don't count the goal node as an expanded node). At the end of the graph search, print out the number of nodes that were expanded.
  3. You need to print the solution path which shows how to move the tiles from the start state to the goal state. Please print this to the screen and to an output file. Make sure it is in the right order!

II. Informed Search

In this part, you will implement A-star search. As with uninformed search, there are specific requirements that you must follow:

Test Files

There are three test cases that you should run your algorithm on. These tests and the corresponding files are:

  1. Test1: testStart1.txt, testGoal1.txt
  2. Test2: testStart2.txt, testGoal2.txt
  3. Test3: testStart3.txt, testGoal3.txt

Record how many nodes were on the solution path and how many nodes were expanded for each of BFS, DFS, ID-DFS and A-Star Search. You will need to set a max depth for ID-DFS. Try to make the max depth as large as possible.

The Assignment Report

Your assignment report should be about 1-2 pages and should not exceed 2 pages. I accept pdf or doc files (pdf is preferred). For your report, you will do the following sections:


Hints

  1. You will need a closed list to keep track of the states that you have already visited. Use a hash table for this.
  2. If you are using Java and running out of memory, add the -mx1024M flag to the Java Virtual Machine (this is done through Eclipse. See me if you don't know how to do this).

Hand in

Please hand in all of your source code and your report. Also include a text file called team.txt which lists the names of the members of your team. Zip everything up with a zip program. To hand in your assignment, go to the TEACH electronic handin site: https://secure.engr.oregonstate.edu:8000/

  1. Login to the TEACH system
  2. Click on the "Submit Assignment" link on the left hand side
  3. Select ProgrammingAssn1 from the dropdown menu, hit submit query
  4. For redundancy, leave a web comment stating who your team members are. If I don't know who is on your assignment team, they won't get credit.
  5. Enter the path of your zip file. Hit Submit Query to hand everything in.

Grading Criteria

The assignment is out of 50. Note that the bulk of the marks are allocated to your report. The code is intended to help you produce results for the experiments. We will run the code to make sure it works.