Chapter 13 Brute Force and Backtracking 1 Analogy In the James Bond movie In Her Majesty s Secret Service agent 007 breaks into an office at lunch time to steal some secret papers from a locked safe He brings along with him a high tech machine to assist in the safe cracking But the process is not subtle there is no listening for tumblers to fall nor sandpapered fingertips The machine works by trying all possible combinations until the right one is found Over the course of an hour the machine finds 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 force Not all problems yield to clever or subtle or direct solution methods Sometimes we must resort to brute force simply trying lots of possibilities looking for the right one Brute force along with some less brutish variations is the focus of this chapter Brute force is an informal term but generally consists of generating the elements of a set that is known to contain solutions and trying each element of the set If a solution exists and if the set generated contains at least one of the solutions then sooner or later brute force will find it Similarly if the set is known to contain all solutions then all solutions will eventually be found Thus in a nutshell the application of brute force requires that we devise a way to generate 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 the elements 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 of elements that are not solutions we test each candidate as it is generated and keep only the solutions 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 Weiss Chapter 13 Brute force and Backtracking Superset generator Solution filter Page 2 Solutions Non solutions discard Figure 1 The brute force strategy The superset generator produces the elements of the appropriate superset and passes each one to the filter The filter determines whether each element is a solution adding it to the list 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 the process after finding the first solution If on the other hand we want all solutions then the 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 s rarely an attractive option Nevertheless for very small problems or problems for which no 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 all drawn 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 a 1 a2 a3 an where each ai is drawn from the set A and where A has a finite cardinality contains a finite number of elements We ll refer to a sequence of length n as an n sequence The cardinality of the superset the number of elements in the superset is simply the cardinality of A raised to the nth power A brute force solution strategy is a reasonable problem solving strategy if it is difficult to solve a problem directly but easy both to generate elements of the superset and to determine given an n sequence whether that n sequence is a solution Before discussing the strategy in greater detail we describe some problems that are appropriate to this method of solution 2 1 Combination padlock A combination lock is an example of a problem whose solution is a sequence For common combination padlocks the solution is a 3 sequence where each of the three elements is one of the numbers on the dial If the dial is numbered for example 0 through 49 then the superset has 50x50x50 125 000 elements Any combination lock can be opened simply by trying all possibilities the filter is simply the act of yanking on the lock after a trial combination has been entered Combination Printed January 14 2019 02 51 PM Chapter 13 Brute force and Backtracking Page 3 locks are effective because trying all the possibilities takes a long time 1 At the rate of ten tries per minute it would take more than eight and a half days to try all the combinations 2 2 Factoring Given an integer n known not to be prime2 consider the problem of finding a divisor of n greater than 1 and less than n This can be viewed as a degenerate form of the sequence problem in which the solution is a sequence of length one or a factor can be viewed as a sequence 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 it into n and seeing if there is a remainder The solution strategy is straightforward but that doesn 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 as public key encryption In a traditional encoding the sender and receiver know the same private key The sender uses the key to encode messages the receiver uses the same key to decode the messages Privacy relies on others not being able to procure the key Security problems arise when a new key must be communicated In public key encryption each participant has two keys one public and one private Everyone knows the public key and can use it to encode a message to the owner of the key But once a message has been encoded with the public key only the holder of the private key can decode it The public key is based on a large integer that is known not to be prime The private key is based on a factor of that number The problem of discovering the private key can be made arbitrarily difficult by choosing a public key that is sufficiently large Note a similarity between public key encryption and the combination lock given enough time anyone can find the factors and decode the message But no scheme has been found that is substantially more efficient than testing all the possibilities As with the combination lock