Difficulty: Intermediate | Prerequisites: Recursion basics, graph theory fundamentals, Big-O notation
The Towers of Hanoi is a classic recursion problem that shows up in algorithm design courses as a vehicle for understanding divide-and-conquer strategies, recurrence relations, and exponential time complexity. In COSC 3320, the twist is modelling the problem as a graph where pegs are vertices and legal moves are edges, which constrains how disks can travel. You should already be comfortable writing recursive functions and analysing their time complexity with the Master Theorem. If you are not, revisit your notes on recursion and recurrence relations first.
The Towers of Hanoi on a graph uses three recursive calls (not two) because the graph structure forces disks through intermediate pegs. The recurrence is T(n) = 3T(n-1) + O(1), which solves to O(3^n) by the Master Theorem. The key insight is that the graph's edges define which peg-to-peg moves are legal, and the algorithm must route disks accordingly.
Towers of Hanoi
A mathematical puzzle where n disks of decreasing size must be moved from a source peg to a destination peg, one at a time, without ever placing a larger disk on a smaller one. Think of it as the simplest example of a problem that is easy to state but exponentially hard to solve.
Graph-based Hanoi
A variant where the pegs are modelled as vertices in a directed graph G = (V, E), and only edges in E represent legal direct moves. In simple terms, this means you cannot move a disk directly between any two pegs; you must follow the graph's edges.
Recurrence relation
An equation that defines a sequence recursively: each term is a function of preceding terms. In this context, T(n) = 3T(n-1) + c captures how the work triples with each additional disk.
Master Theorem
A formula for solving recurrences of the form T(n) = aT(n/b) + f(n). Here it generalises to T(n) = rT(n-d) + c, giving T(n) = O(r^(n/d)). Think of it as a shortcut that saves you from expanding the recurrence by hand.
Base case
The simplest instance of the problem that can be solved directly without recursion. For Hanoi, n = 1: move the single disk straight to the destination.
Vertices V = {Start, Aux1, Aux2, Dest}
Edges E = {(Start, Aux1), (Aux1, Aux2), (Aux2, Dest), (Dest, Start)}
The graph forms a cycle: Start -> Aux1 -> Aux2 -> Dest -> Start
A disk cannot jump directly from Start to Dest; it must pass through intermediary pegs
The function F(n, dest) moves n disks to the destination:
Base case (n = 1): Move the single disk directly to dest
Recursive case: Three recursive calls are needed because of the graph constraints:
F(n-1, A2): Move the top n-1 disks to Aux2 (1st recursive call)
Move disk n to Aux1
F(n-1, S): Move n-1 disks from Aux2 back to Start (2nd recursive call)
Move disk n to Dest
F(n-1, D): Move the remaining n-1 disks from Start to Dest (3rd recursive call)
In the standard (non-graph) Towers of Hanoi, any peg can reach any other peg directly, so two recursive calls suffice. Here the graph's edges forbid a direct Start-to-Dest move for intermediate transfers, forcing an extra pass through the cycle. Each level of recursion therefore spawns three subproblems of size n-1.
The recurrence is T(n) = 3T(n-1) + O(1)
Using the Master Theorem with r = 3 and d = 1: T(n) = O(r^(n/d)) = O(3^(n/1)) = O(3^n)
Compare this with standard Hanoi, which is O(2^n). The graph constraint makes the problem exponentially harder.
T(n) = 3\,T(n-1) + cT(n) = O(3^n)The first formula is the recurrence relation: each call to F(n) generates three calls to F(n-1) plus a constant amount of work (moving a single disk). The second is the closed-form solution, obtained by applying the Master Theorem.
The Towers of Hanoi pattern appears in backup rotation schemes (the "Grandfather-Father-Son" method uses Hanoi-like cycling). Graph-constrained variants model situations where not all transitions between states are permitted, such as robotic arm movement between fixed positions where certain paths are blocked.
Students often assume the graph-based version needs only two recursive calls, just like standard Hanoi. It does not. The graph constraints force a third call because disks cannot skip pegs.
Students sometimes confuse O(3^n) with O(n^3). The former is exponential (grows far faster). 3^10 is 59,049; 10^3 is 1,000.
The base case is sometimes written incorrectly as n = 0 instead of n = 1. With n = 0 there is nothing to move, which is valid but means the real work starts at n = 1.
Students sometimes forget that the graph is directed. The edges define one-way legal moves, so the algorithm must respect directionality.
This problem tests your ability to adapt a known algorithm to new constraints (the graph). Expect variations where the graph edges change.
You will likely need to write the recurrence and solve it. Make sure you can apply the Master Theorem to non-standard forms like T(n) = rT(n-d) + c.
Drawing the graph and tracing through a small example (n = 2 or 3) is a reliable way to verify your algorithm on an exam.
True or False: The graph-based Towers of Hanoi has a time complexity of O(2^n).
Fill in the blank: The recurrence relation for the graph-based Hanoi is T(n) = ___T(n-1) + c.
True or False: In the graph G given in this problem, a disk can move directly from Start to Dest.
Fill in the blank: The base case of the algorithm handles n = ___.
Q: Given a graph G = (V, E) with four pegs and a cycle structure, write a recursive algorithm to solve the Towers of Hanoi. How many recursive calls does each invocation make?
A: Three recursive calls per invocation. The first moves n-1 disks to an intermediate peg, the second moves them back to free the path, and the third moves them to the final destination. The graph constraints prevent direct transfers.
Q: What is the time complexity of the graph-based Towers of Hanoi, and how do you derive it?
A: O(3^n). The recurrence is T(n) = 3T(n-1) + c. Applying the Master Theorem with r = 3, d = 1 gives T(n) = O(3^(n/1)) = O(3^n).
Q: Why does the graph-based version require more moves than the standard Towers of Hanoi?
A: The standard version allows any peg-to-peg transfer, so only two recursive calls (and 2^n - 1 moves) are needed. The graph restricts which moves are legal, forcing an additional recursive pass to shuttle disks through intermediary pegs.
Q: If the graph had only two edges (forming a simple path rather than a cycle), how would the complexity change?
A: The number of recursive calls per level could increase further, depending on the path structure. The principle is the same: more constraints on moves means more intermediate transfers, which means a larger base in the exponential.
This connects to divide-and-conquer because the algorithm breaks the problem into smaller subproblems and combines the results. It also connects to dynamic programming in the sense that overlapping subproblems can arise in related puzzle variants. The graph modelling aspect ties directly to graph theory and state-space search, which appear later in the course when discussing shortest-path algorithms.
Towers of Hanoi, Tower of Hanoi, graph-based Hanoi, constrained Hanoi, recursive algorithm, recurrence relation, Master Theorem, exponential time complexity, O(3^n), divide and conquer, peg puzzle, disk transfer, COSC 3320, algorithm design