Maze solver: A nifty assignment for CS2, AP CS AB, or Intro AI

Don Blaheta

Knox College

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.

The assignments

Extra info about this assignment: