Divide and Conquer

How can you determine the positions of all the rods? (As you certainly know by now, before you can teach a computer to solve a problem, you have to first figure out how to solve it for yourself.)

To solve a large problem like ours, it often helps to break the problem into several smaller pieces. Then, by solving all of smaller problems and combining those results, you can solve the original big problem. This problem-solving technique is called divide and conquer. You divide the original problem into smaller, easier-to-solve components and then you conquer each of the parts.

Let's try to use this technique on the rod stacking problem. How can we break this problem into smaller parts?

Click here for an answer.

How can we solve these simpler problems? We might start by noticing that except for the rods that touch the bin floor, all of the rods in the stack are supported by exactly two other rods. Take a look at the diagram again to make sure that this is the case.

Eric N. Eide
Hamlet Project
Department of Computer Science
University of Utah