Introducing A* Search Algorithm I created a group lab where one student makes a random maze generator, one student makes a corresponding maze solver, and the last student calls the methods created by both students and creates an animated maze walker.  Currently, the students are told to use Prim's algorithm for maze generation, though I am open to any of these other algorithms as well:


Kruskal's
Recursive Backtracker
Aldous-Broder
Growing Tree
Hunt-and-Kill
Wilson's
Eller's
Cellular Automaton
Recursive Division
Sidewinder
Binary Tree


In practice, about 10% of students use other algorithms besides Prim's.

For the maze solver, I teach my students about breadth-first search, and for next year, I would like to expand this a bit and teach them about depth-first search as well.  However, I would also like to give them a real shot at A*, since it is a much, much better algorithm.

What I am looking for is how to get them to see the difficult piece of A*: how a heuristic concretely fits within the algorithm and gets us to a solution.  My target is for 25% of the students to choose to use A* next year.  I don't care which heuristics we use, but I would like them to see something that they can understand quite concretely (as I believe firmly in engendering concrete understandings before abstract understandings) and I would like them to understand the difference between an admissible and an inadmissible heuristic.

For context, I do this all during my AP Computer Science class, so it is in Java, however the question is really about A*, so I am not adding those tags in.

Edit

Mike Zamansky posted a response to this question on his incredible blog and it knocked my socks off! I'm going to integrate a lot of his approach into my own next year.  I would accept his answer, but it's not on this site, so the best I can do from here is link to it.
I usually teach Uniform Cost Search (UCS) before A*, since it is basicaly A* without the heuristic (and it reduces to BFS when all costs = 1, so it is pretty straightforward to explain). Then I teach A* and show them animated examples of the explored nodes in comparison to UCS (here you can find excellent interactive examples). 

In this step, one analogy I like to use is about mazes: Imagine yourself inside a maze from which you must find the exit, but you have no idea where it is. This is UCS. Now imagine there is no ceiling in the maze (like the Harry Potter one), and there is a tower in the exit which can be seen from anywhere in the maze. Now you can make more informed decisions in your search, biasing choices in that direction. This is A*.