Lecture Preview: Exhaustive Search and Recursive Backtracking

(Suggested book reading: Programming Abstractions in C++, Chapter 9)

Today we will talk about recursive backtracking. Backtracking is an algorithmic technique for finding solution(s) by trying partial solutions and then abandoning them if they are not suitable. It is called a "brute force" algorithmic technique, because it just tries all paths until it finds what it wants. Backtracking algorithms are often implemented recursively.

Backtracking problems can often be solved using an algorithm that follows the following general pseudocode: 

function Explore(choices):
    if there are no more choices to make:
        stop.
    else:
        for each available choice C:
            Choose C.
            Explore the remaining choices.   // <-- recursion!
            Un-choose C.  (backtrack!)

So then, for any given problem, the challenge lies in figuring out what the "choices" are, how to "choose" and "un-choose" them, and so on.

Some examples of problems that can be solved using backtracking are:

  • producing all permutations of a set of values
  • parsing languages
  • games: anagrams, crosswords, word jumbles, 8 queens
  • combinatorics and logic programming
  • escaping from a maze
This document and its content are copyright © Marty Stepp, 2014. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.