Tower of Hanoi (Tower of Hanoi)

From Algorithm Wiki
Revision as of 13:05, 15 February 2023 by Admin (talk | contribs)
Jump to navigation Jump to search

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

Tower of Hanoi - Time.png

Space Complexity Graph

Tower of Hanoi - Space.png

Pareto Frontier Improvements Graph

Tower of Hanoi - Pareto Frontier.png