Backtracking

Backtracking is an algorithm design technique used to solve problems, by systematically searching for a solution among all possible candidates. The core idea of backtracking is to construct solutions one component at a time. As a solution is partially constructed, it is evaluated.

If a partially constructed solution violates the problem's constraints or it's determined that no potential values of the remaining components can lead to a solution, the algorithm terminates that path and does not generate further components from it. Instead, it backtracks to a previous point to try a different option.

This process is often visualized as building a state-space tree, where each node represents a partially constructed solution.

• A node is considered promising if it can potentially lead to a solution.
• A node is nonpromising if it cannot lead to a solution.
• The tree is typically constructed in a depth-first search (DFS) fashion.
• When a node becomes nonpromising, the algorithm backtracks to its parent node to explore alternative choices.
• If a complete solution is found, the algorithm either stops (if only one solution is needed) or continues searching for others.

---

Backtracking is used to solve combinatorial problems where solutions grow exponentially fast with input size, by systematically searching for a solution among all possible candidates. It can be seen as a more intelligent variation of exhaustive search.

Backtracking is commonly applied to non-optimization problems.

Examples include, Finding all possible solutions to a puzzle or determining if a Hamiltonian circuit exists, N-Queens problem and Subset-Sum problem.

While it can solve large instances of difficult combinatorial problems, in the worst case, it may still have to generate all possible candidates, leading to exponential time complexity.

Branch-and-Bound

Branch-and-Bound is an algorithm design technique that enhances the idea of backtracking and is specifically applicable to optimization problems. Optimization problems seek to minimize or maximize an objective function, subject to certain constraints.

Similar to backtracking, Branch-and-Bound also constructs solutions one component at a time and uses a state-space tree where nodes represent partially constructed solutions.

The key difference lies in its pruning mechanism:

• It requires a way to compute a bound on the best possible value of the objective function for any solution that can be obtained from a given node. For minimization problems, this is a lower bound, and for maximization problems, it's an upper bound.
• It also maintains the value of the best solution found so far.

A node is considered non-promising and can be terminated (pruned) if its bound value is not better than the value of the best solution already found. This helps in cutting off branches of the state-space tree that cannot possibly lead to an optimal solution.

Branch-and-Bound algorithms uses the best-first rule, where the algorithm prioritizes expanding the node with the most promising bound (e.g., the smallest lower bound for a minimization problem).

Examples include the Assignment Problem, the Knapsack Problem, and the Traveling Salesman Problem (TSP).

Although it offers hope for solving larger instances of NP-hard problems than exhaustive search, its worst-case efficiency can still be exponential.

Comparing Backtracking and Branch-and-Bound

Backtracking and Branch-and-Bound share fundamental similarities but differ in their specific applications and mechanisms for pruning the search space.

Similarities:

• Improvement over Exhaustive Search: Both techniques are designed to solve difficult combinatorial problems more efficiently than a pure exhaustive search by avoiding the generation of all possible candidates.

• Component-by-Component Construction: Both construct candidate solutions one component at a time.

• State-Space Tree: Both utilize a state-space tree to represent partially constructed solutions and the search process.

• Pruning: Both terminate a node (prune a branch) as soon as it can be guaranteed that no solution can be obtained by further developing that path.

Differences:

• Problem Type:

  • Backtracking is generally applied to nonoptimization problems (problems where any valid solution is acceptable, e.g., finding a Hamiltonian circuit or all solutions to the N-Queens problem).

  • Branch-and-Bound is exclusively applicable to optimization problems (problems seeking the best solution, e.g., the shortest Hamiltonian circuit or the most valuable subset for the knapsack problem).

• Pruning Mechanism:

  • Backtracking prunes nonpromising nodes based on whether they violate problem constraints or cannot lead to any valid solution.

  • Branch-and-Bound prunes nodes by computing bounds on the objective function value achievable from that node. If this bound is not better than the value of the best solution already found, the branch is pruned.

• Traversal Order:

  • The state-space tree in Backtracking is typically generated in a depth-first search (DFS) manner. It explores one path as deeply as possible before backtracking.

  • Branch-and-Bound can generate nodes according to several rules, with the best-first rule (expanding the most promising node based on its bound) being a common strategy, though other traversal orders are also possible.

Backtracking to solve the n-Queens problem.

Page 450

The n-Queens problem is a classic combinatorial challenge that involves placing n queens on an n x n chessboard such that no two queens attack each other. This means no two queens can be in the same row, same column, or on the same diagonal.

For n = 1, there's a trivial solution, but for n = 2 and n = 3, no solutions exist.

Backtracking is a suitable algorithm design technique for solving this problem. It systematically searches for a solution by constructing it one component at a time.

In the context of the n-Queens problem:

• Problem Formulation: Since each of the n queens must be placed in its own row, the problem reduces to assigning a column for each queen in its respective row.

• State-Space Tree Construction: The backtracking algorithm explores a state-space tree, where each node represents a partially constructed solution (i.e., some queens have been placed). This tree is typically built in a depth-first search (DFS) fashion.

• Placing Queens and Checking Constraints:

  • The algorithm starts with an empty board.
  • It attempts to place the first queen in the first possible position of its row (e.g., queen 1 in column 1 of row 1).
  • Then, it proceeds to place the next queen in the next row. For each placement, it checks if the current queen placement violates any constraints (i.e., if it attacks any previously placed queens in the same column or on the same diagonal).
  • A node in the state-space tree is considered promising if it can potentially lead to a solution; otherwise, it is nonpromising.

• Backtracking (Pruning):

  • If a partially constructed solution (a queen's placement) is found to be nonpromising (e.g., it attacks another queen or there's no legitimate option for the next queen), the algorithm terminates that path and does not generate further components from it.
  • Instead, it backtracks to the previous queen's position to try a different option (the next available column in that row). If there are no more options for that queen, it backtracks further up the tree.

Solving the 4-Queens Problem to Obtain One Solution

1. Start with an empty 4x4 board.
2. Queen 1 is placed at (1, 1).
3. Queen 2 tries columns 1 and 2 unsuccessfully, then is placed at (2, 3).
4. From (2, 3), no acceptable position exists for Queen 3 in row 3. This is a dead end.
5. The algorithm backtracks to Queen 2 and moves it to the next possible position, (2, 4).
6. Then, Queen 3 is placed at (3, 2), which again proves to be a dead end as no position is available for Queen 4.
7. The algorithm backtracks all the way to Queen 1 and moves it to (1, 2).
8. From (1, 2):
   • Queen 2 goes to (2, 4).
   • Queen 3 goes to (3, 1).
   • Queen 4 goes to (4, 3).
   • This combination (1,2), (2,4), (3,1), (4,3) forms a solution to the problem.

If more solutions are needed, the algorithm can continue its search by resuming from the leaf where it stopped.

Finding All Possible Solutions to the 4-Queens Problem

To find all possible solutions to the 4-Queens problem using backtracking:

• After finding a complete solution, the algorithm does not stop if all solutions are required. Instead, it continues searching by backtracking from the leaf where it found the solution. It will then explore other branches of the state-space tree.

• For example, after finding the solution (1,2), (2,4), (3,1), (4,3), the algorithm would backtrack from Queen 4's position. Since there are no more options for Queen 4 in row 4 (given previous placements), it would backtrack to Queen 3 and try another column for it. If no more columns are available for Queen 3, it would backtrack further to Queen 2, and so on. This systematic exploration ensures that all valid combinations are eventually discovered.

• The problem can have multiple solutions, and the backtracking algorithm is designed to find them by continuing its search. Board symmetry can also be exploited to find additional solutions more efficiently, as some solutions can be obtained from others by reflection or rotation, effectively cutting the size of the search tree.

• While the initial discussion provides steps for finding one solution, the process for finding all solutions is a continuation of the same backtracking logic: instead of halting, the algorithm simply resumes its search from the point of the last successful placement, exploring all remaining alternatives in the state-space tree.