# Tower of Hanoi (Tower of Hanoi)

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)$ | Exact | Deterministic | |

Recursion based | 1940 | $O({2}^n)$ | $O(n \log n)$ | Exact | Deterministic | |

Non-recursion based | 1940 | $O({2}^n)$ | $O(n)$ | Exact | Deterministic | |

Gray-code based | 1940 | $O({2}^n)$ | $O(n)$ | Exact | Deterministic | |

Hanoi graph | 2008 | $O({2}^n)$ | Exact | Deterministic | Time |