# These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

 Page 2/24 Date 03.05.2017 Size 186.06 Kb. #18863

## Pruning and Branch and Bound

• For example on board:
• Since edge (C, D) does not exist we know that no paths with (C, D) in them should be tried
• If we start from A, this prunes a large subtree from the tree and improves our runtime
• Same for edge (A, E) and others too
• Important note:
• Pruning / Branch and Bound does NOT improve the algorithm asymptotically
• The worst case is still exponential in its run-time
• However, it makes the algorithm practically solvable for much larger values of N

## Recursion and Backtracking

• Exhaustive Search algorithms can often be effectively implemented using recursion
• Think again of the execution tree
• Each recursive call progresses one node down the tree
• When a call terminates, control goes back to the previous call, which resumes execution
• BACKTRACKING

## Recursion and Backtracking

• Idea of backtracking:
• Proceed forward to a solution until it becomes apparent that no solution can be achieved along the current path
• At that point UNDO the solution (backtrack) to a point where we can again proceed forward
• Example: 8 Queens Problem
• How can I place 8 queens on a chessboard such that no queen can take any other in the next move?
• Recall that queens can move horizontally, vertically or diagonally for multiple spaces
• See on board

## 8 Queens Problem

• 8 Queens Exhaustive Search Solution:
• Try placing the queens on the board in every combination of 8 spots until we have found a solution
• This solution will have an incredibly bad run-time
• 64 C 8 = (64!)/[(8!)(64-8)!]
• = (64*63*62*61*60*59*58*57)/40320
• = 4,426,165,368 combinations
• (multiply by 8 for total queen placements)
• However, we can improve this solution by realizing that many possibilities should not even be tried, since no solution is possible
• Ex: Any solution has exactly one queen in each column

## 8 Queens Problem

• This would eliminate many combinations, but would still allow 88 = 16,777,216 possible solutions (x 8 = 134,217,728 total queen placements)
• If we further note that all queens must be in different rows, we reduce the possibilities more
• Now the queen in the first column can be in any of the 8 rows, but the queen in the second column can only be in 7 rows, etc.
• This reduces the possible solutions to 8! = 40320 (x 8 = 322,560 individual queen placements)
• We can implement this in a recursive way
• However, note that we can prune a lot of possibilities from even this solution execution tree by realizing early that some placements cannot lead to a solution

## 8 Queens Problem

• Ex: No queens on the same diagonal
• See example on board
• Using this approach we come up with the solution as shown in 8-Queens handout
• JRQueens.java
• Idea of solution:
• Each recursive call attempts to place a queen in a specific column
• A loop is used, since there are 8 squares in the column
• For a given call, the state of the board from previous placements is known (i.e. where are the other queens?)
• If a placement within the column does not lead to a solution, the queen is removed and moved "down" the column

## 8 Queens Problem

• When all rows in a column have been tried, the call terminates and backtracks to the previous call (in the previous column)
• If a queen cannot be placed into column i, do not even try to place one onto column i+1 – rather, backtrack to column i-1 and move the queen that had been placed there
• Using this approach we can reduce the number of potential solutions even more
• See handout results for details

## Finding Words in a Boggle Board

• Another example: finding words in a Boggle Board
• Idea is to form words from letters on mixed up printed cubes
• The cubes are arranged in a two dimensional array, as shown below
• Words are formed by starting at any location in the cube and proceeding to adjacent cubes horizontally, vertically or diagonally
 F R O O Y I E S L D N T A E R E
• Any cube may appear at most one time in a word
• For example, FRIENDLY and FROSTED are legal words in the board to the right

## Finding Words in a Boggle Board

• This problem is very different from 8 Queens
• However, many of the ideas are similar
• But now the calls are in (up to) eight different directions:
• For letter [i][j] we can recurse to
• letter [i+1][j] letter [i-1][j]
• letter [i][j+1] letter[i][j-1]
• letter [i+1][j+1] letter[i+1][j-1]
• letter [i-1][j+1] letter[i-1][j-1]
• If we consider all possible calls, the runtime for this is enormous!
• Has an approx. upper bound of 16!  2.1 x 1013