14-Mar-2025

Backtracking is a powerful algorithmic technique used to solve problems that involve exploring multiple possibilities and finding a solution that satisfies certain constraints. It’s a form of depth-first search where you incrementally build a solution, and if a partial solution violates the constraints, you “backtrack” – undo the last step – and try a different path. Think of it like navigating a maze: you try one path, and if it leads to a dead end, you go back to the last intersection and try a different path.

Here’s a breakdown of how backtracking works:

1. Start with an empty solution: Initialize an empty solution or a starting point.

2. Make a choice: Select a possible next step or component to add to the solution.

3. Check constraints: If the current choice violates any problem constraints, backtrack. That is, undo the choice made in step 2 and return to the previous state.

4. Recursive call: If the current choice is valid, add it to the solution and recursively call the backtracking function to continue building the solution.

5. Base case: If a complete solution is found that satisfies all constraints, return the solution.

6. Backtrack: If no valid choices remain at the current level, backtrack and explore different paths.

Example: N-Queens Problem (JavaScript)

The N-Queens problem asks you 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) {
  // Check the column
  for (let i = 0; i < row; i++) {
    if (board[i][col]) {
      return false;
    }
  }

  // Check upper left diagonal
  for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j]) {
      return false;
    }
  }

  // Check upper right diagonal
  for (let i = row, j = col; i >= 0 && j < N; i--, j++) {
    if (board[i][j]) {
      return false;
    }
  }

  return true;
}

function solveNQueensUtil(board, row, N, solutions) {
  if (row === N) {
    const solution = board.map(row => row.join('')); // Convert to string format
    solutions.push(solution);
    return;
  }

  for (let col = 0; col < N; col++) {
    if (isSafe(board, row, col, N)) {
      board[row][col] = 1; // Place the queen
      solveNQueensUtil(board, row + 1, N, solutions);
      board[row][col] = 0; // Backtrack (remove the queen)
    }
  }
}

function solveNQueens(N) {
  const board = Array(N).fill(0).map(() => Array(N).fill(0));
  const solutions = [];
  solveNQueensUtil(board, 0, N, solutions);
  return solutions;
}


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

In this example, isSafe checks if placing a queen at (row, col) is safe. solveNQueensUtil is the recursive backtracking function. When a queen is placed successfully, the function recursively calls itself for the next row. If no safe position is found in a row, the function backtracks by removing the queen from the previous position and trying a different column.

Backtracking is a fundamental technique applicable to a wide range of problems, including constraint satisfaction, graph traversal, and combinatorial search. Understanding this concept is crucial for any programmer tackling complex algorithmic challenges.