1 Analogy2 Solving problems by brute force2.1 Combination padlock2.2 Factoring2.3 Eight queens3 An ADT for sequences4 Generating sequences: the backtrack tree5 Analysis of the backtrack algorithm6 The eight queens problem6.1 Reducing the size of the superset6.2 Pruning nonviable sequences6.3 Implementing the filter6.4 Speeding up the filter: adding state7 Some other problems that can be solved by brute force7.1 Shelf cutting7.2 Instant Insanity7.3 Permutations7.4 Sorting8 Finding a single solution9 Finding the best solution9.1 The traveling salesman problem10 Solutions of unknown length10.1 The Shortest path problem11 Chapter summary12 Exercises12.1 • Best checker move12.2 • Binary sequences12.3 • Map and graph coloring12.4 • The tree maze problem12.5 • The generalized maze problem12.6 • Permutations12.7 • Word jumblesChapter 14: Brute Force and BacktrackingChapter 13 Brute Force and Backtracking1 AnalogyIn the James Bond movie In Her Majesty’s Secret Service, agent 007 breaks into an officeat lunch time to steal some secret papers from a locked safe. He brings along with him ahigh-tech machine to assist in the safe cracking. But the process is not subtle; there is nolistening for tumblers to fall nor sandpapered fingertips. The machine works by trying allpossible combinations until the right one is found. Over the course of an hour, the machinefinds the combination and the safe opens. Commander Bond successfully steals the papers,saves the world, and, of course, rescues the girl.2 Solving problems by brute forceNot all problems yield to clever or subtle or direct solution methods. Sometimes we mustresort to brute force — simply trying lots of possibilities looking for the right one. Bruteforce, along with some less brutish variations, is the focus of this chapter. Brute force is aninformal term, but generally consists of generating the elements of a set that is known tocontain solutions and trying each element of the set. If a solution exists, and if the setgenerated contains at least one of the solutions, then sooner or later, brute force will findit. Similarly, if the set is known to contain all solutions, then all solutions will eventually befound. Thus, in a nutshell, the application of brute force requires that we devise a way togenerate a set that contains solutions, and a way to test each element of the generated set.We describe the basic brute force strategy for solving a problem as follows: generate theelements of a set that is known to contain solutions -- that is, a superset of the solution set-- and test each element of that set. To avoid the waste of storing a large number ofelements that are not solutions, we test each candidate as it is generated, and keep only thesolutions. If we regard the test as a filter that passes solutions and discards non-solutions,this approach can be represented by the following diagram.© 2001 Donald F. Stanat and Stephen F. WeissChapter 13 Brute force and Backtracking Page 2Superset generatorSolution filterSolutionsNon-solutions (discard)Figure 1. The brute force strategyThe superset generator produces the elements of the appropriate superset and passes eachone to the filter. The filter determines whether each element is a solution, adding it to thelist of solutions if it is, and discarding it if it is not. If the goal is to find a single solution,or if the problem is known to have only one solution, then the filter can shut down theprocess after finding the first solution. If, on the other hand, we want all solutions, thenthe process must continue until the superset generator has exhausted all possibilities.Another name for the technique we call 'brute force' is solution by superset.The brute force strategy can be applied, in some form, to nearly any problem, but it'srarely an attractive option. Nevertheless, for very small problems, or problems for whichno alternative is known, brute force is sometimes the method of choice. It is often convenient to view the solution of a problem as a sequence whose entries are alldrawn from a finite set of possible values, and whose length is fixed or at least bounded.Formally, the solution to such a problem is a sequence (a1,a2,a3,...,an) where each ai isdrawn from the set A and where A has a finite cardinality (contains a finite number ofelements). We'll refer to a sequence of length n as an n-sequence. The cardinality of thesuperset — the number of elements in the superset — is simply the cardinality of A raisedto the nth power.A brute force solution strategy is a reasonable problem solving strategy if it is difficult tosolve a problem directly, but easy both to generate elements of the superset, and todetermine, given an n-sequence, whether that n-sequence is a solution. Before discussingthe strategy in greater detail, we describe some problems that are appropriate to thismethod of solution.2.1 Combination padlockA combination lock is an example of a problem whose solution is a sequence. For commoncombination padlocks, the solution is a 3-sequence where each of the three elements is oneof the numbers on the dial. If the dial is numbered, for example, 0 through 49, then thesuperset has 50x50x50 = 125,000 elements. Any combination lock can be opened simply by trying all possibilities; the filter is simplythe act of yanking on the lock after a trial combination has been entered. CombinationPrinted January 14, 2019 02:51 PMChapter 13 Brute force and Backtracking Page 3locks are effective because trying all the possibilities takes a long time1. At the rate of tentries per minute, it would take more than eight and a half days to try all the combinations.2.2 FactoringGiven an integer n known not to be prime2, consider the problem of finding a divisor of ngreater than 1 and less than n. This can be viewed as a degenerate form of the sequenceproblem in which the solution is a “sequence” of length one, or a factor can be viewed as asequence of (decimal or binary) digits. An adequate superset consists of the set of integers{d: 1 < d < n}. Whichever we choose, we can check each candidate by simply dividing itinto n and seeing if there is a remainder. The solution strategy is straightforward, but thatdoesn't help much if n is very large. The difficulty in finding factors of an integer is the basis for a system of codes known aspublic key encryption. In a traditional encoding, the sender and receiver know the sameprivate key. The