Assignment: 8-Puzzle

Note to self: Next time, combine parts 3 and 4 into one part. That's how I assigned it anyway, but having it broken out into multiple parts was confusing.

The goal of this assignment is to implement regular iterative deepening and A* search for the 8-puzzle. We'll discuss what all of these ideas mean eventually, but we'll start Part 1 right away.

Getting started

First grab puzzle8.py, which contains some useful functions for managing the 8-puzzle. DO NOT MODIFY IT. This code is patterned heavily after a library distributed from the textbook website, which describes the approach used as follows:

The representation of states is not the obvious one (a 3x3 array), but it is both efficient and fairly easy to manipulate. We represent each tile as an integer from 0 to 8 (0 for the blank). We also represent each square as an integer from 0 to 8, arranged as follows:

     0 1 2
     3 4 5
     6 7 8

Finally, we represent a state (i.e., a complete puzzle) as the sum of the tile numbers times 9 to the power of the tile's square number. For example:

     1 2 3                          1*9^0 + 2*9^1 + 3*9^2
     8 . 4 is represented by:    + 8*9^3 + 0*9^4 + 4*9^5
     7 6 5                        + 7*9^6 + 6*9^7 + 5*9^8 = 247893796

There are a number of functions in puzzle8.pyc that you will likely found useful. Start Python up interactively, import puzzle8, then type help(puzzle8). Play around at the command prompt with these functions to get a sense of how they work.

What your code will ultimately do

The goal state that you are trying to achieve is the following:

    1 2 3
    8 . 4
    7 6 5

So for example, if the initial state was

    1 . 2
    8 4 3
    7 6 5

The code that you write should return a list containing [from, to] pairs indicating where to move the blank square. Since you will not worry about keeping track of duplicate states, if there is no solution to be found, your code will just run forever. So for the above example, the solution might appear as

[[1, 2] [2, 5] [5, 4]]

Your assignment, part 1

Implement the following two heuristic functions:

numWrongTiles(state) - returns the number of misplaced tiles for the indicated state
manhattanDistance(state) - returns the Manhattan distance for the misplaced tiles for the indicated state

You won't need these heuristics until part 3 of this assignment, but this is good way of getting used to the puzzle8 code that I am providing.

Put your code in a file called search.py, and submit via Moodle.

Your assignment, part 2

Write the function

itdeep(state)

which uses iterative deepening to return the list describing the path that the blank square takes to reach a solution (as demonstrated earlier).

You may use helper functions if you like.

Any time that you need to expand a node, you should use the puzzle8.neighbors(square) function to determine how to do so. If at any time your algorithm must make a choice as to which state to examine next, you should choose the one that appears first in the neighbors list. This way, everyone in the class should get exactly the same answers even though there are multiple possible solutions.

You should not keep track of duplicate states. If the algorithm checks a state more than once, then so be it.

[Addition to the assignment, which would be great by tonight, but since I added it at the last minute, otherwise include it in the experiments for part 4]

Iterative deepening is not significantly slower than regular breadth-first or depth-first search. To see this, run a few experiments where you time how long iterative deepending takes to run the last iteration through, vs how long it takes in total to run repeatedly in getting down to that level. The difference in time should not be dramatic. Submit the results of your experiments in comments associated with your code.

Your assignment, part 3

Write the function

astar(state,heuristic)

which uses A* search with the provided heuristic to perform the same task as part 2 above. The details in part 2 regarding helper functions, order of node expansion, and duplicate states apply here as well.

In order to implement A* search, you'll need to use a priority queue. The easiest way to go is to use Python's built-in priority queue. The catch is that you'll want to put some kind of arbitrary object into the priority queue, yet Python needs to know how to compare two of these objects for purposes of determining which one is "smaller." To do that, override the built-in __cmp__ method. Here is a quick example:

class HeapItem:
    def __init__(self,name,rank):
        self.name=name
        self.rank=rank
    
    def __cmp__(self,other):
        '''__cmp__ is supposed to return a negative number if self is
        "smaller" than other, 0 if equal, and a positive number if
        "greater."'''
        return  self.rank-other.rank

Your assignment, part 4

Run some experiments with some random states. In comments at the end of search.py, describe your experiments and how iterative deepening, A* with the first heuristic, and A* with the second heuristic compare. You might find it useful to add print statements to your functions so that you now how they're doing. For example, add a print statement to your iterative deepening code so that you know what level it is working on, and add a print statement to your A* search to know what the current "f" value is. You should remove those print statements before submitting your work, but they're likely helpful for experiments and for debugging.

Make sure to do the experiments I added to part 2, if you haven't done them already.

Turn in your code via Moodle when done.