Recursive Backtacking Introduction

Posted on | Post modified | In ,

What is Backtracking?

  • It is a systematic way to iterate through all the possible configurations of a search space.
  • It is a general algorithm which must be customized for each application.
  • It is really just depth-first search on an implicit graph of configurations.
    • Can easily be used to iterate through all subsets or permutations of a set.
    • Ensures correctness by enumerating all possibilities.
    • For backtracking to be efficient, we must prune dead or redundent branches of the search space whenever possible.

General Algorithm

1
2
3
4
5
6
7
8
9
10
Backtrack-DFS(A, k):
    if A = (a_1, a_2, ..., a_k) is a solution:
        report it
    else:
        k = k + 1
        compute S_k
        while S_k != ∅ do:
            a_k = an element in Sk
            S_k = S_k − a_k
            Backtrack-DFS(A, k)

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Combinatorial_Search:
    def __init__(self):
        self.finished = False

    def is_a_solution(self, current_answer, kth, info):
        pass

    def make_move(self, current_answer, kth, info):
        pass

    def unmake_move(self, current_answer, kth, info):
        pass

    def construct_candidates(self, current_answer, kth, info):
        pass

    def process_solution(self, current_answer, kth, info):
        pass

    def backtrack(current_answer, kth, info): 
        if self.is_a_solution(current_answer, kth, info):
            self.process_solution(current_answer, kth, info)
        else:
            kth += 1
            candidates = self.construct_candidates(current_answer, kth, info)

            for candidate in candidates:
                current_answer.append(candidate)
                self.make_move(current_answer, kth, info)
                self.backtrack(current_answer, kth, info)
                self.unmake_move(current_answer, kth, info)
                if self.finished:
                    return

  • is_a_solution(current_answer, kth, info)

    This Boolean function tests whether the first k elements of vector current_answer form a complete solution for the given problem.

    The last argument, info, allows us to pass general information into the routine.

  • construct_candidates(current_answer, kth, info)

    This routine return an array with the complete set of possible candidates for the kth position of current_answer, given the contents of the first k-1 positions.

  • process_solution(current_answer, kth, info)

    This routine prints, counts, or whatever processes a complete solution once it is constructed.

  • make_move(current_answer, kth, info) and unmake_move(current_answer, kth, info)

    These routines enable us to modify a data structure in response to the latest move, as well as
    clean up this data structure if we decide to take back the move.

Applications

  • Constructing all subsets
  • Constructing all permutations
  • Constructing all paths in a graph
  • N queens problem
  • Rat in a maze problem

References