In our CS-2 course we cover a number of problem solving ...



Brute force and backtracking

Stephen Weiss

Department of Computer Science

University of North Carolina at Chapel Hill

CB# 3175, Sitterson Hall

Chapel Hill, NC 27599-3175

weiss@cs.unc.edu

In our CS-2 course we cover a number of problem solving techniques, one of which is brute force. By brute force we mean solving a problem by simply trying all possible candidate solutions looking for ones that work. Problems that submit to brute force solution require two attributes. First the space from which solutions are drawn must be finite. And second, the problem must be what I call an "oh yeah" problem. This is, a problem that may be very hard to solve, but when you are presented with a candidate, it is relatively easy to determine whether or not it is a solution. A good example is a combination lock. If the lock has 60 numbers on the dial and has a three-digit combination, then the solution space contains all possible three-digit combinations (x,y,z) when each is limited to 1...60, a total size of 603 or 216,000. But if presented with a candidate combination, it is a simple matter of dialing the combination and yanking on the lock to determine if the combination is correct. Given the power of machines available today, brute force turns out to be very reasonable, even when the solution space is very large.

Brute force problem solving is characterized by the figure below. The generator produces elements of the solution space, one at a time, and passes each to the filter. The filter determines whether the candidate is a solution. If so, it is passed to the outside; if not, it is discarded.

We restrict ourselves to problems whose solution is a sequence (s1, s2, …sn) where n is known in advance or at least bounded, and where each si is drawn from a finite pool. For simplicity, we’ll assume that each si is drawn from the same pool.

We assume availability of a Sequence class that maintains and manipulates a sequence. Methods in the sequence class include:

extend(x) Add x to the right end of the

sequence.

retract() Remove the rightmost element

of the sequence.

size() Return current sequence length

We can now use the classic backtracking algorithm to generate all possible sequences of length n. The iterative algorithm consists of two phases. In the first phase, we repeatedly add new elements to the sequence.

Extend(x) where x is something new, that is, something that has not already been added to the sequence at this point.

When this step fails, either because the sequence has reached maximal size or because there’s nothing new to do, then we go to the second phase, the backtrack phase (from which the algorithm gets its name).

Undo (retract) the most recently added

element of the sequence.

And then return to the first phase.

When the second phase fails (there’s nothing left to undo) the algorithm ends.

Instead of the iterative version, we use the simpler, recursive version of the backtrack algorithm. The algorithm below (in pseudo Java) displays all maximal length sequences.

backtrack(Sequence s)

{

For each si in the pool

{

s.extend(si)

if (sequence is maximal size)

{display sequence}

else

{backtrack(s)}

s.retract()

}

}

_

Converting this “all sequence generator” to a problem solver requires only that the maximal length sequences pass the filter before display.

For many problems, brute works well with no further modification. However, for some problems, the number of candidate sequences is so large that we must modify the basic backtracking algorithm to make it tractable.

The classic case study for brute force solution is the 8-queens problem: how can you place eight chess queens on a chessboard so that no queen can attack any of the others.[1] In its most general form in which each of the queens can occupy any square on the board, the size of the solution space is 648 or more than 280,000,000,00,000. Even on the most powerful, multi-gigahertz machines, there are simply too many possibilities to try them all.

We treat two strategies to improve efficiency. First, we attempt to reduce the size of the solution space. In the 8-queens problem, for example, we quickly realize that any solution must have each queen in her own row. Any placement of queens in which two or more queens share a row cannot be a solution. Hence we can reformulate the problem: how can we place the eight queens, one per row, so that there are no threats? This change reduces the size of the solution space to 88, a mere 16,777,216 or about sixteen million times smaller than the original. Now brute force starts to look practical.

The second efficiency measure, pruning, often yields even more dramatic improvements. With pruning, we test partially completed sequences for viability. A viable partial sequence is one that might possibly lead to a solution; a non-viable partial sequence is one that cannot possibly lead to a solution. For example, in the figures that follow, the first arrangement is viable while the second is non-viable[2].

viable

nonviable

By rejecting non-viable sequences early, we eliminate many elements of the solution space with a single test. For example, rejecting the non-viable arrangement above eliminates the need to check the 86 or more than a quarter of a million complete queen arrangements that begin this way. Hence a single test eliminates many possibilities from further consideration. By proper use of pruning, the 8-queen problem can be solved by testing only about 16,000 partial or full arrangements.

Adding pruning to the recursive backtrack algorithm is simple and can be done in several ways. We prefer the “test before extend” strategy in which we check an element for viability before adding it to the sequence. The method okToAdd(si) returns true if adding si to the currently viable sequence would result in a viable sequence.

backtrack(Sequence s)

{

For each si in the pool

{

if (s.okToAdd(si))

{

s.extend(si)

if (sequence is maximal size)

// Solution

{display sequence}

else

{backtrack(s)}

s.retract()

}

}

}

Another small change accommodates problems where the solution size is not known in advance, but is bounded.

backtrack(Sequence s)

{

For each si in the pool

{

if (s.okToAdd(si))

{

s.extend(si)

if (sequence is a solution)

// Solution

{display sequence}

else

if(sequence not max size)

{backtrack(s)}

s.retract()

}

}

}

Nifty exercises

Unfortunately, using the 8-queens problem as a case study in class eliminates this as a possible exercise. So we need other brute force problems. What follows are some exercises in more or less increasing order of difficulty.

Map coloring: given (possibly undrawable) map with n regions represented by an adjacency matrix (an nxn boolean matrix; entry (i,j) is true if map region i shares a border with region j), and a palate of c different colors, what are all the different ways to color the map so that adjacent regions are of different colors? Solutions are sequences of length n where si is the color of the ith region. Mapmakers have known for centuries that four colors suffice for any planar map. But the sufficiency of four colors was proven mathematically only relatively recently.

Running a maze: A rectangular maze is an nxm grid with one square designated as the start and another square designated as the finish. For each square, the path to each of its four neighbors (up, down, left, and right) may be open or blocked. From each square, there are four possible moves: up, down, left, and right. At each point along the way, we need consider only three of these since we don’t need to go back to the square from which we came; the backtracking algorithm will take care of that. A solution is a sequence of moves (up, down, left, right) that takes us from start to finish without violating the rules. A sequence is nonviable if it contains a move along a blocked path or if it brings us to a square already visited (to prevent infinite trudging around a loop). The length of a solution is not known in advance, but is bounded by n∗m. This problem is additionally nifty because it requires students to design data structures for representing the maze, and, if the maze contains loops, keeping track of which squares that have been visited.

Change making: Given an amount of money, such as $1, what are all the different ways to make that amount from coins? Solutions are sequences of coins that sum to $1. To prevent, multiple occurrences of the same solution, some canonical representation must be chosen (such as requiring that each coin in the sequence be no greater than its neighbor on the left). Here again, solution length is not known in advance, but is bounded by 100. Because of the penny, any viable partial set of coins will eventually lead to a solution. The problem can be made more interesting by specifying a different coin set. For example, if all the coins are an even denomination, then there's no way to generate an odd sum, and not all viable sequences lead to a solution. Or if we use the American coins but without the penny and nickel, then some viable partial sets cannot meet certain goals. For example, three quarters is viable, but cannot lead to an 80¢ goal. I gave a cash award of $1.91 (one of each coin) to the student who solved the problem most efficiently.

Zoo animal placement: Modern zoos often put compatible animals together in a large enclosure. For example, at the North Carolina Zoo, the zebras, ostriches and giraffes are housed together. However, it's a bad idea to include predator and prey in the same pen. Given a set of animals and an "eats" matrix (an nxn boolean matrix; element (i,j) is true if animal i eats animal j), what are the various ways to group the animals safely?

Word jumbles: Given a jumbled word, list all the real words that are permutations. This problem requires the help of a dictionary that serves to define "real" words[3]. To unscramble a word of, say, length 6, we generate all possible 6-letter sequences. To be viable, a sequence of letters must be a prefix of a real word (for example “bana” is a prefix of a real word, while “banx” is not) and the sequence must be a prefix of a permutation of the word we’re trying to unscramble.

Solving this puzzle requires methods to determine if one string is a prefix of another, if one string is a permutation of another, and if one string is a prefix of a permutation of another. It also requires data structures and methods for efficient storage and search of the dictionary. These methods formed the basis of an earlier assignment.

Cryptograms: Given a word encoded by a simple cipher, list all real words that have the specified pattern of letters. For example, if the encoded word is "QWDDPE", find all 6-letter words where the third and fourth letters are the same; the other letters are all different, and all letters are different from the encoded letters. Again a dictionary is needed. A sequence of letters is viable if it is a prefix of a real word and has the required letter pattern. A somewhat more challenging version of this problem allows some of the letters to be specified as would be the case part way through solving a cryptogram. Known letters are indicated in lower case; unknown letters are in upper case. For example, if the encoded word is “bWDDeE” then we’re looking for a real word (like “bitter”) whose first letter is ‘b’; whose fifth letter is ‘e’; the third and fourth letters are the same and different from the others, and none of the unknown (uppercase) letters match the decoded letters.

Word summing: We define 'a' to be 1; 'b' to be 2; etc., and define "adding" two words as adding their letter values, letter by letter. So for example, "abcde" + "ghijk" = "hjlnp" since 'a'+'g'=h; 'b'+'h'='j', etc. The assignment is to find the two words that add up to "stuff". Here again, a dictionary is needed. This problem is more challenging because the most efficient solution requires a different set of candidates for each letter. For example, the first letter of the solution words could be ‘a’…’r’. However, the fourth and fifth letters are restricted to ‘a’…’e’.

A more challenging version of this problem is to find all words in the dictionary that are the sum of two other dictionary words. There are also a few words that are the sum of two different pairs of words.

Nine square puzzle: given the nine squares shown in the attached diagram, arrange them into a three by three square so that wherever one square touches another, the sum of the touching numbers is zero. That is, a 1 must touch a –1; a 2 must touch a –2, etc. There are 9!*49 == 95,126,814,720 different ways to arrange the squares. Requiring a canonical arrangement (for example, requiring that the label of the puzzle piece in the upper left corner be the smallest of the four corner pieces) reduces the number by a factor of four to 23,781,703,680. Pruning is very effective allowing the puzzle to be solved by testing only about 76,000 configurations. If we think of the 3x3 square being built starting at the upper left and proceeding across the first row, then the second and then the third, adding a new piece to a partially built square is viable if it has not already been used, if its numbers match its neighbors to the left and above (if they exist), and if this is a corner piece, its name is greater than the piece in the upper left corner.

This was a particularly interesting exercise. I gave the puzzle out early in the course and encouraged student to try it. A very few actually solved it by hand; most became delightfully frustrated. They were very pleasantly surprised to see how quickly the problem yielded to brute force with appropriate pruning.

A copy of the assignment, executable program, and test data are available at cs.unc.edu/~weiss/Nifty03. For further reading on brute force and backtracking, including complete Java programs, see our chapter in brute force and backtracking (MS Word) at cs.unc.edu/~weiss/COMP114/

BOOK/13Backtracking.doc

-----------------------

[1] In chess, a queen can move horizontally, vertically, or along a diagonal. Hence if a queen occupies a particular square on the chess board, say row r and column c, then that queen could attack another queen in that same row, that same column, or along the two diagonals that pass through r,c.

[2] While the first figure is viable, it turns out that there are no solutions that begin this way. This illustrates that not all viable sequences lead to solutions.

[3] There’s a 25,000 word dictionary at cs.unc.edu/~weiss/COMP114/dict.txt.

-----------------------

Generator

Filter

Solutions

♣

Non-solutions

Trash

♣

Figure 1b: Non-viable

(solution impossible)

♣

♣

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download