The Towers of Hanoi Puzzle: An Iterative Solution
Reading through the New Turing OmniBus: 66 Excursions in Computer Science, I turned upon the classic Towers of Hanoi Puzzle. The recursive solution, as many know, is mind-blowing in it’s simplicity; the first time I saw it, I remember saying, “OK… and then what?”
function hanoi( n, from, dest, aux )
{
if ( n == 1 )
printline 'Move the plate from ' + from + ' to ' + dest
else
hanoi( n-1, from, aux, dest )
hanoi( 1, from, dest, aux )
hanoi( n-1, aux , dest, from )
endif
end
The book goes on to present an iterative solution, as follows:
A. Always move the smallest disc first in a “clockwise” manner.
B. Then, move the smaller remaining disc onto the the other (in fact, that’s the only option).
C. Repeat A & B until finished.
Here’s a straightforward implementation (download).
#include <iostream> #include <vector> using namespace std; typedef unsigned int uint32; typedef int int32; typedef uint32 Stack; typedef uint32 Disc; Stack next_stack( Stack curr_stack ) { return ( curr_stack + 1 ) % 3; } int32 main( void ) { cout << "Calculating tower of hanoi moves" << endl; cout << "Enter the number of discs: "; uint32 num_discs = 0; cin >> num_discs; /** * Set up the stacks, with discs loaded onto the first one. */ vector<vector> stacks; for ( Stack stack_id = 0; stack_id < 3; stack_id++ ) { stacks.push_back( vector( 1, num_discs+1 ) // sentinel to avoid empty-stack logic ); } Stack curr_stack = 0; for ( Disc disc = num_discs; disc > 0; disc-- ) { stacks[curr_stack].push_back( disc ); } uint32 num_moves = 0; while ( true ) { /** * Smallest disc always moved one over. */ Disc disc1 = stacks[curr_stack].back(); stacks[curr_stack].pop_back(); curr_stack = next_stack( curr_stack ); stacks[curr_stack].push_back( disc1 ); num_moves++; /** * Remaining move is forced. */ Stack from_stack = next_stack( curr_stack ); Stack to_stack = next_stack( from_stack ); if ( stacks[from_stack].back() > stacks[to_stack].back() ) { Stack temp_stack = from_stack; from_stack = to_stack; to_stack = temp_stack; } Disc disc2 = stacks[from_stack].back(); stacks[from_stack].pop_back(); if ( stacks[from_stack].empty() ) { // we're done break; } stacks[to_stack].push_back( disc2 ); num_moves++; } cout << "Total moves:" << num_moves << endl; return 0; }
Is this particular iterative solution better than the recursive one? Aside from being a nice little exercise, no, it’s not that impressive. It takes longer to run than the recursive solution and requires more code. But, I think it’s easy to get how it works: “Move smallest clockwise then move what you can, repeat until we’re done.”.
There are iterative solutions out there that are much quicker, but they start to look like this:
void hanoi(void) { int x, fr, to; unsigned int i, j; for (x=1; x < (1 << N); x++) { i=(x|x-1)+1; to=(i+i/3)&3; i=x&x-1; fr=(i+i/3)&3; for(i=x, j=1; ; i>>=1, j++) { if(i&1) break; } } }
Themocracy