Assignment1

The 8 Puzzle

Due date:
Feburary 1. 11:59pm.

Problem Description

The 8 puzzle is a time-honored kid's game. The idea is that there are 8 tiles numbered 1-8 on a 3x3 grid. There is one space open. For instance, the grid might look like:
9 2 5
8 1
6 3 4
The play proceeds by moving a tile for an occupied space to an unoccupied space. For example, from the above configuration, the following are all of the possible grids after one move (the yellow tile is the one that moved):
9 2 5
8 1 4
6 3
9 2
8 1 5
6 3 4
9 2 5
8 1
6 3 4

There is a typo in all of the pizzles above. "9" should be "7".

The goal of the 8-puzzle is to move tiles until a desired pattern in created. Of course, the usual desired pattern is to put all of the numbers in order starting at the top left and leaving the space at the bottom right. E.g.,

1 2 3
4 5 6
9 8

Do

Write a program that reads for a text file a starting state. For example, this file holds a description for the first table above. I used -1 to indicate the empty spot.

Your program must represent the board in a way such that it can be easily replicated and can hold the replicas in memory. Call this representation a state. (For instance, you might create a Java class to hold a 2-dimensional array of integers.)

Your program must be able to, given a state, determine all of the states that can be achieved in a single move.

Your program must be able to randomly select a move from the possible moves.

Your program must be able to determine when a state is the desired state.

Handle any square grid variant of the 8-puzzle. For instance, the 3 puzzle on a 2x2 grid or a 15 puzzle on a 4x4 grid.

Be able to not move to states it has recently visited. (For example, not move back to a state it was in for the past 3 moves (or 5 or N)).

Hand in:

  1. 50 points -- Programming: An executable version of your program.
  2. 50 points -- Analysis:
    1. Samples of the start states for 3, 8, 15 and 24 puzzles.
    2. A description of the behavior of your randomly moving program for solving 3, 8, 15, and 24 puzzle.
    3. A statement of the size of the state space for each of the above puzzles.
    4. An analysis of the effect of preventing repeated states. For example, does it make find a solution quicker? If yes, in what way?
    5. Not revisiting states can cause the program to get stuck (there are no states it can visit). Analyze why this occurs and what can you do. Does the size of the puzzle affect this analysis?
    6. Sugestions for how you might make the program find a solution even faster.