Monday, June 07, 2004

Instant Insanity

One of my coworkers is attending a “Creativity Class,” and he brought over a puzzle made from blocks of wood. Essentially there are four cubes. Each side of the cube is painted with one color out of a palette of four colors. The object of the puzzle is to arrange the blocks in a single row and have only one of each color present on each of the four sides of the column of blocks. You may get a better idea of this visually.

Being in a group of people intrigued by riddles and puzzles, we attempted to solve this puzzle. After about 30 minutes, we gave up on it for the day. Thanks to Eric Lippert, I am now re-interested in writing algorithms. So I wrote one to solve this problem. It would have taken less time to have written the algorithm in the first place.

My solution is iterative, although a recursive solution is easier. I’d encourage anyone to try writing some code to solve this one. In a few days, I’ll post some comments as to the mathematics involved and give my solution. Go ahead and use the colors from the link above as a starting point.


Hosein Shirazee said...

Hello , i have read your idea about instant-insanity and so be happy that you help me.
plz help how you write your alghoritm . i need it !
thank . Hosein Shirazee

Steven Bone said...

Hosein, Since this is problem is used in various computer science classes, I decided not to post or make available the code for this exercise.

I will give you a few hints:
1) There is a simple mathematical/logical answer to the puzzle that does not involve brute-force.
2) If you wish to use brute-force, do it intelligently.
3) An Object-oriented approach would be to create a Block class that describes the colors of each block using member variables. Some methods would be to rotate the block on the x-axis and flip the block on the y-axis. You would also need to get the current arrangement of colors that are the four outward facing sides after each rotation.
4) Before you start rotating blocks, see if the current arrangement is a feasible solution - with four blocks and four colors, you will need exactly 4 of each color exposed for the problem to be solvable.
5) Use a model - actually making the blocks and evaluating the proposed algorithm can be a great help. Most problems won't be as easy to model. Figure out how to and how many times you need to flip and rotate the block to expose the different sides.

Good Luck!