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.

The 8 queens problem asks the following question: what are the possible configurations of placing 8 queens on a chessboard, such that no queen may attack any other queen?

The 8 queens problem is essentially a chess version of the Mexican standoff (Wikipedia), in which no participants may retreat or proceed without exposing themselves to danger. In chess, the most heavily-armed piece is the Queen, so having 8 Queens on the chessboard is like having many heavily-armed individuals in a small space. Solutions to the 8 queens problem may be found by roving around a small neighborhood. The 8 queens problem seeks to find positions for each of the 8 queens (the gunfighters of chess) that result in a standoff.

This problem may be solved using backtracking. If we imagine the problem space of deciding which squares to place queens onto, the problem space is enormous:

${\frac {64!}{(64-8)!}}$

or, approximately 9 trillion different configurations. However, if we utilize information we know about the rules of chess, and about where queens have already been placed on the chessboard, thus ruling out certain squares, we can reduce the problem space substantially, closer to 80,000 possible solutions.

Solution in Java: https://github.com/charlesreid1/hello-world/blob/master/java/NQueens.java

Solution in Perl: https://github.com/charlesreid1/hello-world/blob/master/perl/8queens.pl