Recursion/Backtracking

The idea behind backtracking is to use recursion to explore a problem.

The recursive backtracking method follows a common generic template:

explore(choices):
    if(no choices left):
        check if this is a solution
        if this is a solution:
            save it
    else:
        make a choice
        explore(remaining choices)
        unmake choice

Examples

8 Queens Problem

Let's examine the 8 queens problem to see backtracking in action.