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