Tower of Hanoi Problem: Two Dimensions

Question

I'm reading Knuths Concrete Mathematics and trying to solve my own questions as I read through the book. Right now, I want to solve a variant of the tower of Hanoi problem - solving for minimum number of moves T(n) to shift n disks from one tower to another given z towers.

This becomes a recurrence relation on two variables - so simply looking for T(n) with z=3wont help. I need a more powerful methodology with which to approach this problem.

I'm thinking you can represent towers as binary numbers of length n and then think about the situation as a finite state automaton. You move disks with bit shifts and there must be exactly nafter every operation.

Any ideas how to approach this multidimensional recurrence relation?

Answer 1

See this paper for some insight into the question: https://www2.bc.edu/~grigsbyj/Rand_Final.pdf.

It seems from the Wikipedia article that the optimal solution is an open problem -- are you talking about the recurrence relation for the "presumed-optimal" Frame-Stewart algorithm? – joriki