Backtracking Algorithm

Backtracking is a recursive algorithm used to solve problems by building a solution incrementally, one piece at a time, and removing solutions that fail to satisfy constraints of the problem.

It’s particularly useful for constraint satisfaction problems like puzzles, permutations, combinations, and finding paths.

Core Principles#

The backtracking algorithm follows these core principles:

1. Choice. At each step, you have a set of choices to make.
2. Constraints. You have constraints that limit the choices you can make.
3. Goal. Identify when a solution is found, allowing the function to backtrack from dead-ends.

Basic Template#

Here’s a basic template of a backtracking algorithm in Javascript:

function backtrack(path, options) {
    // Check if a complete solution is reached
    if (isSolution(path)) {
        processSolution(path);
        return;
    }

    // Iterate over available choices
    for (const choice of options) {
        // Check if choice is valid under current constraints
        if (isValid(path, choice)) {
            path.push(choice);        // Make a choice
            backtrack(path, options); // Recursively explore with the choice made
            path.pop();               // Undo choice (backtrack)
        }
    }
}

Example: N-Queens Problem#

The N-Queens problem is a classic backtracking problem where you need to place N queens on an N×N chessboard so that no two queens attack each other.

Check if a Queen is Safe#

To solve the N-Queens problem, you need to check if a queen can be safely placed at a given position (row, col) on the board.

Here are the conditions to check:

1. Row Check: Check if there is a queen in the same row on the left side.
2. Upper Diagonal Check: Check if there is a queen in the upper diagonal on the left side.
3. Lower Diagonal Check: Check if there is a queen in the lower diagonal on the left side.

If all these conditions are satisfied, the queen can be safely placed at (row, col).

function isSafe(board: number[][], row: number, col: number): boolean {
  // Check row on left side
  for (let j = 0; j < col; j++) {
    if (board[row][j] === 1) {
      return false;
    }
  }

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

  // Check lower diagonal on left side
  for (let i = row, j = col; i < n && j >= 0; i++, j--) {
    if (board[i][j] === 1) {
      return false;
    }
  }

  return true;
}

We don't check the right side of the board because we are placing queens from left to right, so the right side is empty.

Backtracking Algorithm#

The backtracking algorithm for the N-Queens problem involves recursively placing queens on the board and backtracking when a solution is not possible.

Here’s the high-level algorithm:

1. Start with an empty board.
2. Place a queen in the first column.
3. Move to the next column and place a queen in a safe position.
4. Repeat this process until all queens are placed or a solution is not possible.
5. If a solution is not possible, backtrack to the previous column and try a different position.

const n = 4;
const board = Array.from({ length: n }, () => Array(n).fill(0));

function backtrack(board, col) {
  // If the board is filled, return true
  if (col >= n) {
    return true;
  }

  for (let row = 0; row < n; row++) {
    if (isSafe(board, row, col)) {
      board[row][col] = 1;

      // Recursively place queens in the next column
      if (backtrack(board, col + 1)) {
        return true;
      }

      // If placing queen at (row, col) didn't lead to a solution,
      // backtrack by removing the queen
      board[row][col] = 0;
    }
  }

  return false;
}

if (!backtrack(board, 0)) {
  console.log("No solution exists");
} else {
  console.log(board);
}

Full Code#

Here’s a Javascript implementation of the N-Queens problem:

function solveNQueens(n) {
  const board = Array.from({ length: n }, () => Array(n).fill(0));
  const result = [];

  const isSafe = (board, row, col) => {
    for (let j = 0; j < col; j++) {
      if (board[row][j] === 1) {
        return false;
      }
    }

    for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 1) {
        return false;
      }
    }

    for (let i = row, j = col; i < n && j >= 0; i++, j--) {
      if (board[i][j] === 1) {
        return false;
      }
    }

    return true;
  }

  const backtrack = (board, col) => {
    if (col >= n) {
      result.push(board.map(row => row.join("")));
      return;
    }

    for (let row = 0; row < n; row++) {
      if (isSafe(board, row, col)) {
        board[row][col] = 1;
        backtrack(board, col + 1);
        board[row][col] = 0;
      }
    }
  }

  backtrack(board, 0);
  return result;
}

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

Applications#

Backtracking is used in various problems, including:

• Puzzles. Sudoku, crosswords, and word search puzzles.
• Permutations. Generating all permutations of a set of elements.
• Combinations. Generating all combinations of a set of elements.
• Graph Problems. Finding paths, cycles, or spanning trees in a graph.
• Constraint Satisfaction Problems. Scheduling, planning, and optimization problems.
• Game Playing. Chess, checkers, and other board games.
• Subset Problems. Finding subsets of a set that satisfy certain conditions.

Complexity#

The time complexity of backtracking algorithms can vary depending on the problem.

In the worst-case scenario, the time complexity is exponential, O(b^d), where b is the branching factor and d is the depth of the recursion.