Klasyczne Wieże Hanoi - początkowo wszystkie krążki są na słupku 'A'. Rys. 1 Rozwiązaniem zagadki jest ustawienie wieży na słupku 'C' w jak najmniejszej liczbie ruchów, gdzie ruchem jest przeniesienie pojedynczego krążka ze słupka na słupek, z ograniczeniem że nie można kłaść większego krążka na mniejszy. Rys. 2 Dowolne Wieże Hanoi - na początku, krążki mogą być w dowolnej pozycji pod warunkiem, że nigdy większy krążek nie leży na mniejszym (patrz Rys. 3). Na końcu, krążki mogą być w innym dowolnym położeniu - pod tym samym warunkiem. * ) Rys. 3 | |
Rozwiązanie Wieży Hanoi
| |
| |
Rozwiązanie Wież Hanoi - 'regular' na 'perfect'Zacznijmy myśleć jak rozwiązać tę łamigłówkę. Rys. 4 Z tego ustawienia musimy tylko przenieść krążek 4 z 'A' na 'C' i następnie jakąś magiczną sztuczką przenieść 3 krążkową wieżę z 'B' na 'C'. Cofnijmy się myślą. Zapomnijmy o krążkach większych niż 3. Rys. 5 Zapomnijmy na moment o krążku 3 (patrz Rys. 6). Aby móc przenieść krążek 2
na słupek 'A' potrzebujemy zwolnić słupek 'A' (ponad cienką niebieską linią),
krążki mniejsze niż krążek 2 ustawione na słupku 'B'. Tak więc, naszym celem
jest teraz przeniesienie krążka 1 na słupek 'B'. Rys. 6 Więc przenieśmy go. Rys. 7 Opisane powyżej kroki są wykonane przez iteracyjny algorytm zastosowany w Wieże Hanoi, gdy kliknie się guzik "Help me". Ten guzik i funkcja dokonuje analizy aktualnego układu krążków i generuje tylko pojedynczy ruch, który prowadzi najkrótszą drogą do rozwiązania. To jest celowo tak zrobione. Gdy guzik 'Help me' jest ponownie kliknięty, algorytm powtarza wszystkie kroki analizy rozpoczynając od największego krążka - w tym przykładzie krążek 4 - i generuje następny ruch - krążek 2 ze słupka 'C' na słupek 'A'. Rys. 8 Jeśli jest potrzebny rekurencyjny lub iteracyjny algorytm , który generuje serię ruchów prowadzących do rozwiązania dowolnego układu Wież Hanoi należy użyć jakiś rodzaj back track programming, tzn. algorytm powinien pamiętać już wykonane kroki analizy i nie powtarzać analizy układu krążków od początku. Ale to już jest temat na osobne długie opowiadanie. | |