Recursion & Backtracking

🐀 Rat starts at (0,0) → Goal: (5,5) — Press Play to begin

(0,0) START

(5,5) GOAL 🏁

🐀

🏁

Open

Wall

Path

Backtrack

Visited

Solution

Time

O(2^(N×N))

Space

O(N×N)

Debugger · v1.0

LIVE

1function solveMaze(maze, n) {

2 // 1: Start rat at (0, 0)

3 const sol = Array(n).fill(0).map(() => Array(n).fill(0));

4

5 // 2: Solve using DFS backtracking

6 if (!dfs(maze, 0, 0, sol, n))

7 return "No solution exists";

8

9 // 3: Return solution path

10 return sol;

11}

12

13function dfs(maze, row, col, sol, n) {

14 // 4: Goal reached - success!

15 if (row === n-1 && col === n-1) {

16 sol[row][col] = 1; return true;

17 }

18

19 // 5: Check if cell is valid & open

20 if (isSafe(maze, row, col, n)) {

21 sol[row][col] = 1; // mark path

22

23 // 6: Try all 4 directions (D R U L)

24 for (const [dr, dc] of dirs) {

25 // 7: Recurse into next cell

26 if (dfs(maze, row+dr, col+dc, sol, n))

27 return true;

28 }

29

30 // 8: BACKTRACK - unmark cell

31 sol[row][col] = 0;

32 }

33 // 9: No path from this cell

34 return false;

35}

Debugger · v1.0

LIVE

1function solveMaze(maze, n) {

2 // 1: Start rat at (0, 0)

3 const sol = Array(n).fill(0).map(() => Array(n).fill(0));

4

5 // 2: Solve using DFS backtracking

6 if (!dfs(maze, 0, 0, sol, n))

7 return "No solution exists";

8

9 // 3: Return solution path

10 return sol;

11}

12

13function dfs(maze, row, col, sol, n) {

14 // 4: Goal reached - success!

15 if (row === n-1 && col === n-1) {

16 sol[row][col] = 1; return true;

17 }

18

19 // 5: Check if cell is valid & open

20 if (isSafe(maze, row, col, n)) {

21 sol[row][col] = 1; // mark path

22

23 // 6: Try all 4 directions (D R U L)

24 for (const [dr, dc] of dirs) {

25 // 7: Recurse into next cell

26 if (dfs(maze, row+dr, col+dc, sol, n))

27 return true;

28 }

29

30 // 8: BACKTRACK - unmark cell

31 sol[row][col] = 0;

32 }

33 // 9: No path from this cell

34 return false;

35}

State Inspector

Variable	Value
$ratRow	0
$ratCol	0
$action	"init"

Grid:6×6

1x

Recursion & Backtracking

Rat in a Maze

Step 1 of 6

A classic backtracking problem where a rat must find a path from the top-left to the bottom-right corner of a maze, exploring all possible routes.

The Setup

The maze is an N×N grid. Each cell is either open (passable) or a wall (blocked). The rat starts at (0,0) and must reach (N-1,N-1). Walls are generated randomly but the maze is always guaranteed to have at least one solution.

🐀 Rat

● Path

✕ Backtrack

● Solution