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:

• You will need to decide on a heuristic function. Remember that a good heuristic is quick to calculate and comes close to the true distance to the goal without going over.
• You will also need to decide how you want to represent moves.

Python notes:

• If you want to put Puzzle objects into sets or use them as dictionary keys, remember to overload the __hash__ and __eq__ and __ne__ methods of the Puzzle class.

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,
            print
        print

    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, ' ']])
    puzzle.display()
    
    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)
        time.sleep(1)
        puzzle.display()

if __name__ == '__main__':
    main()