towers of hanoi variation pseudocode

Question

This is a variation to the original towers of hanoi problem. The same rules apply but instead of just one stack of n disks there are two. One stack of red disks on the left pole and another stack of purple disks on the right. The final configuration should be the purple on the left and red on the right. There are a total of 3 poles. I'm having trouble understanding/creating the pseudocode for an algorithm that solves this problem. Please help.

Answer 1

Since this is homework so giving you the answer would be wrong, I would suggest that you graphically solve the Towers of Hanoi problem.

Then, add in the modification, and see how your original solution works with the new change.

You should see where the original may fail, but it would be easier to make the modification while looking at it graphically.

If you pick a language that is easy to do graphic solutions then you can do this very fast.

For example, GWT may be a good choice, or Rails, though TCL/TK would also be easy.

Answer 2

The problem as you have presented it is not generally solvable. According to wikipedia, the most trivial multi-stack game has two stacks and four poles, and in general there are twice as many poles/pegs as stacks.

In the 2 stacks x 3 poles case you can see fairly quickly that for n > 1 you can't get very far. The smallest two discs occupy the top of two or one poles, and you can therefore never swap the second-smallest two discs since that always requires one temporary pole.