Islands vs. Mazes

Two Faces of Recursive Backtracking — Same Algorithm Skeleton, Different Worlds

← back to Saga Index   •   Open Maze 1 →

The big idea: The island saga and the maze apps run the exact same algorithmic skeleton — try an option, recurse, undo if stuck — in two completely different problem domains. This page explains what they share, where they diverge, and which context is better suited to teaching which concept. Use it as a study guide before or after exploring both apps.

1. The Shared Skeleton — One Algorithm, Two Costumes

Strip away the domain details and both programs run the same four-step loop:

The Universal Pattern
  1. Choose a candidate next step.
  2. Commit to it (mark as active).
  3. Recurse — try to complete from here.
  4. If recursion fails → undo the commit and try the next candidate.
🏝️ Island version
  1. Collect valid orthogonal neighbors of the current island.
  2. Add one cell to the island.
  3. Recurse: keep growing from that cell.
  4. If target size not reached from here → remove the cell, try another neighbor.
🧩 Maze version (generate)
  1. Collect unvisited grid neighbors of the current cell.
  2. Carve the shared wall; mark the neighbor as visited.
  3. Recurse: keep carving from the neighbor.
  4. All neighbors exhausted → return (automatic backtrack via the call stack).

Side-by-side pseudocode — the parts in purple are identical; the colored lines are domain-specific substitutions:

🏝️ Island.grow( )
function grow(island, targetSize) { if (island.size === targetSize) return true; candidates = getValidNeighbors(island); if (randomize) shuffle(candidates); for each candidate: island.addCell(candidate); // commit if (grow(island, targetSize)) return true; island.removeCell(candidate); // undo return false; // backtrack }
🧩 SWMaze._generateDFS( )
function _generateDFS(r, c) { cell(r,c).visited = true; // commit up front dirs = shuffle(ALL_DIRECTIONS); for each dir in dirs: if (!neighbor.visited): carveWall(r,c, neighbor); // commit _generateDFS(neighbor); // undo is implicit — just don't recurse again // all dirs tried → return (backtrack via call stack) }
Key insight: In the island, undo is explicit — removeCell() physically removes the cell. In maze generation, undo is implicit — there is nothing to remove because the wall was already carved and the cell was already marked visited. The "backtrack" is simply the function returning, letting the for-each loop try the next direction. Both are backtracking; one just has more visible footprints.

2. What They Share

  • ✓ Recursive DFS with backtracking — the call stack is the path memory. When a recursive call returns false (or simply returns), the algorithm has "backed up."
  • ✓ Grid / cell model — both live on a 2D grid addressed by (row, col) pairs. Both use the same SWGrid / SWColor / SWPoint rendering infrastructure.
  • ✓ Direction arrays — both iterate over neighbor offsets (DR, DC), optionally shuffled, to decide which cell to visit next.
  • ✓ Pre-recorded step queue — neither algorithm draws directly. Both record every decision into a step queue first, then the draw() loop plays it back one frame at a time.
  • ✓ Randomize toggle — shuffle the direction / candidate list for organic variety; leave it in fixed order for deterministic, repeatable results.
  • ✓ ADD/BACKTRACK log — every step is visible in a scrollable breadcrumb panel and counted in a live Recursion Cost display, so you can measure the algorithm's efficiency numerically.
  • ✓ Java mirror — both sets of JavaScript classes are deliberate ports of Java source studied in APCS A (Island.java, RecursiveIslandDriver.java), reinforcing the same logic in two languages.
  • ✓ Base case — island: size === targetSize; maze solver: r === endRow && c === endCol. In both, reaching the goal returns true immediately — no more recursion.

3. Where They Differ

Dimension 🏝️ Islands (Stages 3–7) 🧩 Mazes (Maze 1 & 2)
Problem domain Grow an organic blob of cells to a target size on an open ocean. (Generate) carve a perfect maze; (Solve) navigate S → T through it.
Number of algorithms One (growth / backtrack). BFS appears only as a pre-check in Stage 5. Two back-to-back: DFS generation, then separately DFS solving — plus a BFS solution highlight for contrast.
What "commit" means Add a cell to the island data structure. removeCell() explicitly undoes it on backtrack. Mark a cell visited and carve its wall. The wall stays carved — there is nothing to undo.
Backtrack visibility Moderate — backtracked cells turn a dim color and are removed from the island. High — solver dead ends flash red then gray; multiple wrong corridors accumulate on screen, making the cost of backtracking viscerally obvious.
Shape of success An irregular connected blob: no particular start/end, just a counted number of cells. A single linear path from corner to corner; the solution route lights up in gold.
Obstacle handling Ocean pits (Stages 4–7) are hard blocks; the algorithm routes around them by simply having fewer valid candidates. Walls between cells are the obstacles; they are carved away during generation, leaving open passages the solver can travel.
Separation constraint Stage 6b: 8-direction check prevents islands touching even diagonally — adds significant backtrack cost. No separation concept; the maze is a single connected structure by design.
BFS comparison Implicit only (Stage 5 pre-check uses BFS to verify reachability before recursing). Explicit: View Solution runs BFS to highlight the shortest path in gold before the DFS solver runs, directly demonstrating the DFS vs. BFS tradeoff.
Stage-by-stage complexity 7 stages, each adding one concept. The complexity curve is gradual and deliberate. One app with all concepts present at once. Higher density; better as a capstone after the island saga.
Connection to Java source Direct: Stage 7 mirrors Island.java and Coordinates.java method-for-method. Indirect: SWMaze is modeled on the style of SWIsland but has no Java counterpart in the APCS A project.

4. Pedagogical Strengths — What Each Context Teaches Best

🏝️ Why the Island is a great teaching tool
  • Intuitive domain. "Grow a blob on a grid" needs no explanation — students immediately understand the goal. The algorithm feels like a helper, not the main character.
  • Explicit undo. removeCell() makes backtracking physically visible: a cell disappears from the island. Students can point to exactly what was undone, which maps directly to "pop the call stack" in the mental model.
  • Graduated complexity. Seven stages build on each other — pits, cost metrics, multiple islands, separation rules, OOP refactoring. Each stage's change is a single sentence.
  • Java mirror. Stage 7 replicates Island.java line-for-line. A student reading both can see that Java and JavaScript solve the same problem identically.
  • Infinite patience. Because there is no single "right" shape, every run produces an interesting result and students are never "wrong."
🧩 Why the Maze is a great teaching tool
  • Backtracking drama. Dead-end corridors that flash red and accumulate on screen make the cost of wrong choices viscerally obvious in a way the island rarely achieves. Students feel the frustration of dead ends.
  • DFS vs. BFS contrast. Pressing View Solution shows BFS finding the shortest path in one click, then Solve Maze shows DFS wandering before finding a path. No other demo in the saga makes this distinction so concrete.
  • Two-algorithm story. Generation and solving use the same skeleton for different purposes, proving the pattern is truly general — it is not "the island algorithm" but "the DFS algorithm."
  • Perfect maze guarantee. Because a perfect maze has exactly one solution, the solver must encounter dead ends to find it. Backtracking is not optional — it is guaranteed.
  • Transfer signal. After spending weeks on islands, recognizing the same structure in a completely different domain is a powerful metacognitive moment — "I already know how to read this code."

5. Sequencing: Which Should Come First?

The saga is designed to be explored in order — islands first, maze second. Here is why that sequence works:

  1. Islands build confidence. The first time a student sees recursive backtracking it should feel manageable. Growing a blob is lower-stakes than navigating a maze — there is no "wrong" shape, and the undo operation is concrete and visible.
  2. Stages 1–2 provide a manual baseline. Students click cells by hand in Stage 2 before the algorithm takes over in Stage 3. This means they understand what the algorithm is computing before they see how it is computed recursively.
  3. Each island stage adds one idea. By the time students reach Stage 7, they have seen the algorithm add pits, add cost metrics, grow multiple islands, and move into a class — all incrementally.
  4. The maze is the capstone. After absorbing seven island stages, seeing the same skeleton in a maze generates a "transfer" moment. The student is not learning a new algorithm — they are recognizing an old friend in new clothes.
  5. DFS vs. BFS lands harder on familiar ground. The contrast between View Solution (BFS) and Solve Maze (DFS) is the most important new concept the maze introduces. It resonates most strongly once the student already deeply understands DFS from the islands.
Recommended sequence
1 Island 1–2 — manual baseline, grid / coordinate model
2 Island 3 — watch the algorithm run; log ADD & BACKTRACK
3 Islands 4–5 — pits, cost metrics, backtrack ratio
4 Islands 6a–6b — multiple islands, separation rule
5 Island 7 — OOP refactoring; read the Java source alongside it
6 Maze 1 — capstone: same DFS, new domain, DFS vs. BFS
7 Maze 2 — compare/contrast one-color addition
Tip for instructors: If time is limited, skip islands and go to Maze 1 directly — the maze is self-contained and the "Build then Solve" sequence tells the complete DFS story in one session. But students who have done the islands will connect more deeply and arrive with a mental model already in place.

6. Backtrack Cost — Are They Comparable?

Both apps display a Recursion Cost panel with a backtrack ratio. But the numbers mean different things:

🏝️ Island backtrack ratio
Measures how hard the algorithm worked to hit the target size. A ratio near 0 % means the island grew almost perfectly; a high ratio means many candidate cells were tried and removed before enough dead ends cleared. Pit density is the primary driver: a pitted ocean forces the algorithm into corners it must escape from.
🧩 Maze backtrack ratio
Measures how many wrong turns the DFS solver took before reaching T. In a perfect maze on a 20 × 14 grid, a ratio of 100–200 % is normal (the solver visits more dead-end cells than solution cells). Randomize OFF often finds a shorter route than Randomize ON on the same maze — never shorter than BFS's gold path, but sometimes surprisingly close.
What both ratios teach: Every extra backtrack is a recursive call that returned false. A ratio of 50 % means half the total work was "wasted" exploring paths that failed. That is not a bug — it is the algorithm demonstrating exactly why we need backtracking: we cannot know which path is right without trying it.

7. Questions to Think About

Use these to drive a class discussion or written reflection:

Q1. The island uses removeCell() when backtracking. The maze generator does not remove anything — it just returns. Are both of these really "backtracking"? What is the definition of backtracking that covers both?
Q2. In the island saga, Randomize OFF means candidates are tried in a fixed sorted order. In the maze, Randomize OFF means directions are tried N → S → E → W. What do you predict the solver's path looks like with Randomize OFF? Run it and check.
Q3. View Solution (BFS) frequently finds a shorter path than Solve Maze (DFS) on the same maze. Can you construct an example where they follow exactly the same route? What would the maze topology have to look like for that to happen?
Q4. In Stage 6b, switching from a 4-direction to an 8-direction separation check noticeably raises the backtrack ratio. Does the same kind of constraint tightening exist anywhere in the maze? What would be the maze equivalent of "no diagonal touching"?
Q5. The maze generator is guaranteed to visit every cell before finishing. The island may not visit every cell, even if the target size equals the total grid area. Why the difference?
Q6. Maze 2 adds one color (orange resume junction) to make a single algorithmic moment more visible. Could you add a similar one-color enhancement to any island stage? What moment would you highlight, and what color would you use?
Q7. Both apps let you save a PNG image at any point. If you save a maze mid-solve (lots of red dead ends visible) and then reset and solve again with Randomize toggled — is it possible to get a solve with fewer red cells than the BFS gold path has cells? Why or why not?

8. Explore Both

🏝️ Island Saga

Seven stages building from a single cell to a fully object-oriented multi-island recursive generator with cost metrics and Java parity.

Open Saga Index →
🧩 Maze 1 — Classic DFS

DFS Build + DFS Solve + BFS highlight. The clearest backtracking animation in the saga. Three algorithms, one grid.

Open Maze 1 →
🧩 Maze 2 — Resume Junction

Identical to Maze 1 plus one orange color cue marking the exact cell where DFS picks back up after each backtrack. Open side-by-side with Maze 1 to compare.

Open Maze 2 →