Łamigłówka Wieże Hanoi


Na pozycji początkowej znajduje się n krążków, przy czym żaden krążek
większy nie leży na mniejszym:

HH
HHHH
HHHHHHHH
HHHHHHHHHHHH
HHHHHHHHHHHHHHHH
====================== ==================== ==================
Pozycja początkowa Pozycja pośrednia Pozycja końcowa



Przenieść krążki z pozycji początkowej na pozycję końcową z
wykorzystaniem pozycji pośredniej tak, by:
a) każdorazowo przenosić tylko pojedynczy krążek;
b) nigdy nie kłaść krążka większego na mniejszy.

Łamigłówkę tą rozwiązuje następująca rekurencja:

Aby przenieść n krążków z pozycji początkowej na pozycję końcową,
należy:

1. Przenieść n-1 krążków z pozycji początkowej na pozycję pośrednią
z wykorzystaniem pozycji końcowej.
2. Przenieść ostatni krążek z pozycji początkowej na pozycję końcową.

Teraz jesteśmy w podobnej sytuacji jak przed krokiem 1, z tą różnicą
że mamy przenieść n-1 krążków z pozycji pośredniej na pozycję końcową:
obecność największego krążka na pozycji końcowej nie ma bowiem znaczenia
dla dalszego przebiegu rozwiązania.