Tháp Hà Nội

Tháp Hà Nội là một trò chơi toán học

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ốc, Nhậ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ăm 1883.
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 nay 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.

Tờ thứ nhất

"THÁP HÀ NỘI

Trò chơi trí tuệ của An nam

Trò chơi được đem về từ Bắc Kì

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à ở Bắc Kì, 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ụ!

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 4 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.

Cách giải thực tế

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.

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ế.

Ứ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 chẩ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.

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 2ⁿ-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.