Skip to main content

Advanced Backtracking

TL;DR​

Advanced backtracking extends core techniques with optimization and constraint management strategies for complex problems. Word Search: Find words in 2D grid by exploring from each cell; constraint is path adjacency and visited cells; prune branches where letters don't match word prefix. Palindrome Partitioning: Split string into all partitions where each part is palindrome; decision is partition point; constraint is palindrome validation; precompute palindromes for efficiency. Constraint Propagation: When making choice, propagate consequences to reduce domain of future choices (e.g., Sudoku: place digit eliminates that digit from row/column/box possibilities). Branch and Bound: Maintain best solution found; prune branches exceeding current best bound; transforms search from exhaustive to goal-directed. Advanced techniques combine multiple strategies: constraint propagation reduces branching factor exponentially; branch-and-bound provides early termination; precomputation trades space for search speed.

Core Concepts​

Word Search Problem Structure​

Problem: Given 2D grid of characters and word, determine if word exists in grid formed by adjacent cells.

Path Constraint: Each cell visited at most once in single path; adjacent means 4-directional (up/down/left/right).

Search Strategy: DFS from each cell; try to match word character by character; backtrack if character doesn't match or cell revisited.

Key Optimization: Precompute all cells containing first character; only start DFS from those cells.

Palindrome Partitioning Patterns​

Decision: At each position in string, cut here or don't cut.

Constraint: Cut only if substring is palindrome.

State: Current position in string + partition boundaries.

Optimization: Precompute palindrome check matrix dp[i][j] = is substring [i:j] palindrome. Query in O(1) instead of O(j-i) for each cut.

Constraint Propagation Mechanics​

Definition: When variable is assigned value, immediately update domains of dependent variables.

Example (Sudoku): When place digit D at cell (r, c), remove D from possible values for all cells in row r, column c, and box containing (r, c).

Benefit: Reduces branching factor dramatically. If domain becomes empty, prune immediately without recursing deeper.

Implementation: Maintain set of possible values per cell (or per variable in general CSP).

Branch and Bound with Pruning​

Upper/Lower Bound: Compute bound on objective value for current partial solution. If bound worse than best solution found, prune.

Example (Traveling Salesman via backtracking): Best lower bound on remaining path cost > current best tour cost means this branch cannot improve. Prune.

Effectiveness: Depends on bound tightness. Loose bounds prune little; tight bounds prune aggressively.

Cost: Computing tight bounds takes time. Balance between pruning effectiveness and computation cost.

Key Algorithms​

Word Search with Backtracking​

Algorithm:

  1. For each cell containing first character of word
  2. Start DFS from that cell
  3. Try matching rest of word character by character
  4. Mark visited, recurse, unmark (backtrack)

Pruning: If current character doesn't match target, stop early (don't recurse further).

Palindrome Partitioning Optimization​

Precomputation: dp[i][j] = true if s[i:j+1] is palindrome

dp = [[False] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = True
    if i + 1 < n:
        dp[i][i+1] = (s[i] == s[i+1])

for length in range(3, n+1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])

Then use dp during backtracking to check palindrome in O(1).

Constraint Propagation in CSP​

AC-3 Algorithm (simplified):

  • Maintain queue of (variable, constraint) pairs
  • For each pair, remove values from variable's domain that don't have supporting value in related variable's domain
  • When domain changes, add related variables to queue
  • Continue until queue empty (arc consistent)

Practical Example​

# Word Search in Grid
def exist(board, word):
    """
    Find if word exists in 2D grid.
    Returns True if found, False otherwise.
    """
    if not board or not word:
        return False

    rows, cols = len(board), len(board[0])

    def dfs(row, col, word_idx, visited):
        """DFS to match remaining word starting from (row, col)"""
        if word_idx == len(word):
            return True  # Matched entire word

        if (row < 0 or row >= rows or col < 0 or col >= cols or
            (row, col) in visited or board[row][col] != word[word_idx]):
            return False  # Out of bounds, visited, or character mismatch

        visited.add((row, col))

        # Try all 4 directions
        found = (dfs(row+1, col, word_idx+1, visited) or
                dfs(row-1, col, word_idx+1, visited) or
                dfs(row, col+1, word_idx+1, visited) or
                dfs(row, col-1, word_idx+1, visited))

        visited.remove((row, col))  # Backtrack
        return found

    visited = set()

    # Try starting from each cell
    for row in range(rows):
        for col in range(cols):
            if board[row][col] == word[0]:
                if dfs(row, col, 0, visited):
                    return True

    return False

# Palindrome Partitioning
def partition(s):
    """
    Partition string into all possible palindrome partitions.
    Returns list of list of palindromes.
    """
    n = len(s)
    result = []

    # Precompute palindrome check
    dp = [[False] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True
        if i + 1 < n:
            dp[i][i+1] = (s[i] == s[i+1])

    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])

    def backtrack(start, current_partition):
        if start == n:
            result.append(current_partition[:])
            return

        for end in range(start, n):
            if dp[start][end]:  # Check if substring is palindrome
                current_partition.append(s[start:end+1])
                backtrack(end + 1, current_partition)
                current_partition.pop()

    backtrack(0, [])
    return result

# Traveling Salesman Problem (simplified with branch and bound)
def tsp_branch_and_bound(dist_matrix):
    """
    Find shortest Hamiltonian cycle in complete graph.
    Returns minimum cost and one optimal tour.
    """
    n = len(dist_matrix)
    visited = [False] * n
    current_path = [0]  # Start from city 0
    best_cost = [float('inf')]
    best_tour = [None]

    def lower_bound(node, visited):
        """Compute lower bound on remaining cost"""
        # Simplified: minimum outgoing edge for unvisited nodes
        bound = 0
        for i in range(n):
            if not visited[i]:
                bound += min(dist_matrix[i])
        return bound

    def backtrack(node, cost):
        if len(current_path) == n:
            # Complete tour - add return to start
            total_cost = cost + dist_matrix[node][0]
            if total_cost < best_cost[0]:
                best_cost[0] = total_cost
                best_tour[0] = current_path[:]
            return

        # Bound: current cost + lower bound on remaining
        bound = cost + lower_bound(node, visited)
        if bound >= best_cost[0]:
            return  # Prune

        for next_node in range(n):
            if not visited[next_node]:
                visited[next_node] = True
                current_path.append(next_node)
                edge_cost = dist_matrix[node][next_node]
                backtrack(next_node, cost + edge_cost)
                current_path.pop()
                visited[next_node] = False

    visited[0] = True
    backtrack(0, 0)
    return best_cost[0], best_tour[0]

# Tests
board = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
print("Word 'ABCCED' found:", exist(board, "ABCCED"))
print("Word 'ABCB' found:", exist(board, "ABCB"))

print("\nPalindrome partitions of 'nitin':")
partitions = partition("nitin")
for p in partitions:
    print(p)

print("\nTSP with 4 cities:")
dist = [[0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]]
cost, tour = tsp_branch_and_bound(dist)
print(f"Minimum cost: {cost}, Tour: {tour}")

Common Pitfalls​

warning

Word Search visited tracking: Forgetting to mark cell as visited before recursing leads to revisiting same cell in single path. Always restore visited status on backtrack.

Palindrome precomputation errors: Off-by-one errors in palindrome DP matrix (inclusive vs exclusive endpoints). Verify base cases and recurrence carefully.

Constraint propagation incomplete: Propagating only immediate constraints; missing transitive implications. Properly implement arc-consistency algorithms.

Loose branch-and-bound bounds: Computing bounds too conservatively reduces pruning effectiveness. Tighter bounds prune more but cost more to compute; balance needed.

Not restoring state on backtrack: Advanced problems often modify data structures in place (add to sets, update bounds). Always restore completely.

Heuristic ordering neglect: Trying choices in arbitrary order misses branching optimizations. Reorder choices by heuristics (MRV, LCV in CSP).

Self-Check​

  1. In word search, why must we track visited cells per path, not globally?
  2. How does precomputing palindromes reduce backtracking complexity for palindrome partitioning?
  3. In branch-and-bound, how tight must bounds be to justify the computation cost?

One Takeaway​

info

Advanced backtracking transforms exhaustive search into intelligent exploration through three mechanisms: constraint propagation to reduce branching factor, branch-and-bound to enable early termination, and precomputation to speed up decision making. The key is recognizing what to precompute, how to propagate constraints, and how tight to make bounds. Combine these techniques strategically, and you unlock efficient solutions to problems that seem intractable via naive backtracking.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson Education.
  • Tsang, E. (1993). Foundations of Constraint Satisfaction. Academic Press.