Recursion Index

Challenging problems

Here are a few problems involving Recursion that could give you a few sleepless nights, and a lot of satisfaction once you solve them.



I haven't attempted all of the following problems, but I know all of them involve Recursion. (You might be able to solve them using non-recursive methods as well.)


Minimum Volume

You are given the dimensions of a set of objects, each object being either a cube or a sphere or a cylinder. If one object can completely enclose another, then the second object can be placed inside the first. The total volume of all objects is thus reduced. Your program should find the placement of objects which gives you the least total volume, and display this volume.

You cannot put more than one object into any given object. You cannot have an object containing an object containing an object. [This simplifies the program.]

A cube is specified by its edge length 'a'.
[Volume of a cube = a^3.]
A sphere is specified by its radius 'r'.
[Volume of a sphere = (4 / 3) * PI * r^3.]
A cylinder is specified by its radius 'r' and height 'h'.
[Volume of a cylinder = PI * r^2 * h.]

For example, if three cubes of sides 6, 8 and 12 units are given, the minimum total volume required to hold all the three cubes is 12^3 + 6^3.

Assume that there are a maximum of 10 objects.



Rubik's Cube

I haven't been able to solve this one as yet.

Rubik's Cube is a famous game, entertaining both kids as well as adults. The Rubik's Cube is a cube with 6 different colors, one for each surface. The cube is 'chopped up' into 3 rows, 3 columns and 3 layers in such a way that rotation is possible about any of the three axes. By turning or twisting one layer (of 9 mini-cubes) at a time, the color arrangement is distorted. By repeated random rotation of layers, the cube is shuffled.

The object of the game is to get a shuffled Rubik's cube back to it's initial state, i.e., with only one color on each side.

So, make a program to accept a shuffled Rubik's cube, and twist and turn it back into order. Preferably with a neat graphical display. Get it working and you've made yourself a software product with market value. Get rich.

[I'm sorry if I haven't explained it properly. It's not so easy to explain. If you've never played with a Rubik's cube, it's quite hard to imagine it, and much harder to program it.]

Recursion Index April 2000

Click Here!