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.