Backtracking

Consider the N Queens problem -- Discover if and how N Queens can be placed on an N x N chessboard in non-attacking position.  (There is a solution to the N Queens problem for all boards of N ≥ 4)

Assume N = 4.  We want to place 4 queens on the chessboard below in non-attacking position.

We will develop a backtracking algorithm to try to solve this problem.  Backtracking is used to solve problems for which a sequence of objects is to be selected from a set such that the sequence satisfies some constraint.  In the case of the N-queens, the constraint is that all N queens be placed in non-attacking position.

Backtracking is a modified depth-first search of a tree consisting of all of the possible sequences that can be constructed from the problem set.  In backtracking we perform a depth-first traversal of this tree until we reach a node that is non-viable or non-promising, at which point we "prune the subtree" rooted at this node, and continue the depth-first traversal of the tree.

public static void DFS (Graph g, Object vertex) {

g.visit(vertex);

Iterator itr = g.neighbors(vertex);

while (itr.hasNext( ) ) {

Object v = itr.next( );

if (!g.isVisited(v) )

DFS(g, v);

}

}

This algorithm just specifies the order in which the nodes are to be "visited",  it does not include any instruction for what to do at a node when it is "visited".

The diagram below partially illustrates the state space tree for the instance of the N-Queens problem when N = 4.  the ordered pair (i, j) in each node indicates a possible row, column placement of a queen.  Each queen can be placed in one of the N columns for each of the N rows, for a total of  4 x 4 x 4 x 4 = 256 candidate solutions.  In general therefore, there are NN candidate solutions.

The general backtracking algorithm problem modifies depth-first search as follows:

public static void backtrack( node v) {

//backtracking pseudo-code

if (promising(v) )

if (there is a solution at v)

write the solution;

else {

for (each child u of v)

backtrack(u);

}

For the N-Queens problem, a placement is "promising" if the placed queen is not in the same column or same diagonal as one of the already positioned queens.  To locate the first solution to the 4-queens problem, the following nodes in state-space will be visited.

This traversal of state-space corresponds to the following attempts at positioning the queens.

When none of the children nodes of a placed queen leads to a promising solution, the algorithm backtracks and removes the last queen placed.

public class NQueens {

private int [ ] columns;

private int N;

public NQueens(int size) {

N = size;

columns = new int[size];

}

private void placeQueen (int  row) {

if (promising (row) ) {

if (row == N - 1) {

//print out result

for (int i = 0; i < N; i++)

System.out.print( "  "+ columns[i] );

System.out.println( );

}

else

for (int j = 0; j < N; j++) {

columns[row + 1] = j;

placeQueen (row + 1);

}

}

}

private boolean promising(int index) {

int k = 0;

boolean flag = true;

while (k < index && flag) {

if ( columns[index] == columns[k] ||

Math.abs(columns[index] - columns[k]) == index - k)

flag = false;

}

return flag;

}

public void placeNQueens ( ) {

//post-condition:   All solutions to the NQueens for user supplied N have been found

for (int i = 0; i < N; i++) {

columns[0] = i;

placeQueen(0);

}

}

}

Efficiency of the NQueens Backtracking Algorithm

Obtain an upper bound for the number of "promising" nodes examined in the state space.

When placeQueen( i ) is called, i  queens have been placed in rows 0 .. i -1.  There are n(n - 1) …(n - i + 1) ways to place the first i queens when i > 0.  When i = 0,  there is 1 call to promising( ).  Thus for each iteration of the for-loop in placeNQueens( ), the number of "promising" nodes that are visited is less than or equal to:

{1 + n +  n(n-1) +  … + n(n-1) ….2}

and since the for-loop in placeNQueens executes n times,

# of promising  nodes £  n{1 + n + n(n-1) + …. + n(n-1) … 2} = n (n!) {1/n! + 1/(n-1)! + … + 1/1!}

n                                                          ¥

= n (n!) S 1/i!  £ n (n!) (e -1)               since     S1/i! = e

i = 1                                                       i = 0

This bound must be multiplied by O(n) -- the run-time of promising( ) in our algorithm, but this method can be reduced to O(1) if an array of diagonals used is maintained by NQueens.  This bound is also artificially high, because it ignores the number of nodes that are non-promising because of the test for occupied diagonals.  Still the worst-case bound on using a backtracking algorithm to find all solutions to the NQueens problem is worse than exponential.

The 0-1 Knapsack

Consider of size K and we want to select from a set of n objects , where the ith object has size si and value vi, a subset of these objects to maximize the value contained in the knapsack with the contents of the knapsack less than or equal to K.

Suppose that K = 16 and n = 4, and we have the following set of objects ordered by their value density.

i                       vi                      si                      vi/si

1                      \$45                  3                      \$15

2                      \$30                  5                      \$  6

3                      \$45                  9                      \$  5

4                      \$10                  5                      \$  2

We will construct the state space where each node contains the total current value in the knapsack, the total current size of the contents of the knapsack, and maximum potential value that the knapsack can hold.  In the algorithm, we will also keep a record of the maximum value of any node (partially or completely filled knapsack) found so far.  When we perform the depth-first traversal of the state-space tree, a node is "promising" if its maximum potential value is greater than this current best value.

We begin the state space tree with the root consisting of the empty knapsack.  The current weight and value are obviously 0.  To find the maximum potential value we treat the problem as if it were the fractional knapsack problem and we were using the greedy algorithmic solution to that problem.  We have shown that the greedy approach to the fractional knapsack problem yields an optimal solution.  We place each of the remaining objects, in turn, into the knapsack until the next selected object is too big to fit into the knapsack.  We then use the fractional amount of that object that could be placed in the knapsack to determine the maximum potential value.

totalSize = currentSize + size of remaining objects that can be fully placed

bound (maximum potential value) = currentValue +

value of remaining objects fully placed +

(K - totalSize) * (value density of item that is partially placed)

In general, for a node at level i in the state space tree (the first i items have been considered for selection) and for the kth object as the one that will not completely fit into the remaining space in the knapsack, these formulae can be written:

k-1

totalSize = currentSize +  S sj

j=i+1

k-1

bound = currentValue  + S vj   + (K - totalSize) * (vk/sk)

j=i+1

For the root node, currentSize = 0,  currentValue = 0

totalSize = 0 + s1 + s2 = 0 + 3 + 5 = 8

bound = 0 + v1 + v2 + (K - totalSize) * (v3/s3) = 0 + \$45 + \$30 + (16 - 8) * (\$5) = \$75 + \$40 = \$115

From the root, we add two children at level 1 -- the node where the first item is included in the knapsack and the node where it is not.  For the child where the first item is not included in the knapsack, the calculation for the bound proceeds as follows:

totalSize = 0 + s2 + s3 = 5 + 9 = 14

bound = 0 + v2 + v3 + (K - totalSize) * (v4/s4) = 0 + \$30 + \$45 + (16  - 14) * (\$2)

= \$79

The state spaced traversed by the backtracking algorithm is displayed below.  When the bound of a node is less than or equal to the current maximum value, or adding the current item to the node causes the size of the contents to exceed the capacity of the knapsack, the subtrees rooted at that node are pruned, and the traversal backtracks to the previous parent in the state space tree.

public class KnapsackBacktrack {

private double maxValue;

private double K;             //knapsack capacity

private double [ ] s;           //array of sizes

private double [ ] v;           //array of values (both ordered by value density)

private List bestList;           //members of solution set for current best value

private int numItems;          //number of items in set to select from (first item is

//dummy 0)

public KnapsackBacktrack(double capacity, double [ ] size, double [ ] value,

int num) {

maxValue = 0.0;

K = capacity;

s = size;

v = value;

numItems = num;

bestList = null;

}

private void knapsack(int index, double currentSize, double currentValue,

List cList) {

if (currentSize <= K && currentValue > maxValue) {

maxValue = currentValue;

bestList = new LinkedL:ist(cList);

}

if (promising(index, currentSize, currentValue) {

List  leftList  = new LinkedList(cList);

leftList.add(new Integer(index + 1) );

knapsack(index + 1, currentSize + s[index+1], currentValue +                                                         v[index+1], leftList);

rightList = new LinkedList(cList);

knapsack(index + 1, currentSize, currentValue, rightList);

}

}

private boolean promising(int item, double size, double value) {

double bound = value;

double totalSize = size;

int k = item + 1;

if (size > K)  return false;

while (k < numItems && totalSize + s[k] <= K) {

bound += v[k];

totalSize += s[k];

k++;

}

if (k < numItems)

bound += (K - totalSize) * (v[k]/s[k]);

return bound > maxValue;

}

public void findSolution( ) {

List currentList = new LinkedList( );   //create an empty list

knapsack (0, 0.0, 0.0, currentList);

System.out.print("The solution set is:  ");

for (int i = 0; i < bestList.size( ); i++) {

System.out.print("  " + bestList.get(i) );

System.out.println( );

System.out.println("The value contained in the knapsack is:  \$" +                                                            maxValue);

}

}

For the example problem this algorithm traverses the following state space:

Run-time Efficiency of the Dynamic Programming Algorithm

For n objects, there are 2n possible solution sets -- the ith object is either in or out of the solution set.  The state space, therefore, is represented as a complete binary tree with 2n leaves.  Such a tree will have a total of 2n+1 - 1 nodes.  The backtracking algorithm, therefore, has a worst-case bound that is O(2n).  With pruning the actual number of nodes "visited" by the algorithm is much less.

The Hamiltonian Cycle Problem

A path is not a Hamiltonian cycle if

1. after traversing N vertices it cannot return to the start vertex
2. if for any 0 < i < N there is not an edge from path[i-1] to path[i]
3. if the path contains a cycle -- if any vertex in the path (except the first and last) occur more than once.

The "brute force" algorithm tries all N! permutations of the N vertices to find all the Hamiltonian cycles in the graph.  The backtracking algorithm prunes unpromising subtrees, but the algorithm is still O(n!).

public class HamiltonianBacktrack {

private int [ ][ ] M;             //adjacency matrix representation of the graph

private int [ ] path;

private int N;                                 //number of vertices in the graph

public HamiltonianBacktrack(int [ ][ ] G) {

M = G;

N = M.length;

path = new int[N + 1];

}

private void hamiltonian(int index) {

if (promising(index) ) {

if (index == N -1) {

//print out the result

path[index+1] = path[0];   //first add the start vertex to the end                                                                                           //of the cycle

System.out.print("A soulution is: ");

for (int i = 0; i <= N; i++)

System.out.print("  " + path[i]);

System.out.println( );

}

else

for (int j = 0; j < N; j++) {          //try all vertices as the next one

path[index+1] = j;

hamiltonian(index+1);

}

}

}

private boolean promising(int index) {

if (index == 0) return true;

if (index == N -1 && M[path[index]][path[0]] == 0)

return false;

if (index > 0 && M[path[index-1]][path[index]] == 0)

return false;

int j = 0;

while (j < index && path[index] != path[j])

j++;

return (j == index);

}

public void hamiltonianPath(int startVertex) {

path[0] = startVertex;

hamiltonian(0);

}

}