20-Jan-2025

Backtracking is a powerful algorithmic technique used to solve problems that involve exploring a search space to find a solution. It works by incrementally building a solution, one step at a time. If a partial solution is found to be invalid or does not lead to a complete solution, the algorithm “backtracks” to the previous step and tries a different path. Think of it as exploring a maze – if you hit a dead end, you retrace your steps and try a different route.

How Backtracking Works

Backtracking employs a recursive approach and typically follows these steps:

1. Base Case: Define a condition that indicates whether a solution has been found or if the search space has been exhausted. This is the termination condition for the recursion.

2. Choices: At each step, identify the possible choices or decisions that can be made.

3. Constraints: Implement rules or conditions that determine if a choice is valid or feasible. This prevents exploring dead ends.

4. Recursion: For each valid choice, recursively call the backtracking function to explore the next step in the search space.

5. Backtracking: If a recursive call returns without finding a solution, undo the choice made in the current step (i.e., backtrack) and try the next available choice.

Example: N-Queens Problem

The N-Queens problem is a classic example where backtracking is effective. The goal is to place N chess queens on an N×N chessboard such that no two queens threaten each other (no two queens share the same row, column, or diagonal).

function isSafe(board, row, col, N) {
  for (let i = 0; i < row; i++) {
    if (board[i] === col || Math.abs(board[i] - col) === row - i) {
      return false;
    }
  }
  return true;
}

function solveNQueensUtil(board, row, N, solutions) {
  if (row === N) {
    solutions.push([...board]); // Found a solution, add a copy
    return;
  }

  for (let col = 0; col < N; col++) {
    if (isSafe(board, row, col, N)) {
      board[row] = col;
      solveNQueensUtil(board, row + 1, N, solutions);
      // Backtrack implicitly – no need to reset board[row] as next loop iteration overwrites
    }
  }
}

function solveNQueens(N) {
  const board = new Array(N);
  const solutions = [];
  solveNQueensUtil(board, 0, N, solutions);
  return solutions;
}

const solutions = solveNQueens(4);
console.log(solutions);

Explanation

• isSafe(): Checks if placing a queen at (row, col) is safe.
• solveNQueensUtil(): The recursive backtracking function. It tries placing a queen in each column of the current row.
• solveNQueens(): Initializes the board and starts the backtracking process.

Key Advantages of Backtracking

• Simplicity: Relatively easy to implement.
• Versatility: Can be adapted to various problems.
• Finding All Solutions: Can be used to find all possible solutions or a single solution.

Limitations

• Time Complexity: Can be computationally expensive for larger search spaces, potentially leading to exponential time complexity.
• Memory Usage: Recursive calls can consume significant stack space, especially for deep recursion.

Backtracking is a fundamental technique in problem-solving. Understanding its core principles opens up possibilities to tackle a wide range of challenges effectively.