1068 Intermediate

1068-maze-solver — Maze Solver

Functional Programming

Tutorial

The Problem

Path finding in a 2D grid is a fundamental robotics and game AI problem: find a path from start to end while avoiding walls. DFS backtracking finds any path; BFS finds the shortest path (by number of steps). Both are foundational to robot navigation, video game pathfinding, and circuit board routing.

This example implements both DFS (finds a path, not necessarily shortest) and BFS (finds the shortest path), demonstrating the fundamental algorithmic trade-off between the two search strategies.

🎯 Learning Outcomes

• Implement DFS backtracking for 2D grid path finding

• Implement BFS for shortest-path grid traversal

• Use a visited matrix to prevent revisiting cells

• Reconstruct the path by tracking parent pointers in BFS

• Understand when DFS vs BFS is appropriate

Code Example

#![allow(clippy::all)]
// 1068: Maze Solver — Backtracking on 2D Grid

use std::collections::VecDeque;

const DIRS: [(i32, i32); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];

// Approach 1: DFS backtracking
fn solve_maze(
    maze: &[Vec<i32>],
    start: (usize, usize),
    end_: (usize, usize),
) -> Option<Vec<(usize, usize)>> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut path = Vec::new();

    fn dfs(
        r: usize,
        c: usize,
        end_: (usize, usize),
        maze: &[Vec<i32>],
        visited: &mut Vec<Vec<bool>>,
        path: &mut Vec<(usize, usize)>,
        rows: usize,
        cols: usize,
    ) -> bool {
        if (r, c) == end_ {
            path.push((r, c));
            return true;
        }
        if maze[r][c] == 1 || visited[r][c] {
            return false;
        }
        visited[r][c] = true;
        path.push((r, c));
        for &(dr, dc) in &DIRS {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
                if dfs(
                    nr as usize,
                    nc as usize,
                    end_,
                    maze,
                    visited,
                    path,
                    rows,
                    cols,
                ) {
                    return true;
                }
            }
        }
        path.pop();
        false
    }

    if dfs(
        start.0,
        start.1,
        end_,
        maze,
        &mut visited,
        &mut path,
        rows,
        cols,
    ) {
        Some(path)
    } else {
        None
    }
}

// Approach 2: BFS for shortest path
fn solve_maze_bfs(
    maze: &[Vec<i32>],
    start: (usize, usize),
    end_: (usize, usize),
) -> Option<Vec<(usize, usize)>> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent = vec![vec![(usize::MAX, usize::MAX); cols]; rows];
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start.0][start.1] = true;

    let mut found = false;
    while let Some((r, c)) = queue.pop_front() {
        if (r, c) == end_ {
            found = true;
            break;
        }
        for &(dr, dc) in &DIRS {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
                let (nr, nc) = (nr as usize, nc as usize);
                if maze[nr][nc] == 0 && !visited[nr][nc] {
                    visited[nr][nc] = true;
                    parent[nr][nc] = (r, c);
                    queue.push_back((nr, nc));
                }
            }
        }
    }

    if !found {
        return None;
    }
    let mut path = vec![end_];
    let (mut r, mut c) = end_;
    while (r, c) != start {
        let (pr, pc) = parent[r][c];
        path.push((pr, pc));
        r = pr;
        c = pc;
    }
    path.reverse();
    Some(path)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn test_maze() -> Vec<Vec<i32>> {
        vec![
            vec![0, 0, 1, 0, 0],
            vec![0, 0, 0, 0, 1],
            vec![1, 1, 0, 1, 0],
            vec![0, 0, 0, 0, 0],
            vec![0, 1, 1, 0, 0],
        ]
    }

    #[test]
    fn test_dfs() {
        let maze = test_maze();
        let path = solve_maze(&maze, (0, 0), (4, 4)).unwrap();
        assert_eq!(*path.first().unwrap(), (0, 0));
        assert_eq!(*path.last().unwrap(), (4, 4));
    }

    #[test]
    fn test_bfs() {
        let maze = test_maze();
        let path = solve_maze_bfs(&maze, (0, 0), (4, 4)).unwrap();
        assert_eq!(*path.first().unwrap(), (0, 0));
        assert_eq!(*path.last().unwrap(), (4, 4));
    }

    #[test]
    fn test_impossible() {
        let maze = vec![vec![0, 1], vec![1, 0]];
        assert!(solve_maze(&maze, (0, 0), (1, 1)).is_none());
    }
}

(* 1068: Maze Solver — Backtracking on 2D Grid *)

(* 0 = open, 1 = wall *)
let directions = [| (0, 1); (1, 0); (0, -1); (-1, 0) |]

(* Approach 1: Backtracking to find any path *)
let solve_maze maze start_r start_c end_r end_c =
  let rows = Array.length maze in
  let cols = Array.length maze.(0) in
  let visited = Array.init rows (fun _ -> Array.make cols false) in
  let path = ref [] in
  let rec dfs r c =
    if r = end_r && c = end_c then begin
      path := (r, c) :: !path;
      true
    end else if r < 0 || r >= rows || c < 0 || c >= cols
              || maze.(r).(c) = 1 || visited.(r).(c) then false
    else begin
      visited.(r).(c) <- true;
      path := (r, c) :: !path;
      let found = ref false in
      Array.iter (fun (dr, dc) ->
        if not !found then
          found := dfs (r + dr) (c + dc)
      ) directions;
      if not !found then
        path := List.tl !path;
      !found
    end
  in
  if dfs start_r start_c then Some (List.rev !path) else None

(* Approach 2: BFS for shortest path *)
let solve_maze_bfs maze start_r start_c end_r end_c =
  let rows = Array.length maze in
  let cols = Array.length maze.(0) in
  let visited = Array.init rows (fun _ -> Array.make cols false) in
  let parent = Array.init rows (fun _ -> Array.make cols (-1, -1)) in
  let queue = Queue.create () in
  Queue.push (start_r, start_c) queue;
  visited.(start_r).(start_c) <- true;
  let found = ref false in
  while not (Queue.is_empty queue) && not !found do
    let (r, c) = Queue.pop queue in
    if r = end_r && c = end_c then found := true
    else
      Array.iter (fun (dr, dc) ->
        let nr = r + dr and nc = c + dc in
        if nr >= 0 && nr < rows && nc >= 0 && nc < cols
           && maze.(nr).(nc) = 0 && not visited.(nr).(nc) then begin
          visited.(nr).(nc) <- true;
          parent.(nr).(nc) <- (r, c);
          Queue.push (nr, nc) queue
        end
      ) directions
  done;
  if not !found then None
  else begin
    let path = ref [(end_r, end_c)] in
    let r = ref end_r and c = ref end_c in
    while (!r, !c) <> (start_r, start_c) do
      let (pr, pc) = parent.(!r).(!c) in
      path := (pr, pc) :: !path;
      r := pr; c := pc
    done;
    Some !path
  end

let () =
  let maze = [|
    [|0; 0; 1; 0; 0|];
    [|0; 0; 0; 0; 1|];
    [|1; 1; 0; 1; 0|];
    [|0; 0; 0; 0; 0|];
    [|0; 1; 1; 0; 0|]
  |] in
  (match solve_maze maze 0 0 4 4 with
   | Some path -> assert (List.hd path = (0, 0)); assert (List.nth path (List.length path - 1) = (4, 4))
   | None -> assert false);
  (match solve_maze_bfs maze 0 0 4 4 with
   | Some path -> assert (List.hd path = (0, 0))
   | None -> assert false);

  (* Impossible maze *)
  let maze2 = [| [|0; 1|]; [|1; 0|] |] in
  assert (solve_maze maze2 0 0 1 1 = None);

  Printf.printf "✓ All tests passed\n"

Key Differences

Bounds checking: Rust uses checked_add on usize or signed arithmetic with range checks; OCaml checks bounds before casting.

Path reconstruction: Rust's DFS pushes/pops to a Vec; OCaml's uses a ref to a list with List.tl for backtracking.

BFS parent map: Rust uses HashMap<(usize, usize), (usize, usize)> for parent tracking; OCaml would use Hashtbl.

Direction encoding: Both use an array of (row_delta, col_delta) tuples — this is a universal pattern for 2D grid traversal.

OCaml Approach

let solve_maze maze start end_ =
  let rows = Array.length maze in
  let cols = Array.length maze.(0) in
  let visited = Array.make_matrix rows cols false in
  let path = ref [] in
  let dirs = [|(0,1); (1,0); (0,-1); (-1,0)|] in
  let rec dfs r c =
    if (r, c) = end_ then (path := (r,c) :: !path; true)
    else if maze.(r).(c) = 1 || visited.(r).(c) then false
    else begin
      visited.(r).(c) <- true;
      path := (r,c) :: !path;
      if Array.exists (fun (dr, dc) ->
        let nr, nc = r + dr, c + dc in
        nr >= 0 && nr < rows && nc >= 0 && nc < cols && dfs nr nc
      ) dirs then true
      else begin path := List.tl !path; false end
    end
  in
  if dfs (fst start) (snd start) then Some (List.rev !path) else None

The DFS structure is identical. OCaml's mutable path ref mirrors Rust's mutable path Vec.

Full Source

#![allow(clippy::all)]
// 1068: Maze Solver — Backtracking on 2D Grid

use std::collections::VecDeque;

const DIRS: [(i32, i32); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];

// Approach 1: DFS backtracking
fn solve_maze(
    maze: &[Vec<i32>],
    start: (usize, usize),
    end_: (usize, usize),
) -> Option<Vec<(usize, usize)>> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut path = Vec::new();

    fn dfs(
        r: usize,
        c: usize,
        end_: (usize, usize),
        maze: &[Vec<i32>],
        visited: &mut Vec<Vec<bool>>,
        path: &mut Vec<(usize, usize)>,
        rows: usize,
        cols: usize,
    ) -> bool {
        if (r, c) == end_ {
            path.push((r, c));
            return true;
        }
        if maze[r][c] == 1 || visited[r][c] {
            return false;
        }
        visited[r][c] = true;
        path.push((r, c));
        for &(dr, dc) in &DIRS {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
                if dfs(
                    nr as usize,
                    nc as usize,
                    end_,
                    maze,
                    visited,
                    path,
                    rows,
                    cols,
                ) {
                    return true;
                }
            }
        }
        path.pop();
        false
    }

    if dfs(
        start.0,
        start.1,
        end_,
        maze,
        &mut visited,
        &mut path,
        rows,
        cols,
    ) {
        Some(path)
    } else {
        None
    }
}

// Approach 2: BFS for shortest path
fn solve_maze_bfs(
    maze: &[Vec<i32>],
    start: (usize, usize),
    end_: (usize, usize),
) -> Option<Vec<(usize, usize)>> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent = vec![vec![(usize::MAX, usize::MAX); cols]; rows];
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start.0][start.1] = true;

    let mut found = false;
    while let Some((r, c)) = queue.pop_front() {
        if (r, c) == end_ {
            found = true;
            break;
        }
        for &(dr, dc) in &DIRS {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
                let (nr, nc) = (nr as usize, nc as usize);
                if maze[nr][nc] == 0 && !visited[nr][nc] {
                    visited[nr][nc] = true;
                    parent[nr][nc] = (r, c);
                    queue.push_back((nr, nc));
                }
            }
        }
    }

    if !found {
        return None;
    }
    let mut path = vec![end_];
    let (mut r, mut c) = end_;
    while (r, c) != start {
        let (pr, pc) = parent[r][c];
        path.push((pr, pc));
        r = pr;
        c = pc;
    }
    path.reverse();
    Some(path)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn test_maze() -> Vec<Vec<i32>> {
        vec![
            vec![0, 0, 1, 0, 0],
            vec![0, 0, 0, 0, 1],
            vec![1, 1, 0, 1, 0],
            vec![0, 0, 0, 0, 0],
            vec![0, 1, 1, 0, 0],
        ]
    }

    #[test]
    fn test_dfs() {
        let maze = test_maze();
        let path = solve_maze(&maze, (0, 0), (4, 4)).unwrap();
        assert_eq!(*path.first().unwrap(), (0, 0));
        assert_eq!(*path.last().unwrap(), (4, 4));
    }

    #[test]
    fn test_bfs() {
        let maze = test_maze();
        let path = solve_maze_bfs(&maze, (0, 0), (4, 4)).unwrap();
        assert_eq!(*path.first().unwrap(), (0, 0));
        assert_eq!(*path.last().unwrap(), (4, 4));
    }

    #[test]
    fn test_impossible() {
        let maze = vec![vec![0, 1], vec![1, 0]];
        assert!(solve_maze(&maze, (0, 0), (1, 1)).is_none());
    }
}

(* 1068: Maze Solver — Backtracking on 2D Grid *)

(* 0 = open, 1 = wall *)
let directions = [| (0, 1); (1, 0); (0, -1); (-1, 0) |]

(* Approach 1: Backtracking to find any path *)
let solve_maze maze start_r start_c end_r end_c =
  let rows = Array.length maze in
  let cols = Array.length maze.(0) in
  let visited = Array.init rows (fun _ -> Array.make cols false) in
  let path = ref [] in
  let rec dfs r c =
    if r = end_r && c = end_c then begin
      path := (r, c) :: !path;
      true
    end else if r < 0 || r >= rows || c < 0 || c >= cols
              || maze.(r).(c) = 1 || visited.(r).(c) then false
    else begin
      visited.(r).(c) <- true;
      path := (r, c) :: !path;
      let found = ref false in
      Array.iter (fun (dr, dc) ->
        if not !found then
          found := dfs (r + dr) (c + dc)
      ) directions;
      if not !found then
        path := List.tl !path;
      !found
    end
  in
  if dfs start_r start_c then Some (List.rev !path) else None

(* Approach 2: BFS for shortest path *)
let solve_maze_bfs maze start_r start_c end_r end_c =
  let rows = Array.length maze in
  let cols = Array.length maze.(0) in
  let visited = Array.init rows (fun _ -> Array.make cols false) in
  let parent = Array.init rows (fun _ -> Array.make cols (-1, -1)) in
  let queue = Queue.create () in
  Queue.push (start_r, start_c) queue;
  visited.(start_r).(start_c) <- true;
  let found = ref false in
  while not (Queue.is_empty queue) && not !found do
    let (r, c) = Queue.pop queue in
    if r = end_r && c = end_c then found := true
    else
      Array.iter (fun (dr, dc) ->
        let nr = r + dr and nc = c + dc in
        if nr >= 0 && nr < rows && nc >= 0 && nc < cols
           && maze.(nr).(nc) = 0 && not visited.(nr).(nc) then begin
          visited.(nr).(nc) <- true;
          parent.(nr).(nc) <- (r, c);
          Queue.push (nr, nc) queue
        end
      ) directions
  done;
  if not !found then None
  else begin
    let path = ref [(end_r, end_c)] in
    let r = ref end_r and c = ref end_c in
    while (!r, !c) <> (start_r, start_c) do
      let (pr, pc) = parent.(!r).(!c) in
      path := (pr, pc) :: !path;
      r := pr; c := pc
    done;
    Some !path
  end

let () =
  let maze = [|
    [|0; 0; 1; 0; 0|];
    [|0; 0; 0; 0; 1|];
    [|1; 1; 0; 1; 0|];
    [|0; 0; 0; 0; 0|];
    [|0; 1; 1; 0; 0|]
  |] in
  (match solve_maze maze 0 0 4 4 with
   | Some path -> assert (List.hd path = (0, 0)); assert (List.nth path (List.length path - 1) = (4, 4))
   | None -> assert false);
  (match solve_maze_bfs maze 0 0 4 4 with
   | Some path -> assert (List.hd path = (0, 0))
   | None -> assert false);

  (* Impossible maze *)
  let maze2 = [| [|0; 1|]; [|1; 0|] |] in
  assert (solve_maze maze2 0 0 1 1 = None);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    fn test_maze() -> Vec<Vec<i32>> {
        vec![
            vec![0, 0, 1, 0, 0],
            vec![0, 0, 0, 0, 1],
            vec![1, 1, 0, 1, 0],
            vec![0, 0, 0, 0, 0],
            vec![0, 1, 1, 0, 0],
        ]
    }

    #[test]
    fn test_dfs() {
        let maze = test_maze();
        let path = solve_maze(&maze, (0, 0), (4, 4)).unwrap();
        assert_eq!(*path.first().unwrap(), (0, 0));
        assert_eq!(*path.last().unwrap(), (4, 4));
    }

    #[test]
    fn test_bfs() {
        let maze = test_maze();
        let path = solve_maze_bfs(&maze, (0, 0), (4, 4)).unwrap();
        assert_eq!(*path.first().unwrap(), (0, 0));
        assert_eq!(*path.last().unwrap(), (4, 4));
    }

    #[test]
    fn test_impossible() {
        let maze = vec![vec![0, 1], vec![1, 0]];
        assert!(solve_maze(&maze, (0, 0), (1, 1)).is_none());
    }
}

Deep Comparison

Maze Solver — Comparison

Core Insight

DFS backtracking finds any path; BFS finds the shortest. Both need visited tracking and boundary checking. The parent array in BFS enables path reconstruction by tracing back from the destination.

OCaml Approach

• Queue module for BFS

• ref cells for mutable path and found flag

• Tuple arrays for parent tracking (int * int) array array

• Array.iter over direction tuples

Rust Approach

• VecDeque for BFS

• const DIRS for compile-time direction array

• Bounds checking via i32 arithmetic then cast back to usize

• Option<Vec<...>> return type — idiomatic for "might not exist"

Comparison Table

Aspect	OCaml	Rust
Directions	`let directions = [\|...\|]`	`const DIRS: [(i32,i32); 4]`
Bounds check	`r < 0 \\|\\| r >= rows`	Cast to `i32`, compare, cast back
BFS queue	`Queue.t`	`VecDeque`
Path return	`option`	`Option<Vec<...>>`
Parent tracking	`(int * int) array array`	`Vec<Vec<(usize,usize)>>`

Exercises

Add diagonal movement (8 directions) and verify BFS still finds shortest paths.

Implement A* search that uses Manhattan distance as the heuristic, finding shortest paths faster than BFS on open grids.

Write a maze generator using recursive backtracking (carve passages) and verify the solver can solve all generated mazes.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust