Divide and Conquer

Perhaps one of the most obvious ways to approach problem solving (because it also gets used in coding) is to divide the original problem into a number of smaller problems. Applying this approach does however have two considerations that do not apply to coding. The first is that you may not have any idea of how to divide up the problem into smaller problems and while this approach may get you a solution to the main problem it may be a long way from being the best solution.

Any solution is better than no solution at all and so if you have no idea of how to solve the overall problem the process of attempting to break it up into smaller problems that you may be able to solve can be considered progress. If you can come up with five smaller problems which in combination if solved would solve the original problem and you know how to solve one of them then you may be 20% closer to solving the original problem.

So how can you use this approach to find a solution to the problem?

Well the first thing that you need to do is to make use of what you already know. Consider all of the solutions and partial solutions that you have used in the past (whether for programming tasks or anything else). Will any of those either as is or with modification get you any closer to solving the problem. Even if none of them do, the mere fact of considering what you know will at the very least assist you in breaking up the problem into smaller ones. The solution you used for part of some other problem will not help with this one but a similar approach to dividing up the problem just might.

Often it may look like there is no way that the particular problem can be divided up. In practice any problem that is too complicated to solve in one go can always be divided into smaller problems. In the book "Think Like a Programmer" one example that is used to demonstrate how dividing up a problem into smaller problems can lead to a solution is a sliding number puzzle. With a 4x4 grid containing the numbers 1 through 15 and an empty space the problem is to make use of the empty space to slide the number around until they are in order 1 through 4 on the first row, 5 through 8 on the second, 9 through 12 on the third and 13 through 15 and the space on the last. The divide and conquer technique on this puzzle involves splitting the original problem in two. The first is to get the first row into position and the second is to solve a 4x3 grid. The second of these can then be further divided into two problems, get the rest of the first column into position and then solve a 3x3 grid. The final step is to divide the problem one more time into getting the rest of the second row into position and then solve a 3x2 grid. Solving a 3x2 grid is relatively easy (provided that it is in fact solvable) and in turn gives the necessary clues to solving the other parts of the overall problem that need to be solved first when you actually apply the solution. Breaking the original problem up into four pieces like this where each individual piece is far far easier to solve than trying to solve the original problem all at once makes solving the original problem much easier.

Notice that in the previous paragraph I included the text - provided that it is in fact solvable - now that isn't mentioned in the book. For the purpose of the example in the book a starting position for this puzzle was chosen that was solvable. In fact with this particular puzzle exactly half of the possible start position are solvable and the other half are not. One thing that is not obvious with this particular puzzle is that there are two possible parities. Swap the position of any two numbers and you switch the parity. If the starting position has the wrong parity then the closes that you can get to the wanted solution is to have all but two numbers in their correct positions with those last two numbers reversed and no way to swap them around the right way without reversing two other numbers. When this particular puzzle has the wrong parity then the puzzle is impossible to solve. Dividing up this problem to solve it piece at a time doesn't tell you that only half of the possible start positions are solvable and it doesn't tell you that any alternative solutions to the overall problem will also only be solvable half the time. If you started with one of the positions with the wrong parity and came to the conclusion that this particular way of breaking up the problem doesn't solve the problem for all possible start positions then you may very well end up wasting time trying to find alternate solutions to the problem that will work for all start positions before it finally occurs to you that this puzzle is only solvable half the time. Note that swapping parity involves removing two numbers from the grid to reverse them and so if the parity is the solvable one then no amount of sliding the numbers around will ever produce one of the unsolvable start positions.

Notice also that in looking at how to solve the problem that we did care which of the smaller problems that we looked at solving first. While the code to apply the solution needs to run in a particular order, working out the partial solutions can happen in any order. A program does not have to be written in the order that it will run in and doesn't have to be solved in the order that you write it in. As long as all of the pieces when assembled together and run in the right order solve the problem it doesn't matter how you got there.

Where a problem is too complex to solve all at once, finding any way at all to break it up into smaller simpler problems will get you closer to finding a solution. While the solution found using this approach may not be the most efficient possible for solving the entire problem, it will at least lead to more understandable code as that too will be broken up into easier to understand pieces. Having written the various pieces of code you may discover a way to combine them together to make the overall solution more efficient. Applying this will not necessarily be an appropriate thing to do. Unless the rearrangement makes the code significantly more efficient of the program needs to make use of all the efficiency available then you are better off keeping the code separated up to solve each of the smaller problems in turn. This will both make the code easier to understand and maintain and will also make it easier to reuse the code.


This article written by Stephen Chapman, Felgall Pty Ltd.

go to top

FaceBook Follow
Twitter Follow