Towers of Hanoi

Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.

The Towers of Hanoi problem is a simple problem whose solution is intractable. A tower of 3 is a simple exercise.

Change the 3 to 80 and the program will not finish even in 15,000,000,000 (15 billion) years!
The eager solution in Python would never finish. But the lazy program would continue to return results as called for the next value.

Here is the Python code [#1]

def eagerMove(n, a, c, b):
	if n != 0:
		eagerMove(n-1,a,c,b)
		print("move {0:d} from {1:s} to {2:s}".format(n,a,b))
		eagerMove(n-1,c,b,a)
eagerMove(3,"A","B","C")

Here is the output of the Python code.

move 1 from A to C
move 2 from A to C
move 1 from B to A
move 3 from A to C
move 1 from B to A
move 2 from B to A
move 1 from C to B

An "eager" program will run until every part of the program has run, even if not all parts are needed.

Change the 3 to 80 and the program will not finish even in 15,000,000,000 (15 billion) years!

Here is the Python code [#2]

def lazyMove(n, a, b, c):
	if n != 0:
		for move in lazyMove(n-1,a,c,b):
			yield move
		yield "move " + str(n) + " from " + a + " to " + b
		for move in lazyMove(n-1,c,b,a):
			yield move
nextMove = lazyMove(80, "A", "C", "B")
for i1 in range(0,10):
	print(next(nextMove))

Here is the output of the Python code.

move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to A
move 2 from C to B
move 1 from A to B
move 4 from A to C
move 1 from B to C
move 2 from B to A

A "lazy" program will compute each partial result as requested.

This program will print the moves, in order, as requested. If, however, an unbounded (practically infinite) number is requested, the program would never complete.