Backtracking

Overview

Exponential time algorithms with multiple solutions

Many problems have multiple solutions. Some problems grow exponentially but have solutions that may be found in less than exponential time.

Many of the techniques for finding solutions to difficult problems are commonly employed in artificial intelligence but the same techniques are useful in other application areas also.

Problem solving is often a search through the space of the different states possible for the problem.

Example The figure at right, n=3 number of bits, has 8 = 2³ states in the solution space.

Example A list of four unique integers has 4! = 24 permutations but only one that is sorted.

The search space contains each of the 24 permutations.

An exhaustive or brute-force search could be used but would expend more effort than necessary and could be unviable for large problem size.

Consider one possible solution in the search space of sorting the list in ascending order: <5,2,4,1>

After examining 5 and 2, the search can be terminated and another possible solution considered rather than examining 5, 2, 4, 1 as would BFS or DFS.

While merge sort obviously is predictably more efficient O(n lg n), the point here is that the n! state space can often be searched and a solution found in considerably less than n! time.

The key is to recognize when a partial solution is nonpromising in order to terminate the search and try other possible solutions.

Example: The search space of a sorted list <5, 2, 4> would include all 3! permutations of solutions, as in the one at left below.

The one at right shows only those necessary to be examined to determine which permutation is the sorted (descending) solution, <5, 4, 2>.

Full search space examined by brute-force

Partial search space examined by backtracking

Our strategy for searching the solution space might be to explore each descendant until either a complete solution:

1. is solution found then stop
2. is solution not found but descendants represent a promising solution then search a descendant
3. is solution not found and remaining descendant represent an unpromising solution, back up to a previous node and try an unexplored descendant

Employing this strategy would examine the nodes in the following order to find a descending sort:

• a, b - no possible solution with <2,4> or <2,5>, backup to a
• a, c, g - no solution, backup g, c, a
• a, d, m - no solution, backup m, d
• a, d, n, p - solution

Question 1 - (For the search space above): What is the best case search for a ascending sorted solution? W(n) on left side.

A descending sorted solution?  W(n) if starting on right side.

The worst case? Recall that a complete tree of height h has 2^h+1−1 nodes, the decision tree for sorting n items has height ³ lg n! for n! possible permutations (leafs). Brute force search of the complete space has exponential Q(2^{lg n!+1}) number of nodes.

Example: For n bits there are 2ⁿ encodings. A tree could represent for n=3 the 2³ values as below:

To find a value greater than 4 (100) in the organized search space, a binary search algorithm could easily do so in lg n time, the height.

Assuming the tree had the most significant bit at the top, any of the right branches would be a solution.

If the tree had the least significant bit at the top, finding a value greater than 4 could not be accomplished in lg n time without knowing beforehand the location of 5 (101), 6 (110) or 7 (111).

Our strategy for searching the solution space might be to explore descendant in DFS until either a complete solution:

1. is found then stop
2. is not found but descendants may hold the solution then search a descendant
3. is not found and no descendant may hold the solution, back up to a previous node and try another descendant

Employing this strategy would examine the nodes in the following order to find a value of 5 or greater:

• a, b, d, h - no solution, backup to d
• i - no solution, backup to d, b
• e, j - no solution, backup to e
• k - solution 110 or 6

Note that we did better than exponential time but searching for the maximal value equal 7 would be still exponential. Recall that a complete tree of height h has 2^h+1−1 nodes, the decision tree for sorting n items has height n. Brute force search of the complete space, Q(2ⁿ⁺¹).

 

Traversing a binary tree

Traversing and printing a binary tree in pre-order is:

preorder( T ) print T.node preorder( T.left ) preorder( T.right )

Printing the tree nodes at right as: abdhiejkcflmgnp

Notice that the algorithm traverses the tree in Depth-First order.

Whenever a left-branch has been fully traversed, it backs-up to traverse the right-branch.

Question 2 - Which node(s) does the algorithm back-up to after printing node k?

 

Generating the binary tree

The following generates the binary tree in a Depth-First, pre-order fashion.

This is the essence of the job of search algorithms, generating and exploring the search-space.

When the size of the solution X=3, the solution X is printed.

After a solution is generated, the algorithm backs-up to Line 3, generating the next solution.

All solutions are generated, none are excluded.

preorderBT( X[1..i] ) --  pre: X[1..i] specifies first i values --  post: Solution X[1..i] if size(X[1..i]) = 3 then print X[1..i] else    for each x Î {0, 1} do            X[i+1] ¬ x            preorderBT( X[1..i+1] )

Printed 000 001 010 011 100 101 110 111

Question 3 - Trace execution to generate the call tree for the first 4 print executions. Initial call is: preOrderBT( X[] )

 

Backtracking is based on constructing a search-space-tree whose nodes are specific choices of a solution's components (sub-solutions).

When none of a node's descendants (sub-solutions) can lead to a solution, DFS terminates and backtracks to the previous node with descendants (sub-solutions) that may lead to a solution.

By terminating searches and not exploring non-solution descendants, backtracking reduces the number of nodes examined and can often solve exponential time problems in a reasonable amount of time.

Backtracking is not an optimization method, simply attempts to reduce the size of the search-space examined.

Question - Why not use dynamic programming for sorting? It can solve difficult problems in linear time, sometimes.

Answer - Are there repeated solutions in any of the problems above? That is, is there an dynamic programming substructure?

Generic Backtracking Algorithm - Line 4 is only difference with preorderBT algorithm above.

DFSbt( X[1..i] ) --  pre: X[1..i] specifies first i components of a solution --  post: Solution X[1..i] --           Si+1 is solution i+1 if X[1..i] is a solution then print X[1..i] else    for each x Î Si+1 do       if x is consistent with X[1..i] and valid option for problem constraints then            X[i+1] ¬ x            DFSbt( X[1..i+1] )

The idea of backtracking is to construct a solution one component at a time and evaluate each partially constructed candidates as follows:

1. If a solution is found ...
2. If a partially constructed solution can be developed further without violating the problem's constraints, take the first remaining valid option for the next component.
3. If there is no valid option for the next component, no alternative for any remaining component need be considered. In this case the algorithm backtracks to replace the last component of the partially constructed solution with the next valid option.

The difference between backtracking and brute-force

Brute-force examines all the search space, including non-viable solutions.

Backtracking avoids the search space with no viable solutions.

Line 4 above is the key difference between the two methods. Without Line 4, unviable solutions would be examined.

 

Binary backtracking to find 3-bit binary values greater than 5, starting at least significant bit

Pseudocode version DFSbt( X[1..i] )       if binary( X[1..i] ) > 5 then print(X)       else          for x Î { 0, 1 } do             if i+1 £ 3  then         -- valid solution                 X[i+1] ¬ x                 DFSbt( X )      return  -- try different solution Output: 110              111

Java version void DFSbt( int X[], int i ) {    if( binary(X, i) > 5 ) print(X);    else      for(int x=0; x<=1; x++)         if (i+1 <= 3) {          X[i+1] = x;          DFSbt( X, i+1 );        } }

Backtracking can be observed to build the partial solution from the components of the two bits, 00, of b and d for example.

Tree at right has edges marked with 0 or 1, the value of x at line 4.

Example - Generate low bits first.

• Nodes abdh checked for solution at line 2, partial solution X considered is 000.
• Choose x=0, line 4. Increasing solution X size exceeds 3 bits (line 5), the limit of a viable solution.
• Choose x=1, line 4. Increasing solution X size exceeds 3 bits (line 5), the limit of a viable solution.
• The algorithm returns (to line 4 of previous call) to choose x=1, another valid component (this is the backtracking).
• The new promising solution is 100, for nodes abdi.
• The promising solution is checked (line 2), fails as a solution.
• Backtracking continues, eventually producing the answer 110 for nodes akeb.

Note that all viable solutions (3 bits or less) are produced in exponential time, Q(2^h+1). The valid solution test at line 5 is too strong to reduce the search space.

Any solution would be satisfactory and the algorithm could stop by exiting the for, often in below exponential time.

Question - Trace the recursion down to node j.

Change

The following makes change using { 25, 10, 5, 1 } coins.

DFSbtChange( X[1..i], change ) --  pre: X[1..i] specifies first i components of a solution --  post: Solution X[1..i] if change = 0 then print X[1..i] else    for each x Î {25, 10, 5, 1} do       if change - x >= 0 then            X[i+1] ¬ x            DFSbtChange( X[1..i+1], change - x )

Question 4a - Give the first solution found for DFSbtChange( X[1..i], 11 ).

Greedy - Some minor changes can produce behavior based on minimizing the number of coins used, the algorithm always chooses the minimum number of coins as the solution.

Line 3 and 6 introduce the greedy behavior.

Line 3 chooses largest coins first.

Line 6 excludes solutions that exceed an upper bound, the minimum number of coins used so far for a complete solution.

min ¬ ¥ is assumed initialization of global variable.

N-Queens

N-Queens is the quintessential backtracking problem because it clearly delineates the nonpromising solutions from the promising.

Queens can move along any diagonal, row or column.

The following are legal chess moves (arrows) for the Queen to attack other Queens.

	1	2	3	4
1	%	#	&
2	¬	Q	®	®
3	'	$	(
4		$		(

The goal of 4-Queens is to place 4 queens in non-attacking positions on the chess board.

The board below is a valid solution since no row, column or diagonal has more than one queen.

1 2 3 4 1   Q     2       Q 3 Q       4     Q

X row 1 2 3 4 column 2 4 1 3

The board is encoded in the state array X where the index is the row and the value is the column; see above for encoding of the one solution.

Promising moves are those that do not conflict with previous promising moves and do not violate the problem constraints; only one queen per row and must be on the board.

Promising moves are determined by function conflicted.

conflicted(X, row, column) - Function that returns True if placing a Queen at (row, column) conflicts with any previously placed Queens.

conflicted( X, 3, 1) returns True below; i.e. trying to place a Queen in (3, 1) conflicts with at least one other, Queen in (1, 1).

1 2 3 4 1 Q       2     Q   3 Q       4

X row 1 2 3 4 column 1 3

Question 4b - Can a Queen be placed anywhere above in row 3 without conflicting?

A partial search space for the 4-Queens problems is below, which includes the first solution.

Node numbers indicate the order in which the space is explored.

The x's indicate search space not explored because the partial solution does not have any valid components, due to queen conflicts.

For example, with a queen in row 1, column 1 of partial solution 1, there was no need to explore placing a queen in row 2, column 1 or 2.

After examining partial solution 4, no solution can exist for a queen in row 1, column 1.

The algorithm backtracks to row 1 and places a queen in row 1, column 2, which does have a solution.

Call by: DFSbtQ( X[], 0)

Question 5

• Are there any other partial solutions from 6, other than the configuration of 7?
• What is the next partial solution after 8?

  	1	2	3	4
  1
  2
  3
  4

• Continue to find the next solution.

  1 2 3 4 1         2         3         4

  1 2 3 4 1         2         3         4

  1 2 3 4 1         2         3         4

  1 2 3 4 1         2         3         4

Conclusion

Backtracking:

• substructure requires a criteria to determine promising subproblems to explore
  • criteria is: consistent with previous subproblems and does not violate problem constraints
• improves over brute-force algorithms by only developing promising subproblems.
• can be used in non-optimization problems, that is, decision problems.
• degenerates into brute force in worst case (as seen in our first example).