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?

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.

Hamlet Project

Department of Computer Science

University of Utah