| Summary | Maze solver --- CS2 students implement a given algorithm that uses queues or stacks to manage a search through a given maze, to find whether it's solvable or not. Can be easily adapted for use with GridWorld API; and a more complex version implementing A* is appropriate for an intro AI course. |
| Topics | Selecting data structures; working with several interacting objects. Uses 2D array, stack, and queue, although easily adapted to use stacks only, and see below about GridWorld. |
| Audience | The main assignment is mid-late CS2, but includes many elements outside the AP subset; however, it is fairly easy to adapt into a non-Bug-based GridWorld project appropriate for AP CS AB. Another variant described in detail would be appropriate for an intro AI course. |
| Difficulty | Intermediate; in a semester-length CS2 course, probably a 2-week project. |
| Strengths | Encourages creativity in implementation without going overboard. Leads naturally into discussions about depth-first and breadth-first search. |
| Weaknesses | Some of the first pieces to be implemented are big stoppers on the later stuff, despite not being very important pedagogically. I include one way to work around this problem. |
| Dependencies | Main assignment requires stacks, queues, 2D arrays, and familiarity with reading pseudocode and the java documentation. Students must handle several classes that interact with each other. As written, requires some knowledge of GUI writing (eg Swing) and enumerated types, although these are not intrinsic to the main assignment and can be removed. |
| Variants | GridWorld, CS262/AI. See below. |
Solving a maze requires a good algorithm; otherwise you just wander around aimlessly. It requires good data management, to keep track of where you've been and where you need to explore (and in what order). And it's fun, naturally graphical, and something you can easily show off to friends and family.
The basic algorithm is a real, non-contrived example of using a stack or queue---and actually works differently depending on which is used, providing a natural segue into depth-first and breadth-first tree (graph) search. Inputting, representing, and displaying the maze itself is also a challenge, as is marking the already-explored squares to prevent infinite loops; making all the pieces talk to each other and work together is a significant portion of the project, and just about right for a mid- to late-term CS2 student.
Since the assignment is written for a 2D maze, with walls as thick as the corridors (à la Rogue or NetHack), this assignment is also perfectly amenable to a GridWorld implementation in an AP CS AB course.
The same framework lends itself to A* best-first search. This version is more appropriate for an intro AI course (or a CS262c-style combined course); but in that environment, it provides a good hands-on demonstration of heuristics and the concepts of admissibility and informedness.
Extra info about this assignment: