Towers of Hanoi

The computer solves the Towers of Hanoi puzzle by itself. Press a key from 2 to 8 to choose the number of rings, which are stacked on the first of three pegs above a checkered base. The program then moves the whole stack to peg 3, one ring at a time. Each ring rises off its peg, slides across and drops onto its new place. When the stack is finished it prints “OK IN n MOVES”, and pressing p starts again.

The program carries no author credit; the only text on screen is the title “TOWERS OF HANOI”.

Program Analysis

Rings and Pegs

Lines 40–110 hold the eight rings as DATA strings built from top-half block graphics, with quarter blocks at the ends of the even-numbered rings. Each ring is therefore half a character wider than the one above it. The strings go into r$(1)–r$(8), and the unused r$(9) stays as nine spaces to erase a ring. Line 10 POKEs UDG b with alternating 85 and 170 to make a checkerboard, and line 240 prints the base from it with the peg numbers 1, 2 and 3 set into it.

The Solution

The solver at lines 340–410 is recursive, with GO SUB 340 calling itself. Sinclair BASIC has no local variables, so it keeps the ring count n and the three peg numbers p, q and r as globals. Each call swaps them before it recurses and swaps them back afterwards, and m counts the moves. Lines 640–680 find the top of a peg by stepping down the screen with SCREEN$ until a cell is not a space. Block graphics and UDGs read back as an empty string, so any ring or the base stops the search. The position is kept as a single number, row × 33 + column, and INT splits it back apart. Lines 540–620 animate the move by printing the ring and then printing r$(9) over it at each step, going up, across in two-column steps and down.

Notable Techniques

• Recursion through GO SUB, with global variables swapped before and after each call.
• SCREEN$ used to sense where graphics are, relying on its empty result for any character it cannot match.
• Half-cell ring widths made from the quarter-block graphics.

Potential Issues

• With more than three rings the animation goes wrong. In testing, five rings were solved in the correct 31 moves, but pieces of rings were left behind on pegs 1 and 2. The top-of-peg search looks one column to the right of the peg’s centre, where the smallest ring has no graphics. The lift and slide loops then draw and erase relative to that row, so on some moves the erase appears to land on the wrong row.
• Lines 160–170 read INKEY$ three times. If the key is released after line 160 accepts it, VAL INKEY$ at line 170 appears to fail on an empty string.

This program came from an Oliger (JLO SAFE) disk in the SNUG library set and was converted for tape. It has no disk commands, so no changes were needed. It was tested in ZEsarUX on a stock TS2068: three rings were solved cleanly in seven moves.