Thứ Tư, 8 tháng 5, 2013


Tháp Hà Nội

Bách khoa toàn thư mở Wikipedia
Một bộ mẫu của Tháp Hà Nội
Tháp Hà Nội là một trò chơi toán học hay trò chơi đố.

Mục lục

[ẩn]

[sửa] Luật chơi

Bìa hộp đựng những trò chơi Tháp Hà Nội được Pháp sản xuất lần đầu.
Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:
  • một lần chỉ được di chuyển một đĩa
  • một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)

[sửa] Lịch sử

Trò chơi Tháp Hà Nội có thể đã xuất hiện ở Đông Á từ thế kỷ 19 hoặc trước đó. Các đĩa được làm bằng sứ ởTrung QuốcNhật Bản và Việt Nam.
Trò chơi này được đưa sang phương Tây lần đầu bởi nhà toán học người Pháp Edouard Lucas vào năm1883.
Trò chơi này nhanh chóng được các nhà toán học nghiên cứu sau đó, và trở thành ví dụ về phương pháp giải đệ quy kinh điển trong dạy học và tin học. Lời giải tối ưu cho trò chơi có thể tìm thấy chính xác cho trường hợp 3 cọc. Nhưng khi mở rộng cho 4 cọc hoặc nhiều hơn, lời giải chính xác cho đến này vẫn chưa được khẳng định.
Các phiên bản đầu tiên được Pháp sản xuất, kèm theo tờ minh họa ngoài bìa và hai tờ hướng dẫn. Các tờ hướng dẫn này chứa nhiều thông tin lịch sử quý báu về trò chơi này.

[sửa] Tờ thứ nhất

Tờ hướng dẫn thứ nhất của trò chơi Tháp Hà Nội được Pháp sản xuất lần đầu.
"THÁP HÀ NỘI
Trò chơi trí tuệ của An nam
Trò chơi được đem về từ Đông Kinh
Bởi giáo sư N. CLAUS (của SIAM)
Trường Cao đẳng Quan Li-Sou-Stian!

Trò chơi này được tìm thấy, lần đầu, trong cuốn sách được minh họa Quan thoại FER-FER-TAM-TAM, đang được xuất bản, trong tương lai gần, bởi chính phủ Trung Hoa. Tháp Hà Nội có các đĩa, nhỏ dần, có số lượng thay đổi, mà chúng tôi làm bằng gỗ, có lỗ ở giữa. Ở Nhật Bản, Trung Quốc, và ở Đông Kinh, chúng được làm bằng sứ.
Trò chơi có mục đích là dỡ bỏ các đĩa, và đặt vào cột bên cạnh, theo các quy tắc nhất định.
Vui và bổ ích, dễ học và dễ chơi trong thành phố, ngoài nông thôn, trên chuyến du lịch, nó được tạo ra để mang đến kiến thức khoa học, giống mọi trò chơi kỳ thú và mới lạ của giáo sư N. CLAUS (của SIAM).
Chúng tôi trao giải thưởng 1000 franc, 100 nghìn franc, một triệu franc, và nhiều hơn, cho ai hoàn thành, bằng việc dùng tay di chuyển tháp Hà Nội với 64 đĩa, theo quy tắc của trò chơi. Chúng tôi nói ngay là cần số lần di chuyển là:
18 446 744 073 709 551 615
nhiều hơn năm tỷ thế kỷ!
Theo một truyền thuyết Ấn Độ, những người Brahmin đã tiếp nối nhau trong một thời gian dài để thay đổi Đền Bernares, di chuyển 64 đĩa vàng của Tòa tháp Brahma, trạm kim cương từ Golconde. Khi công việc hoàn thành, Tòa tháp và Brahmin sẽ đổ, và lúc đó là thời điểm kết thúc của vũ trụ!
-------------------- PARIS, BẮC KINH, TOKYO và SÀI GÒN
Trong các hiệu sách và tiểu thuyết
1883

Bản quyền đã giữ"

[sửa] Tờ thứ hai

Tờ hướng dẫn thứ hai của trò chơi Tháp Hà Nội được Pháp sản xuất lần đầu.
"Luật chơi và cách chơi trò THÁP HÀ NỘI

Đế đặt nằm ngang; các cột thẳng đứng. Các đĩa đặt theo thứ tự từ lớn đến nhỏ từ thấp lên cao; tạo nên một Tòa tháp. Trò chơi đòi hỏi di chuyển các đĩa, bằng cách đặt chúng vào cột bên cạnh, một đĩa trong một di chuyển, theo luật sau:
I. -- Sau mỗi di chuyển, các đĩa đều nằm trên một, hai, hoặc ba cột, theo thứ tự từ lớn đến nhỏ từ thấp đến cao.
II. -- Đĩa trên cùng của một trong ba cột đĩa được đặt vào cột rỗng.
III. -- Đĩa trên cùng của một trong ba cột đĩa được đặt lên một cột đĩa khác, nếu đĩa này nhỏ hơn các đĩa của cột này.

Trò chơi có thể dễ dàng tự khám phá, bằng việc giải quyết dần từ 3, 4, và 5 đĩa.

Trò chơi luôn giải được và đòi hỏi thời gian chơi lâu khoảng gấp đôi mỗi khi cho thêm một đĩa vào Tòa tháp. Bất kỳ ai giải được cho tám đĩa, ví dụ, chuyển các đĩa từ cột 1 sang cột 2, cũng sẽ biết cách giải cho chín đĩa. Chỉ cần chuyển tám đĩa sang cột 3, rồi chuyển đĩa thứ chín sang cột 2, và mang tám đĩa từ cột 3 về cột 2. Bây giờ, khi thêm một đĩa vào trò chơi, tổng số di chuyển tăng gấp đôi, cộng với một, so với trước.
Với tháp hai đĩaba lần di chuyển là đủ
--ba--bẩy--
--bốn--mười lăm--
--5--31--
--6--63--
--7--127--
--8--255--
vân vân.
Với tốc độ một di chuyển trong một giây, cần bốn phút để chuyển tám đĩa.
Các biến thể của trò chơi. -- Có thể thay đổi, đến vô cùng, điều kiện của bài toán tháp Hà Nội như sau. Khi bắt đầu, xếp các đĩa, theo thứ tự bất kỳ, lên một, hai, hay cả ba cột. Sau đó cần xây dựng lại tòa thấp trên một cột định trước. Với 64 đĩa, số lần di chuyển là khổng lồ; số này dài 50 chữ số.
Xem thêm chi tiết trong chương nói về Baguenaudier ở:
TOÁN HỌC GIẢI TRÍ bởi Mr. Édouard Lucas,
giáo sư toán học cao cấp tại Lycée Saint-Louis
Hai tập nhỏ, trong hai màu

Paris, 1883, bởi GAUTHER-VILLARS,
máy in của Académie des Sciences và Ecole Polytechnique
Quai des Augustins, 55"

[sửa] Văn học

Trong truyện khoa học viễn tưởng cổ điển Now Inhale (Hít vào nào) của Eric Frank Russell (trong Astounding Science Fiction tháng tư năm 1939, cũng như trong nhiều tuyển tập văn học khác), có một người anh hùng là tù nhân trên một hành tinh nơi mà luật địa phương bắt tù nhân chơi một trò chơi đến khi thắng hay thua thì thôi, sau đó sẽ tiến hành hành quyết ngay. Người anh hùng được biết là chỉ được chơi trong ngục với các thiết bị đơn giản tuân thủ luật chơi đã được định rõ trước khi chơi và không thể thay đổi được nữa khi trò chơi đã bắt đầu, và trò chơi có điểm kết thúc hữu hạn. Trò chơi và cuộc hành quyết sau đó sẽ được truyền hình khắp hành tinh, và xem người tù vô vọng cố gắng vật lộn với trò chơi càng lâu càng tốt là một thứ giải trí thật hấp dẫn; kỷ lục trước đây là mười sáu ngày. Người anh hùng đã tính toán rằng một con tàu giải cứu có thể mất cả năm hoặc hơn mới đến nơi được nên đã chọn chơi trò Tháp Hà Nội với 64 đĩa để đợi con tàu đến cứu. Khi dân địa phương nhận ra điều đó, họ rất tức tối nhưng theo luật chơi thì không thể làm gì được. Có lẽ họ sẽ thay đổi luật chơi đối với những tù nhân tương lai.

[sửa] Cách giải thực tế

(Trên) Lời giải cho 3 đĩa. (Dưới) Lời giải cho 4 đĩa.
Tái tạo lại trang trong phần này để xem sự tương quan giữa hai lời giải.
Nhiều cách giải đã được phát triển trong bài toán tháp Hà Nội. Ở đây giới thiệu một cách chơi thực tế.
Lần lượt di chuyển đĩa 1 và một trong những đĩa lớn hơn. Nếu có hai đĩa lớn hơn thì phải chuyển đĩa nhỏ lên đĩa lớn. Khi chuyển một đĩa số lẻ, luôn chuyển nó một cọc theo chiều kim đồng hồ; khi chuyển một đĩa số chẵn, luôn chuyển nó một cọc ngược chiều kim đồng hồ.
Một cách dễ hơn để nhớ cách giải là chú ý đĩa nhỏ nhất sẽ được chuyển mỗi lần di chuyển thứ hai, và luôn được chuyển theo cùng chiều. Trong các lần chuyển đĩa nhỏ nhất, chỉ có một lần chuyển hợp lệ mà không phải chuyển đĩa nhỏ nhất thêm một lần nữa.

[sửa] Cách giải khác

Mục đích của bài toán là thực hiện được yêu cầu của trò chơi. Dạng bài toán thông dụng nhất là: "Người chơi được cho ba cái cọc và một số đĩa có kích thước khác nhau có thể cho vào các cọc này. Ban đầu sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:
  • một lần chỉ được di chuyển một đĩa
  • một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)".
Bài toán này có lời giải chính xác. Tuy nhiên các mở rộng cho trường hợp có nhiều hơn ba cọc cho đến nay vẫn chưa được giải cặn kẽ.
Đa số các trò chơi dạng này có 8 đĩa. Đối với người mới chơi thì có vẻ khó nhưng thật ra thuật giải của nó hết sức đơn giản:

[sửa] Thuật giải đệ quy

  • đặt tên các cọc là A, B, C -- những tên này có thể chuyển ở các bước khác nhau (ở đây: A = Cọc Nguồn, B = Cọc Đích, C = Cọc Trung Gian)
  • gọi n là tổng số đĩa
  • đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng)
Để chuyển n đĩa từ cọc A sang cọc B thì cần:
  1. chuyển n-1 đĩa từ A sang C. Chỉ còn lại đĩa #n trên cọc A
  2. chuyển đĩa #n từ A sang B
  3. chuyển n-1 đĩa từ C sang B cho chúng nằm trên đĩa #n
Phương pháp trên được gọi là thuật giải đệ quy: để tiến hành bước 1 và 3, áp dụng lại thuật giải cho n-1. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụng cho n = 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc C.
Ngôn ngữ Pascal biểu diễn giải thuật trên là:
VAR n: Integer;
Procedure chuyen(sodia: Integer; CotNguon: Char; CotDich: Char; CotTG: Char);
   Begin
        If sodia>0 then begin
           chuyen(sodia-1, CotNguon, CotTG, CotDich);
           Writeln(CotNguon,'->',CotDich); { Dia lon nhat hien tai }
           chuyen(sodia-1, CotTG, CotDich, CotNguon)
        End;
   End;
BEGIN
     Write('Hay nhap so dia: '); Readln(n);
     chuyen(n,'A','C','B');//Thực hiện chuyển từ cột A sang cột C với cột B làm trung gian
     Readln;
END.
Ngôn ngữ C viết trên Dev C++
#include <cstdlib>
#include <iostream>
#include <conio.h>
 
using namespace std;
void chuyen(int sodia, char CotNguon, char CotDich, char CotTG)
{
        if (sodia>0)
        {
           chuyen(sodia-1, CotNguon, CotTG, CotDich);
           cout<<CotNguon<<"->"<<CotDich<<"\n";
           chuyen(sodia-1, CotTG, CotDich, CotNguon);
        }
}
int main()
{    char CotNguon,CotDich,CotTG;
    int n;
     cout<<"Hay nhap so dia: ";
     cin>>n;
     chuyen(n,'A','C','B');
     getch();
}
[sửa] Giải thích thuật giải
(Trên) Lời giải cho 3 đĩa. (Dưới) Lời giải cho 4 đĩa.
Tái tạo lại trang trong phần này để xem sự tương quan giữa hai lời giải.
Sau đây là dạng dễ xem hơn của thuật giải này:
  1. chuyển đĩa 1 sang cọc C
  2. chuyển đĩa 2 sang cọc B
  3. chuyển đĩa 1 từ C sang B sao cho nó nằm lên 2
Vậy ta hiện có 2 đĩa đã nằm trên cọc B, cọc C hiện thời trống
  1. chuyển đĩa 3 sang cọc C
  2. lặp lại 3 bước trên để chuyển 1 & 2 cho nằm lên 3
Mỗi lần dựng xong tháp từ đĩa i đến 1, chuyển đĩa i+1 từ cọc A là cọc xuất phát, rồi lại di chuyển tháp đã dựng lên đĩa i+1.

[sửa] Giải thuật bằng biểu diễn nhị phân

Các vị trí đĩa có thể xác định được trực tiếp từ biểu diễn nhị phân của số thứ tự di chuyển (cơ số 2 với một chữ số cho mỗi đĩa) trong đó các dãy 1 và các dãy 0 tượng trưng cho các dãy các đĩa liền nhau trên cùng cọc, và mỗi khi chữ số có thay đổi thì đĩa kế tiếp sẽ dời sang trái hay phải một cọc (hay chuyển sang cọc ngoài cùng phía đối diện). Chữ số ở đầu đại diện cho đĩa lớn nhất và nếu là chữ số 0 thì có nghĩa là đĩa lớn nhất không dời khỏi cọc xuất phát và ngược lại. Đặt các chữ số 1 và 0 luân phiên bên dưới các chữ số của một bước chuyển cho phép biết được di chuyển theo một chiều khi nó hợp với chữ số của bước chuyển tại nơi chữ số thay đổi và theo chiều kia khi nó không hợp. Do đó bước chuyển 00000000... có nghĩa là đặt 8 đĩa lớn nhất lên cọc ban đầu, bước chuyển 11111111... có nghĩa là đặt chúng lên cọc cuối cùng, và bước chuyển 11011000... có hai đĩa lớn nhất trên cọc đích, đĩa tiếp theo trên cọc xuất phát, hai đĩa tiếp theo ở cọc trung gian, và ba đĩa tiếp theo nữa trên cọc xuất phát, bất kể có thêm bao nhiêu chữ số đại diện các đĩa nhỏ hơn. Ta có thể dễ dàng tính được các vị trí của các đĩa trong một bộ tám mươi đĩa sau một số các bước tiến, nếu giới hạn đủ lớn để chứa nó. Việc dùng phương pháp đệ quy cho trường hợp tám mươi đĩa như thế này có thể không thực tế.

[sửa] Ứng dụng

Tháp Hà Nội là một bài toán thường được dùng để dạy về lập trình cơ bản. Một phiên bản bằng hình của bài toán này được lập trình trong chương trình soạn thảo emacs, có thể truy cập được bằng cách gõ M-x hanoi. Ngoài ra cũng có một thuật giải mẫu viết bằng ngôn ngữ Prolog.
Bài toán Tháp Hà Nội thường được dùng trong nghiên cứu tâm lý về cách giải quyết vấn đề. Cũng có những biến thể khác của bài toán này gọi là Tháp Luân Đôn dùng trong chuẩn đoán và điều trị thần kinh tâm lý đối với các chức năng thực hành.

[sửa] Trường hợp bốn cọc trở lên

Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy (tiếng Anh sequential advancement) để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở. Đây là một ví dụ tiêu biểu cho thấy một bài toán đơn giản, có thể giải được vẫn có thể trở thành khó hơn rất nhiều bằng cách hơi nới lỏng một số ràng buộc của nó.
Mặc dù không biết được chính xác cần bao nhiêu lần di chuyển, có thể có một vài kết quả tiệm cận. Có một "lời giải được coi như tối ưu" có thể áp dụng một cách đệ quy để tìm một lời giải–xem giải thích cũng như một vài biến thể của bài toán bốn cọc trong bài khảo sát của Paul Stockmeyer (tiếng Anh).
Mặc dù với số đĩa nhỏ thử nghiệm trên máy tính thì "lời giải được coi như tối ưu" này là thực sự tối ưu, nhưng nó vẫn chưa có một chứng minh tổng quát để coi là thực sự tối ưu. Tuy nhiên, những kết quả nghiên cứu trong năm 2004 (tiếng Anh) đã cho thấy lời giải được coi như tối ưu phải nằm trong cùng độ lớn với lời giải tối ưu.


Tower of Hanoi

From Wikipedia, the free encyclopedia
A model set of the Towers of Hanoi (with 8 disks)
An animated solution of the Tower of Hanoi puzzle forT(4,3).
The Tower of Hanoi or Towers of Hanoi , also called the Tower of Brahma or Towers of Brahma, is amathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.

Contents

[hide]

[edit] Origins

The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a legend about anIndian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks.Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, since that time. The puzzle is therefore also known as the Tower ofBrahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end.[1]It is not clear whether Lucas invented this legend or was inspired by it.
If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 264−1 seconds or roughly 585 billion years;[2] it would take 18,446,744,073,709,551,615 turns to finish.
There are many variations on this legend. For instance, in some tellings, the temple is a monastery and the priests are monks. The temple or monastery may be said to be in different parts of the world — including Hanoi, Vietnam, and may be associated with any religion. In some versions, other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day.
The Flag Tower of Hanoi may have served as the inspiration for the name.

[edit] Solution

The puzzle can be played with any number of disks, although many toy versions have around seven to nine of them. The game seems impossible to many novices, yet is solvable with a simple algorithm. The number of moves required to solve a Tower of Hanoi puzzle is 2n-1, where n is the number of disks.[3]

[edit] Iterative solution

The following solution is a simple solution for the toy puzzle.
Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle using the fewest number of moves to do so.[4]
It should perhaps be noted that this can be rewritten as a strikingly elegant set of rules:

[edit] Simpler statement of iterative solution

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:
  • make the legal move between pegs A and B
  • make the legal move between pegs A and C
  • make the legal move between pegs B and C
  • repeat until complete
For an odd number of disks:
  • make the legal move between pegs A and C
  • make the legal move between pegs A and B
  • make the legal move between pegs B and C
  • repeat until complete
In each case, a total of 2n-1 moves are made.

[edit] Recursive solution

A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. The following procedure demonstrates this approach.
  • label the pegs A, B, C—these labels may move at different steps
  • let n be the total number of discs
  • number the discs from 1 (smallest, topmost) to n (largest, bottommost)
To move n discs from peg A to peg C:
  1. move n−1 discs from A to B. This leaves disc #n alone on peg A
  2. move disc #n from A to C
  3. move n−1 discs from B to C so they sit on disc #n
The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial. This approach can be given a rigorous mathematical formalism with the theory of dynamic programming[5][6]
The Tower of Hanoi is often used as an example of a simple recursive algorithm when teaching introductory programming. Implementations in various languages may be found at the Hanoimania! website.

[edit] Logical analysis of the recursive solution

As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of h (h=height) disks from a starting peg A (f=from) onto a destination peg C(t=to), B being the remaining third peg and assuming tf. First, observe that the problem is symmetric for permutations of the names of the pegs (symmetric group S3). If a solution is known moving from peg A to peg C, then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If h=1, then simply move the disk from peg A to peg C. If h>1, then somewhere along the sequence of moves, the largest disk must be moved from peg A to another peg, preferably to peg C. The only situation that allows this move is when all smaller h-1 disks are on peg B. Hence, first all h-1 smaller disks must go from A to B. Subsequently move the largest disk and finally move the h-1 smaller disks from peg B to peg C. The presence of the largest disk does not impede any move of the h-1 smaller disks and can temporarily be ignored. Now the problem is reduced to moving h-1 disks from one peg to another one, first from A to B and subsequently from B to C, but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the h-1 problem to h-2, h-3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows. Identify the disks in order of increasing size by the natural numbers from 0 up to but not including h. Hence disk 0 is the smallest one and disk h-1 the largest one.
The following is a procedure for moving a tower of h disks from a peg A onto a peg C, with B being the remaining third peg:
  • Step 1: If h>1 then first use this procedure to move the h-1 smaller disks from peg A to peg B.
  • Step 2: Now the largest disk, i.e. disk h-1 can be moved from peg A to peg C.
  • Step 3: If h>1 then again use this procedure to move the h-1 smaller disks from peg B to peg C.
By means of mathematical induction, it is easily proven that the above procedure requires the minimal number of moves possible, and that the produced solution is the only one with this minimal number of moves. Using recurrence relations, the exact number of moves that this solution requires can be calculated by: 2h − 1. This result is obtained by noting that steps 1 and 3 take Th − 1 moves, and step 2 takes one move, giving Th = 2Th − 1 + 1.

[edit] Non-recursive solution

The list of moves for a tower being carried from one peg onto another one, as produced by the recursive algorithm has many regularities. When counting the moves starting from 1, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2. Hence every odd move involves the smallest disk. It can also be observed that the smallest disk traverses the pegs f, t, r, f, t, r, etc. for odd height of the tower and traverses the pegs f, r, t, f, r, t, etc. for even height of the tower. This provides the following algorithm, which is easier, carried out by hand, than the recursive algorithm.
In alternate moves:
  • move the smallest disk to the peg it has not recently come from.
  • move another disk legally (there will be one possibility only)
For the very first move, the smallest disk goes to peg t if h is odd and to peg r if h is even.
Also observe that:
  • Disks whose ordinals have even parity move in the same sense as the smallest disk.
  • Disks whose ordinals have odd parity move in opposite sense.
  • If h is even, the remaining third peg during successive moves is t, r, f, t, r, f, etc.
  • If h is odd, the remaining third peg during successive moves is r, t, f, r, t, f, etc.
With this knowledge, a set of disks in the middle of an optimal solution can be recovered with no more state information than the positions of each disk:
  • Call the moves detailed above a disk's 'natural' move.
  • Examine the smallest top disk that is not disk 0, and note what its only (legal) move would be: (if there is no such disc, then we are either at the first or last move).
  • If that move is the disk's 'natural' move, then the disc has not been moved since the last disc 0 move, and that move should be taken.
  • If that move is not the disk's 'natural' move, then move disk 0.

[edit] Binary solutions

Disk positions may be determined more directly from the binary (base 2) representation of the move number (the initial state being move #0, with all digits 0, and the final state being #2n−1, with all digits 1), using the following rules:
  • There is one binary digit (bit) for each disk
  • The most significant (leftmost) bit represents the largest disk. A value of 0 indicates that the largest disk is on the initial peg, while a 1 indicates that it's on the final peg.
  • The bitstring is read from left to right, and each bit can be used to determine the location of the corresponding disk.
  • A bit with the same value as the previous one means that the corresponding disk is stacked on top the previous disk on the same peg.
    • (That is to say: a straight sequence of 1's or 0's means that the corresponding disks are all on the same peg).
  • A bit with a different value to the previous one means that the corresponding disk is one position to the left or right of the previous one. Whether it is left or right is determined by this rule:
    • Assume that the initial peg is on the left and the final peg is on the right.
    • Also assume "wrapping" - so the right peg counts as one peg "left" of the left peg, and vice versa.
    • Let n be the number of greater disks that are located on the same peg as their first greater disk and add 1 if the largest disk is on the left peg. If n is even, the disk is located one peg to the left, if n is odd, the disk located one peg to the right.
For example, in an 8-disk Hanoi:
  • Move 0
    • The largest disk is 0, so it is on the left (initial) peg.
    • All other disks are 0 as well, so they are stacked on top of it. Hence all disks are on the initial peg.
  • Move 28-1
    • The largest disk is 1, so it is on the right (final) peg.
    • All other disks are 1 as well, so they are stacked on top of it. Hence all disks are on the final peg and the puzzle is complete.
  • Move 0b11011000 = 21610
    • The largest disk is 1, so it is on the right (final) peg.
    • Disk two is also 1, so it is stacked on top of it, on the right peg.
    • Disk three is 0, so it is on another peg. Since n is odd(n=3), it is one peg to the right, i.e. on the left peg.
    • Disk four is 1, so it is on another peg. Since n is even(n=2), it is one peg to the left, i.e. on the right peg.
    • Disk five is also 1, so it is stacked on top of it, on the right peg.
    • Disk six is 0, so it is on another peg. Since n is odd(n=5), the disk is one peg to the right, i.e. on the left peg.
    • Disks seven and eight are also 0, so they are stacked on top of it, on the left peg.
The source and destination pegs for the mth move can also be found elegantly from the binary representation of m using bitwise operations. To use the syntax of the C programming language, the mth move is from peg (m&m-1)%3 to peg ((m|m-1)+1)%3, where the disks begin on peg 0 and finish on peg 1 or 2 according as whether the number of disks is even or odd. Furthermore the disk to be moved is determined by the number of times the move count (m) can be divided by 2 (i.e. the number of zero bits at the right), counting the first move as 1 and identifying the disks by the numbers 0, 1, 2 etc. in order of increasing size. This permits a very fast non-recursive computer implementation to find the positions of the disks after m moves without reference to any previous move or distribution of disks.

[edit] Gray code solution

The binary numeral system of Gray codes gives an alternative way of solving the puzzle. In the Gray system, numbers are expressed in a binary combination of 0s and 1s, but rather than being a standard positional numeral system, Gray code operates on the premise that each value differs from its predecessor by only one (and exactly one) bit changed. The number of bits present in Gray code is important, and leading zeros are not optional, unlike in positional systems.
If one counts in Gray code of a bit size equal to the number of disks in a particular Tower of Hanoi, begins at zero, and counts up, then the bit changed each move corresponds to the disk to move, where the least-significant-bit is the smallest disk and the most-significant-bit is the largest.
Counting moves from 1 and identifying the disks by numbers starting from 0 in order of increasing size, the ordinal of the disk to be moved during move m is the number of times m can be divided by 2.
This technique identifies which disk to move, but not where to move it to. For the smallest disk there are always two possibilities. For the other disks there is always one possibility, except when all disks are on the same peg, but in that case either it is the smallest disk that must be moved or the objective has already been achieved. Luckily, there is a rule which does say where to move the smallest disk to. Let f be the starting peg, t the destination peg and r the remaining third peg. If the number of disks is odd, the smallest disk cycles along the pegs in the order f->t->r->f->t->r, etc. If the number of disks is even, this must be reversed: f->r->t->f->r->t etc.[7]

[edit] Visual solution

The divisions on a typical Imperial ruler can act as a key for the sequence of disc moves.
A visual solution may be discovered by looking closely at a ruler with imperial measurements.[8] These are typically subdivided into progressively smaller marks of 1 inch, 1/2 inch, 1/4 inch, 1/8 inch, 1/16 inch and 1/32 inch divisions. These can be considered to correspond to the progressively smaller discs.
Beginning with the smallest division corresponding to the smallest disc, each step along the ruler shows which disc will be moved next. A common ruler with 1/32 inch divisions can be used to solve a Tower of Hanoi puzzle with up to six discs.
Note that this only provides a key for the sequence of disc movements, not their direction. As mentioned earlier, the smallest disc should always be cycled through pegs A, B, C, then back to A (or C, B, A, then back to C).

[edit] Graphical representation

The game can be represented by an undirected graph, the nodes representing distributions of disks and the edges representing moves. For one disk, the graph is a triangle:
Tower of Hanoi 1-disk graph.svg
The graph for 2 disks is 3 triangles arranged in a larger triangle:
Tower of Hanoi-2.svg
The nodes at the vertices of the outermost triangle represent distributions with all disks on the same peg.
For h+1 disks, take the graph of h disks and replace each small triangle with the graph for 2 disks.
For 3 disks the graph is:
Tower of Hanoi-3.svg
  • call the pegs a, b and c
  • list disk positions from left to right in order of increasing size
The sides of the outermost triangle represent the shortest ways of moving a tower from one peg to another one. The edge in the middle of the sides of the largest triangle represents a move of the largest disk. The edge in the middle of the sides of each next smaller triangle represents a move of each next smaller disk. The sides of the smallest triangles represent moves of the smallest disk.
The game graph of level 7 shows the relatedness to the Sierpiński Triangle
In general, for a puzzle with n disks, there are 3n nodes in the graph; every node has three edges to other nodes, except the three corner nodes, which have two: it is always possible to move the smallest disk to the one of the two other pegs; and it is possible to move one disk between those two pegs except in the situation where all disks are stacked on one peg. The corner nodes represent the three cases where all the disks are stacked on one peg. The diagram for n+1 disks is obtained by taking three copies of the n-disk diagram—each one representing all the states and moves of the smaller disks for one particular position of the new largest disk—and joining them at the corners with three new edges, representing the only three opportunities to move the largest disk. The resulting figure thus has 3n+1 nodes and still has three corners remaining with only two edges.
As more disks are added, the graph representation of the game will resemble the Fractal figure, Sierpiński triangle. It is clear that the great majority of positions in the puzzle will never be reached when using the shortest possible solution; indeed, if the priests of the legend are using the longest possible solution (without re-visiting any position) it will take them 364-1 moves, or more than 1023 years.
The longest non-repetitive way for three disks can be visualized by erasing the unused edges:
Tower of Hanoi-3 Longest Path.svg
The circular Hamiltonian path for three disks is:
Tower of Hanoi-4 Longest Cycle.svg
The graphs clearly show that:
  • From every arbitrary distribution of disks, there is exactly one shortest way to move all disks onto one of the three pegs.
  • Between every pair of arbitrary distributions of disks there are one or two different shortest paths.
  • From every arbitrary distribution of disks, there are one or two different longest non selfcrossing paths to move all disks to one of the three pegs.
  • Between every pair of arbitrary distributions of disks there are one or two different longest non selfcrossing paths.
  • Let Nh be the number of non selfcrossing paths for moving a tower of h disks from one peg to another one. Then:
    • N1=2
    • Nh+1=(Nh)2+(Nh)3.
    • For example: N8≈1.5456x10795

[edit] Applications

The Tower of Hanoi is frequently used in psychological research on problem solving. There also exists a variant of this task called Tower of London for neuropsychological diagnosis and treatment of executive functions.
The Tower of Hanoi is also used as Backup rotation scheme when performing computer data Backupswhere multiple tapes/media are involved.
As mentioned above, the Tower of Hanoi is popular for teaching recursive algorithms to beginning programming students. A pictorial version of this puzzle is programmed into the emacs editor, accessed by typing M-x hanoi. There is also a sample algorithm written in Prolog.
The Tower of Hanoi is also used as a test by neuropsychologists trying to evaluate frontal lobe deficits.

[edit] General shortest paths and the number 466/885

A curious generalization of the original goal of the puzzle is to start from a given configuration of the disks where all disks are not necessarily on the same peg, and to arrive in a minimal number of moves at another given configuration. In general it can be quite difficult to compute a shortest sequence of moves to solve this problem. A solution was proposed by Andreas Hinz, and is based on the observation that in a shortest sequence of moves, the largest disk that needs to be moved (obviously one may ignore all of the largest disks that will occupy the same peg in both the initial and final configurations) will move either exactly once or exactly twice.
The mathematics related to this generalized problem becomes even more interesting when one considers the average number of moves in a shortest sequence of moves between two initial and final disk configurations that are chosen at random. Hinz and Chan Hat-Tung independently discovered [9] [10] (see also, [11] Chapter 1, p. 14) that the average number of moves in an n-disk Tower is exactly given by the following exact formula:
 \frac{466}{885}\cdot 2^n - \frac{1}{3} - \frac{3}{5}\cdot \left(\frac{1}{3}\right)^n +
\left(\frac{12}{29} + \frac{18}{1003}\sqrt{17}\right)\left(\frac{5+\sqrt{17}}{18}\right)^n +
\left(\frac{12}{29} - \frac{18}{1003}\sqrt{17}\right)\left(\frac{5-\sqrt{17}}{18}\right)^n.

Note that for large enough n, only the first and second terms are not converging to zero, so we get anasymptotic expression466/885\cdot 2^n - 1/3 + o(1), as n \to \infty. Thus, intuitively we could interpret the fraction of 466/885\approx 52.6\% as representing the ratio of the labor one has to perform when going from a randomly chosen configuration to another randomly chosen configuration, relative to the difficulty of having to cross the "most difficult" path of length 2n − 1 which involves moving all the disks from one peg to another. An alternative explanation for the appearance of the constant 466/885 , as well as a new and somewhat improved algorithm for computing the shortest path, was given by Romik. [12]

[edit] Variations

[edit] Cyclic Hanoi

Cyclic Hanoi is a variation of the Hanoi in which each disk must be moved in the same cyclic direction, in most cases, clockwise.[13] For example, given a standard three peg set-up, a given disk can be moved from peg A to peg B, then from B to C, C to A, etc. This can be solved using two mutually recursive procedures:
To move n discs clockwise from peg A to peg C:
  1. move n−1 discs clockwise from A to C
  2. move disc #n from A to B
  3. move n−1 discs counterclockwise from C to A
  4. move disc #n from B to C
  5. move n−1 discs clockwise from A to C
To move n discs counterclockwise from peg A to peg C:
  1. move n−1 discs clockwise from A to B
  2. move disc #n from A to C
  3. move n−1 discs clockwise from B to C

[edit] Four pegs and beyond

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.
The fact that the problem with four or more pegs is an open problem does not imply that no algorithm exists for finding (all of) the optimal solutions. Simply represent the game by an undirected graph, the nodes being distributions of disks and the edges being moves and use breadth first search to find one (or all) shortest paths moving a tower from one peg onto another one. However, even smartly implemented on the fastest computer now available, this algorithm provides no way of effectively computing solutions for large numbers of disks; the program would require more time and memory than available. Hence, even having an algorithm, it remains unknown how many moves an optimal solution requires and how many optimal solutions exist for 1000 disks and 10 pegs.
Though it is not known exactly how many moves must be made, there are some asymptotic results. There is also a "presumed-optimal solution" given by the Frame-Stewart algorithm. The related open Frame-Stewart conjecture claims that the Frame-Stewart algorithm always gives an optimal solution. The optimality of the Frame-Stewart algorithm has been computationally verified for up to 30 disks.[14]
For other variants of the four-peg Tower of Hanoi problem, see Paul Stockmeyer's survey paper.[15]

[edit] Frame-Stewart algorithm

The Frame-Stewart algorithm, giving a presumably-optimal solution for four (or even more) pegs, is described below:
  • Let n be the number of disks.
  • Let r be the number of pegs.
  • Define T(n,r) to be the number of moves required to transfer n disks using r pegs
The algorithm can be described recursively:
  1. For some k1 \leq k < n, transfer the top k disks to a single other peg, taking T(k,r) moves.
  2. Without disturbing the peg that now contains the top k disks, transfer the remaining n − k disks to the destination peg, using only the remaining r − 1 pegs, taking T(n − k,r − 1) moves.
  3. Finally, transfer the top k disks to the destination peg, taking T(k,r) moves.
The entire process takes 2T(k,r) + T(n − k,r − 1) moves. Therefore, the count k should be picked for which this quantity is minimum.
This algorithm (with the above choice for k) is presumed to be optimal, and no counterexamples are known.

[edit] Multistack Towers of Hanoi

U.S. patent number 7,566,057 issued to Victor Mascolo discloses multistack Tower of Hanoi puzzles with two or more stacks and twice as many pegs as stacks. After beginning on a particular peg, each stack displaces and is displaced by a different colored stack on another peg when the puzzle is solved. Disks of one color also have another peg that excludes all other colors, so that there are three pegs available for each color disk, two that are shared with other colors, and one that is not shared. On the shared pegs, a disk may not be placed on a different colored disk of the same size, a possibility that does not arise in the standard puzzle.
The simplest multistack game, Tower of Hanoi (2 x 4), has two stacks and four pegs, and it requires 3[T(n)] moves to solve where T(n) is the number of moves needed to solve a single stack classic of n disks. The game proceeds in seesaw fashion with longer and longer series of moves that alternate between colors. It concludes in reverse seesaw fashion with shorter and shorter such series of moves. Starting with the second series of three moves, these alternate series of moves double in length for the first half of the game, and the lengths are halved as the game concludes. The solution involves nesting an algorithm suitable for Tower of Hanoi into an algorithm that indicates when to switch between colors. When there are k stacks of n disks apiece in a game, and k > 2, it requires k[T(n)] + T(n-1) + 1 moves to relocate them.
The addition of a centrally located universal peg open to disks from all stacks converts these multistack Tower of Hanoi puzzles to multistack Reve's puzzles as described in the preceding section. In these games each stack may move among four pegs, the same combination of three in the 2 x 4 game plus the central universal peg. The simplest game of this kind (2 x 5) has two stacks and five pegs. A solution conjectured to be optimal interlocks the optimal solution of the 2 x 4 puzzle with the presumed optimal solution to Reve's puzzle. It takes R(n) + 2R(n-1) + 2 moves, where R(n) is the number of moves in the presumed optimal Reve's solution for a stack of n disks.

[edit] In popular culture

In the classic science fiction story Now Inhale, by Eric Frank Russell (Astounding Science Fiction April 1959, and in various anthologies), the human hero is a prisoner on a planet where the local custom is to make the prisoner play a game until it is won or lost, and then execution is immediate. The hero is told the game can be one of his own species', as long as it can be played in his cell with simple equipment strictly according to rules which are written down before and cannot change after play starts, and it has a finite endpoint. The game and execution are televised planet-wide, and watching the desperate prisoner try to spin the game out as long as possible is very popular entertainment; the record is sixteen days. The hero knows a rescue ship might take a year or more to arrive, so chooses to play Towers of Hanoi with 64 disks until rescue arrives. When the locals realize they've been had, they are angry, but under their own rules there is nothing they can do about it. They do change the rules, which will apply to any future prisoners. This story makes reference to the legend about the Buddhist monks playing the game until the end of the world, and refers to the game asarkymalarky. (The slang term "malarky", meaning nonsense, pre-dates this story by at least 30 years.[16] )
The puzzle is featured regularly in adventure and puzzle games. Since it is easy to implement, and easily recognised, it is well-suited to use as a puzzle in a larger graphical game (e.g. Knights of the Old Republic and Mass Effect[17]). Some implementations use straight disks, but others disguise the puzzle in some other form.

[edit] See also

[edit] Notes

  1. ^ Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. pp. 137.ISBN 0030846935.
  2. ^ Ivan Moscovich, 1000 playthinks: puzzles, paradoxes, illusions & games, Workman Pub., 2001 ISBN 0-7611-1826-8.
  3. ^ Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. pp. 197.ISBN 0821848143.
  4. ^ Troshkin, M. Doomsday Comes: A Nonrecursive Analysis of the Recursive Towers-of-Hanoi Problem, Focus, 95(2): 10-14 (in Russian).
  5. ^ Moshe Sniedovich (2002). "OR/MS Games: 2. The Towers of Hanoi Problem,"INFORMS Transactions on Education 3(1): 34–51.
  6. ^ Sniedovich, Moshe (2010). Dynamic Programming: Foundations and PrinciplesTaylor & Francis.ISBN 9780824740993.
  7. ^ [1][dead link]
  8. ^ Gardner, Martin (2008). Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi, Postscript to Chapter 6, Cambridge University Press.
  9. ^ A. Hinz (1989). "The Tower of Hanoi". Enseignement Mathematique 35: 289–321.
  10. ^ T. Chan (1988). "A statistical analysis of the towers of Hanoi problem". Internat. J. Comput. Math. 28: 57–65. doi:10.1080/00207168908803728.
  11. ^ Stewart, Ian (2004). Another Fine Math You've Got Me Into.... Courier Dover Publications.ISBN 0716723425.
  12. ^ D. Romik (2006). "Shortest paths in the Tower of Hanoi graph and finite automata". SIAM Journal on Discrete Mathematics 20 (3): 610–622. doi:10.1137/050628660.
  13. ^ T. D. Gedeon (1996). "The Cyclic Towers of Hanoi: An Iterative Solution Produced by Transformation".The Computer Journal 39 (4).
  14. ^ Korf, Richard E., and Ariel Felner (2007). "Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem"IJCAI: 2324–2329.
  15. ^ Paul Stockmeyer (1994). "Variations on the Four-Post Tower of Hanoi Puzzle"Congressus Numerantium 102: 3–12.
  16. ^ "Re: Malarkey a.k.a malarky". Phrases.org.uk. Retrieved 2009-11-03.
  17. ^ "Tower of Hanoi (video game concept)"iantbomb.com. Retrieved 2010-12-05.