# Tower of Hanoi (36B)

Question. Given 3 pegs and n disks, how can we move all the disks from src to dest such that larger disks cannot stack on top of smaller disks?

n: int

number of disks. This implies we have disk from radius 1 to n

src, dest, temp: List<int>

3 pegs that we can puts disks on. src initially has the disks [1\dots n] on it. dest, temp will be empty initially.

We can observe that:

• The largest disk has to go on the \tt{dest} peg first before everything else.

To do so, we need to move everything else to the \tt{temp} peg first. Now \tt{src} only has the largest disk and \tt{dest} is empty ⇒ so we can directly move.

Let’s consider a simple case with only 2 disks.

We do this 4-step process for any number of disks, except that 2 is the n-th disk and disk 1\sim n is in the position of 1.

function SolveHanoi(n, src, dest, temp):
	// do nothing if there's no disk
	if n > 0:
		// move disks 1…n-1 to temp
		SolveHanoi(n - 1, src, temp, dest)
		put disk n on dest
		// move disks 1…n-1 from temp to dest
		SolveHanoi(n - 1, temp, dest, src)

Github