We assume that a solution to the problem can be constructed from component solutions, xi. So the solution can be expressed as (x1, x2,...,xn) and a partial solution is (x1, x2,...,xi) where i < n. A state-space tree is the tree of the construction of the solution from partial solution starting with the root with no component solution (...).
Draw an abstract tree.
The tree is typically search depth first and the nodes are implicit meaning they are generated as need. A node is said to be promising if the partial solution is still feasible. Any time the partial node becomes infeasible the node, called non-promising the branch will no longer be pursued. So, the algorithm backtracks to the first promising node and explores the other branches of the state-space tree.
Algorithm Backtrack(X[1...i])
if X[1...i] is a solution then write X[1...i]; exit
else
for each X[1...i+1] that is promising do
Backtrack(X[1...i+1])
The above has the advantage that perhaps not all the solutions are generated and some potential solutions maybe eliminating because they belong they have a non-promising partial solution.
The difficult of constructing the backing tracking algorithm typically is generating the state-space tree.
We search for a cycle that visits all the nodes of the graph only once.
We start at an arbitrary node of the graph, which is a partial solution. We construct a larger partial solution by adding an adjacent node to the path. If we can get back to the start node then we have generate the solution.
Illustrate.
Given a set of numbers,S, find a subset with sum, N.
The root of the state-space tree is the empty set. For each element, xi in S we consider both adding and not adding the element to the partial solution {x1, x2, ..., xi-1}. The node contains the partial solution and sum.
Illustrate with S={3, 5, 6, 7} and N = 15.
The problem is to configure n queens on an nxn checkered board so that no queen can attack another queen.
Naturally each queen must be on a unique row, call the queen 1 the queen on row 1. We recursively place the queens on the next square on its row.
Illustrate with 4 queens
The efficiency of backtracking relies on pruning tree. Sometimes symmetry in the problem can eliminate branches early. For example, in the n-queen, problem we only need consider the first n/2 positions.
Another trick is to trick is to presort the set in the subset sum problem.
Another trick is to pre-assign values in the partial solution as we did in the Hamiltonian circuit problem.