Maze Solving with DFS

Grid search with visited cells and path backtracking

Explore one route as deeply as possible

Depth-first search enters an open neighboring cell, marks it visited, and continues from there. Walls, boundaries, and visited cells are rejected. The visited set prevents cycles, while a separate path stack records the cells on the current candidate route.

Dead ends trigger an undo

If a cell has no unvisited open neighbor, remove it from the active path and return to the previous cell. That previous recursive call can then try another direction. Reaching the goal stops the search with the current path intact.

The player uses a fixed 5 by 5 maze. Amber cells form the current DFS path, previously visited cells remain visible, dark cells are walls, and the successful start-to-goal route turns green.

🐭

🚩

Start at (0, 0) and search for goal (4, 4).

1function solveMaze(grid: number[][], sr: number, sc: number, gr: number, gc: number) {
const visited = new Set<string>();
const path: [number, number][] = [];
const dfs = (r: number, c: number): boolean => {
  const key = r + ',' + c;
  if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return false;
  if (grid[r][c] === 1 || visited.has(key)) return false; // wall / visited
  visited.add(key);
  path.push([r, c]);                     // move to (r,c)
  if (r === gr && c === gc) return true;  // reach the goal
  for (const [dr, dc] of [[1,0],[0,1],[-1,0],[0,-1]]) { // four directions
    if (dfs(r + dr, c + dc)) return true;
  }
  path.pop();                             // dead end: backtrack one cell
  return false;
};
dfs(sr, sc);
return path;
19}

Start(0,0)

Goal(4,4)

Current cell(0,0)

Path length1

Visited1

1 / 19

One path, not necessarily the shortest

With a visited set, DFS processes each grid cell at most once, taking O(RC) time and space. It finds a path when one exists, but not necessarily the shortest path. Breadth-first search is the standard unweighted-grid choice when minimum step count matters.

Invariant: the active path is always a simple route from the start to the current cell, and every removed cell remains visited so the search cannot loop.

Compare grid backtracking with board constraints in N-Queens and explicit choices in Subsets.

Algorithm Visualizer

Maze Solving with DFS

Explore one route as deeply as possible

Dead ends trigger an undo

One path, not necessarily the shortest