Brute Force Operations

Solving Complicated Problems

Suppose you are tasked with creating the perfect Software Development team within a certain budget. This is a complicated task in that you need to find out which of the applicants are the best programmers, and from that group, which of them will work comfortably and effectively with the rest of the group, and from that group, which of them are paid at a rate that will keep the whole team under the specified payroll budget. You are likely to have to try every combination of applicants available until you have found the best team.

The first thing to note for this situation is that it could take years if not decades. By the time you might have figured out the best combination of applicants, their knowledge, programming and interpersonal skills, and their pay rates, they will probably be obsolete. In other words, don't try this at home . . . or anywhere else for that matter.

What if there were a variety of ways to get from one side of a mountain to the other through a cave, following different paths as you come to them. The most complete way to get this done would be to try each path, and at each fork or branch in the subsequent paths, try each one of those, and so on. Again, not terribly difficult to describe but there could be a lot of different paths.

When we try all the possibilities without implementing any strategies to be more efficient, we are said to be employing a brute force, or exhaustive strategy.

For the science (and fun) of understanding this kind of combinatorial problem, Computer Scientists have come up with an interesting variety of scenarios in order to seek out and study more efficient and effective ways to solve these kinds of problems. The problems are not inherently difficult but because they are combinatorial, they can become very difficult to solve when the number of combined things gets very large. This kind of problem deserves our attention.

The key to recursive backtracking, or for any kind of recursion really, is that you want to solve a small part of the problem in one method call, and then pass the problem on by calling another method. Consider the classic factorial problem.

     5! is actually 5 * 4! and 4! is actually 4 * 3!, and so on.

     The five part of the problem is solved,

     and then the same method is called
     to solve the four part of the problem,

     and the process continues until the limiting case occurs
     when the value is one.

Recursion by itself is pretty interesting. However, it is possible that a solution that has been found during the recursion might not satisfy the larger need. For example, in the cave, it is possible that you have followed several paths and then you run into a dead end. If that happened, you could give up and start over but that would be really costly in terms of time (and processing overhead on a computer). In the case of recursive backtracking, if you come to an unworkable place, you just let that method stop and then see if the method that called it has other choices (such as trying a different path at the most recent fork in the cave.

By backtracking one space to the most recent fork, your process can try another fork and keep trying paths and forks until it finds the other side of the mountain. Sometimes it will progress forward, and sometimes a given path won't work so it falls back to the most recent decision-making point. And again, while this is a brute force method, it is very likely to work if there is, in fact, a solution available.

Let's Try One

The best way to understand recursive backtracking is to see it in action. In the next few sections, you will be given some example (classic) recursive backtracking problems and you can watch how they are run. This is an interesting part of Computing Science so get ready for an interesting challenge.