A* search in sliding-block puzzles

A sliding-block puzzle is a square grid of numbered blocks that can slide vertically and horizontally, like this:

The goal of this assignment is to get the numbers of the puzzle back into order using A* search.

Here is the A* algorithm:

A*(start state, goal state)
make finished an empty set
make frontier an empty priority queue
note the path to start is an empty list
note the priority of start is start.h(goal)
add start to frontier
until frontier is empty
    take the min-priority parent off frontier
    stop if parent is the goal
    otherwise add parent to finished
    for each move from parent
        let child be the neighbor of parent via move
        if child is in neither frontier nor finished
            add child to frontier
        if the best path to child so far is through parent
            note the path to child is the path to parent followed by move
            note the priority of child is the number of moves in its path plus child.h(goal)

To apply this algorithm to a sliding-block puzzle, think of puzzle configurations as states. The "children" of a configuration are the ones that can be reached by moving one block into the empty space. The heuristic function h estimates the number of moves it will take to get to the goal configuration.

A Puzzle class and an Agent class have been started for you below. Once you complete the indicated methods, you will be able to watch a puzzle being solved. Adjust the height of your console window to match the puzzle height, so that each display appears in the same place.

Algorithm notes:

Python notes:

import copy
import time

class Puzzle(object):
    """A sliding-block puzzle."""
    def __init__(self, grid):
        """Instances differ by their number configurations."""
        self.grid = copy.deepcopy(grid) # No aliasing!
    def display(self):
        """Print the puzzle."""
        for row in self.grid:
            for number in row:
                print number,

    def moves(self):
        """Return a list of possible moves given the current configuration."""
        # YOU FILL THIS IN
    def neighbor(self, move):
        """Return a Puzzle instance like this one but with one move made."""
        # YOU FILL THIS IN

    def h(self, goal):
        """Compute the distance heuristic from this instance to the goal."""
        # YOU FILL THIS IN

class Agent(object):
    """Knows how to solve a sliding-block puzzle with A* search."""
    def astar(self, puzzle, goal):
        """Return a list of moves to get the puzzle to match the goal."""
        # YOU FILL THIS IN

def main():
    """Create a puzzle, solve it with A*, and console-animate."""
    puzzle = Puzzle([[1, 2, 5], [4, 8, 7], [3, 6, ' ']])
    agent = Agent()
    goal = Puzzle([[' ', 1, 2], [3, 4, 5], [6, 7, 8]])
    path = agent.astar(puzzle, goal)
    while path:
        move = path.pop(0)
        puzzle = puzzle.neighbor(move)

if __name__ == '__main__':