Stack programming task

The Towers of Hanoi is a classic game that can be implemented programmatically using three stacks.

Your task is to create a computer version of this game.

What is important here is the code that you write to implement the stacks. The code should be your focus, not the user interface. In an exam you may be asked to write algorithms to implement a stack. This page therefore includes some guidance on how to approach this particular task to get the most out of it.

Your game should have three poles, and need only use three discs. Your solution could be extended to work with more discs later.

You can have a go at an online version here Towers of Hanoi

Objective of the game

The objective of the game is to move all of the discs from the first pole to the third in the fewest number of moves.

Rules of the game

Only one disc can be moved at a time.

A disc can only be placed onto an empty pole, or onto a larger disc.

How to approach this task

1. It is tempting to begin by creating a complex user interface before you write any code. Don’t procrastinate! You should bake the cake before you put the icing on. To begin with, all you need is a form with a couple of command buttons, cmdPush and cmdPop.
2. Get one stack working properly first. Declare an array variable, aStack1(3). This array needs only three elements, since the pole will never contain more than three discs. Use a one based array for simplicity (type Option Base 1 at the top of the module). The array will need module level scope so that it can be manipulated by your push and pop programs.
3. Declare a variable to act as a pointer for the top of the stack, iTop1.
4. Declare a variable to indicate the maximum size of the stack, iMaxSize1.
5. Write the Push operation using the standard algorithm. For now, this can be implemented as a procedure. It should have one parameter, which is the value to push onto the stack. You should check for stack overflow, but do not concern yourself yet with legal game moves. Call this program from a button on the form.
6. Use the Locals Window, and step through your code, to observe the contents of the stack as you perform successive push operations.
7. Write the Pop operation using the standard algorithm. For now, this can be implemented as a procedure that simply removes a value from the top of the stack. Call this program from a button on the form.
8. Use the Locals Window, and step through your code, to observe the contents of the stack as you perform successive push followed by pop operations.
9. Now code up the second stack, aStack2(3) in the same way as the first and test it in the same way.
10. Write additional code to move a value from the first stack to the second. In other words, pop from stack 1 then push to stack 2. Again, do not concern yourself with valid moves yet, simply make sure you can transfer a value from one stack to another.
11. Now code up the third stack, aStack3(3) and write code to transfer a value from any stack to any other stack.
12. At this stage you have the basic processes in place, and can begin to add logic to check for legal moves. You might now consider using functions rather than procedures to reduce the amount of code needed. For example, the push function may be passed a value to push, and the name of the stack to push it on to.
13. Now you can give some more thought to the user interface. You could use the contents of listboxes to emulate the discs on the poles, or you could manipulate the visible properties of command buttons of different sizes. You could even use pictures; there is after all a finite number of legal disc configurations. You also need to consider how the user would specify a move, without having to clutter the form with command buttons.
14. Finally, you can consider keeping track of the number of moves and reporting when a player has won. Perhaps you should penalise attempts at illegal moves in some way.