Tower of Hanoi

Description

The Tower of Hanoi puzzle consists of $n$ discs, no two of the same size, stacked on $p \geq 3$ vertical pegs, in such a way that no disc lies on top of a smaller disc. A permissible $move$ is to take the top disc from one of the pegs and move it to one of the other pegs, as long as it is not placed on top of a smaller disc. Initially, they are all stacked on the first peg. The goal is to end up with them all stacked on the last peg.

Parameters

n: number of discs

p: number of pegs

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Iteration based	1883	$O({2}^n)$	$O(n)$ auxiliary	Exact	Deterministic
Recursion based	1940	$O({2}^n)$	$O(n*log n)$ auxiliary	Exact	Deterministic
Non-recursion based	1940	$O({2}^n)$	$O(n)$ auxiliary	Exact	Deterministic
Gray-code based	1940	$O({2}^n)$	$O(n)$ auxiliary	Exact	Deterministic
Hanoi graph	2008	$O({2}^n)$		Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff