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:

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.

Related Posts