Rat In A Maze Algorithm: Solve Using Backtracking in JavaScript

The Rat In A Maze problem is a classic pathfinding challenge where a rat needs to navigate a N × N maze from the top-left to the bottom-right corner, only moving through open paths (represented by 1).

🧠 Understanding the Problem

Given an N × N grid where 1 represents an open path and 0 represents a blocked cell, the rat must find a path from (0,0) to (N-1,N-1). The rat can move in four directions:

• Right (R)
• Down (D)
• Up (U)
• Left (L)

The challenge is to determine a valid path using the Backtracking algorithm, which explores possible moves and backtracks when an invalid state is found.

⚙️ Implementation in JavaScript

Here’s an efficient JavaScript implementation using backtracking:

  
function validateGrid(grid) {
  if (!Array.isArray(grid) || grid.length === 0)
    throw new TypeError('Grid must be a non-empty array')

  const allRowsHaveCorrectLength = grid.every(
    (row) => row.length === grid.length
  )
  if (!allRowsHaveCorrectLength) throw new TypeError('Grid must be a square')

  const allCellsHaveValidValues = grid.every((row) => {
    return row.every((cell) => cell === 0 || cell === 1)
  })
  if (!allCellsHaveValidValues)
    throw new TypeError('Grid must only contain 0s and 1s')
}

function isSafe(grid, x, y) {
  const n = grid.length
  return x >= 0 && x < n && y >= 0 && y < n && grid[y][x] === 1
}

function getPathPart(grid, x, y, solution, path) {
  const n = grid.length

  if (x === n - 1 && y === n - 1 && grid[y][x] === 1) {
    solution[y][x] = 1
    return path
  }

  if (!isSafe(grid, x, y)) return false
  if (solution[y][x] === 1) return false

  solution[y][x] = 1

  const right = getPathPart(grid, x + 1, y, solution, path + 'R')
  if (right) return right

  const down = getPathPart(grid, x, y + 1, solution, path + 'D')
  if (down) return down

  const up = getPathPart(grid, x, y - 1, solution, path + 'U')
  if (up) return up

  const left = getPathPart(grid, x - 1, y, solution, path + 'L')
  if (left) return left

  solution[y][x] = 0
  return false
}

function getPath(grid) {
  const n = grid.length
  const solution = Array.from({ length: n }, () => Array(n).fill(0))
  return getPathPart(grid, 0, 0, solution, '')
}

export class RatInAMaze {
  constructor(grid) {
    validateGrid(grid)
    const solution = getPath(grid)

    this.path = solution !== false ? solution : ''
    this.solved = solution !== false
  }
}
  

🚀 How the Algorithm Works

1️⃣ Validate the input grid to ensure it's a square matrix containing only 0 and 1.
2️⃣ Start from the top-left corner (0,0) and attempt to move right, down, up, or left.
3️⃣ If the destination (N-1,N-1) is reached, return the path taken.
4️⃣ If a move leads to a dead end, backtrack and explore other directions.
5️⃣ If no path is found, return false.

🛠️ Time Complexity

The worst-case time complexity of this approach is O(4^(N²)) since each cell has up to 4 possible moves.

✅ Example Output

  
Input Grid:
1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

Output Path:
DRDDRR
  

🎯 Applications

• Solving robotic navigation problems
• AI-based pathfinding algorithms
• Game development (maze-solving bots)

📌 Conclusion

The Rat In A Maze problem is a perfect example of backtracking, showcasing how recursive exploration and constraint checking work together. Mastering this technique will help in solving more complex pathfinding problems.