Web Tutorial: The Tower of Hanoi (Part 3/3)

The final part of this web tutorial is here, and it's perhaps the most important thing we'll be doing.

Comment out this part. Or erase it.

'openpiece = pop(1)
'push 2, openpiece
'openpiece = pop(1)

Declare the variable operation. It's not "shared" because it isn't referenced in any subroutine or function.

DIM SHARED stack(3, 4) AS INTEGER
DIM SHARED top(3) AS INTEGER
DIM SHARED piece(4) AS STRING
DIM SHARED openpiece AS INTEGER
DIM operation AS INTEGER

Now, let's wrap the call to drawstack() in a While loop. As long as the third rod does not have four disks, the user has not won the game.

'openpiece = pop(1)
'push 2, openpiece
'openpiece = pop(1)

WHILE top(3) < 4
    drawstack
WEND

Now, set operation to 0. And create a While loop within the current While loop, that will run for as long as operation is 0.

WHILE top(3) < 4
    drawstack

    operation = 0

    WHILE operation = 0

    WEND
WEND

Move the cursor to below the drawn setup, and proceed to ask for input from the user. If openpiece is 0, that means all disks are on rods. So you have to ask which piece to remove. If it's not 0, then that means there is an open, unassigned piece and you need to place it on a rod. Whatever the user input it, assign the value to the variable selected.

WHILE top(3) < 4
    drawstack

    operation = 0

    WHILE operation = 0
        LOCATE 12, 2
        IF openpiece = 0 THEN
            INPUT "Remove piece  "; selected
        ELSE
            INPUT "Place onto rod"; selected
        END IF
    WEND
WEND

Next, set the value of operation to the value returned by the function doable(), passing in selected as an argument.

WHILE top(3) < 4
    drawstack

    operation = 0

    WHILE operation = 0
        LOCATE 12, 2
        IF openpiece = 0 THEN
            INPUT "Remove piece    "; selected
        ELSE
            INPUT "Place onto stack"; selected
        END IF

        operation = doable(selected)
    WEND
WEND

And then let's create the doable() function. First, set the function to return 0 by default.

SUB drawstack ()
FOR i = 1 TO 6
    LOCATE i + 1, 2

    FOR j = 1 TO 3
        IF i = 1 THEN
            drawpiece 0
        ELSE
            IF i = 6 THEN
                drawbase j
            ELSE
                drawpiece (stack(j, 6 - i))
            END IF
        END IF
    NEXT j
NEXT i

COLOR 15, 0
LOCATE 9, 2
PRINT "Open ";
IF openpiece = 0 THEN
    PRINT "(none)         ";
ELSE
    drawpiece openpiece
END IF
END SUB

FUNCTION doable (userinput)
doable = 0
END FUNCTION

Again, we set  a conditional revolving around whether openpiece is 0 or not.

FUNCTION doable (userinput)
doable = 0

IF openpiece = 0 THEN

ELSE

END IF
END FUNCTION

So if there is no disk currently unassigned to any rod, iterate from the first rod to the third. And if the appropriate element of the top array is greater than zero (which means that particular rod is not empty)...

FUNCTION doable (userinput)
doable = 0
IF openpiece = 0 THEN
    FOR i = 1 TO 3
        IF top(i) > 0 THEN

        END IF
    NEXT
ELSE

END IF
END FUNCTION

...and if the number of the topmost disk on that rod matches userinput, then set doable to 1 and openpiece to the value returned by pop(), with the number of that rod passed in as an argument. It's not the most efficient way ever, but it works. This also means that if the user enters in some funny number, it won't work.

FUNCTION doable (userinput)
doable = 0
IF openpiece = 0 THEN
    FOR i = 1 TO 3
        IF top(i) > 0 THEN
            IF stack(i, top(i)) = userinput THEN
                doable = 1
                openpiece = pop(i)
            END IF
        END IF
    NEXT
ELSE

END IF
END FUNCTION

Now, if openpiece isn't 0, that means you need to "push" the disk on the indicated rod. First, we need to ascertain that userinput is between 1 and 3. Seems a bit defensive, but it's necessary.

FUNCTION doable (userinput)
doable = 0
IF openpiece = 0 THEN
    FOR i = 1 TO 3
        IF top(i) > 0 THEN
            IF stack(i, top(i)) = userinput THEN
                doable = 1
                openpiece = pop(i)
            END IF
        END IF
    NEXT
ELSE
    IF userinput >= 1 AND userinput <= 3 THEN

    END IF
END IF
END FUNCTION

Now, you can place the disk on the rod only if the topmost disk on the rod is larger than the disk you're trying to "push", or if that rod is empty anyway.

FUNCTION doable (userinput)
doable = 0
IF openpiece = 0 THEN
    FOR i = 1 TO 3
        IF top(i) > 0 THEN
            IF stack(i, top(i)) = userinput THEN
                doable = 1
                openpiece = pop(i)
            END IF
        END IF
    NEXT
ELSE
    IF userinput >= 1 AND userinput <= 3 THEN
        IF stack(userinput, top(userinput)) > openpiece OR top(userinput) = 0 THEN

        END IF
    END IF
END IF
END FUNCTION

Set doable to 1 and execute the appropriate push().

FUNCTION doable (userinput)
doable = 0
IF openpiece = 0 THEN
    FOR i = 1 TO 3
        IF top(i) > 0 THEN
            IF stack(i, top(i)) = userinput THEN
                doable = 1
                openpiece = pop(i)
            END IF
        END IF
    NEXT
ELSE
    IF userinput >= 1 AND userinput <= 3 THEN
        IF stack(userinput, top(userinput)) > openpiece OR top(userinput) = 0 THEN
            doable = 1
            push userinput, openpiece
        END IF
    END IF
END IF
END FUNCTION

Now start the program and try to place the rods!

Some improvements

We need to keep track of the number of moves! So let's create a variable, moves. Set it to 0.

DIM SHARED stack(3, 4) AS INTEGER
DIM SHARED top(3) AS INTEGER
DIM SHARED piece(4) AS STRING
DIM SHARED openpiece AS INTEGER
DIM operation AS INTEGER
DIM SHARED moves AS INTEGER

piece(1) = " 1 "
piece(2) = "  2  "
piece(3) = "   3   "
piece(4) = "    4    "
openpiece = 0

FOR i = 1 TO 3
    FOR j = 1 TO 4
        stack(i, j) = 0
    NEXT j

    top(i) = 0
NEXT i

push 1, 4
push 1, 3
push 1, 2
push 1, 1
moves = 0

In the push() subroutine, increment moves at the end. This means that every "push" is counted as one move. Yes, that means after all the initial calls to push(), openpiece should be 4. Now see why you set moves to 0 after the push() calls?

SUB push (stackno, value)
top(stackno) = top(stackno) + 1
stack(stackno, top(stackno)) = value
moves = moves + 1
openpiece = 0
END SUB

Now, at the end of the drawstack() subroutine, after printing out openpiece, print out the moves used so far!

SUB drawstack ()
FOR i = 1 TO 6
    LOCATE i + 1, 2

    FOR j = 1 TO 3
        IF i = 1 THEN
            drawpiece 0
        ELSE
            IF i = 6 THEN
                drawbase j
            ELSE
                drawpiece (stack(j, 6 - i))
            END IF
        END IF
    NEXT j
NEXT i

COLOR 15, 0
LOCATE 9, 2
PRINT "Open ";
IF openpiece = 0 THEN
    PRINT "(none)         ";
ELSE
    drawpiece openpiece
END IF

LOCATE 10, 2
PRINT "Moves ";
PRINT moves;
END SUB

Go ahead, run the program again. Does the game keep track of the number of moves you have made?

Now, for one more improvement. Tell the user when they have won the game. After that While loop, call drawstack() again and move the cursor, then print the congratulatory message. This is logical because they can only have won if they've exited the While loop, meaning that top(3) is 4, which in turn means that all four disks are on the third rod.

WHILE top(3) < 4
    drawstack

    operation = 0

    WHILE operation = 0
        LOCATE 12, 2
        IF openpiece = 0 THEN
            INPUT "Remove piece  "; selected
        ELSE
            INPUT "Place onto rod"; selected
        END IF

        operation = doable(selected)
    WEND
WEND

drawstack
LOCATE 12, 2
PRINT "Congratulations! You have solved the Tower of Hanoi!"

Try it! I used 26 moves to solve the game. You can (and should) do a lot better.

Notes

This code hasn't been fully abstracted, which is geek-speak to say, if you want to modify the code to incorporate more disks or change the background color and such, there are a few places you have to change. Still, this is just an exercise in programming logic. Don't worry too much about it. I certainly didn't.

Sure, take the code and make it better. That's what sharing is for.

Many towering thanks,
T___T