Backtracking Algorithm Explained

January 23, 2025 | Algorithms

Backtracking is an algorithmic technique used for solving problems recursively by trying to build a solution incrementally. If a partial solution violates the constraints of the problem, the algorithm backtracks and tries a different path.

How Backtracking Works

Backtracking explores all possible solutions in a structured manner. It follows these steps:

1. Start with an empty solution.
2. Add elements to the solution while ensuring constraints are met.
3. If a constraint is violated, remove the last added element (backtrack) and try another option.
4. Repeat until a valid solution is found or all possibilities are exhausted.

Backtracking Implementation

Example: Solving the N-Queens Problem

The N-Queens problem involves placing N queens on an N x N chessboard so that no two queens threaten each other.

function solveNQueens(n) {
  const solutions = [];
  const board = Array.from({ length: n }, () => Array(n).fill('.'));
  
  function isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
      if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;
      if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;
    }
    return true;
  }
  
  function backtrack(row) {
    if (row === n) {
      solutions.push(board.map(r => r.join('')));
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  }
  
  backtrack(0);
  return solutions;
}

console.log(solveNQueens(4));

Applications of Backtracking

• Combinatorial Problems: Generating subsets, permutations, and combinations.
• Constraint Satisfaction Problems: Solving Sudoku, N-Queens, and crossword puzzles.
• Pathfinding Problems: Finding a path in a maze.

When to Use Backtracking

• When the problem requires exploring multiple possibilities.
• When a brute-force solution is too slow.
• When constraints limit the number of valid solutions.