Bài toán Tháp Hà Nội Có thể còn ít người Việt Nam biết Tháp Hà Nội, nhưng rất nhiều thanh niên sinh viên trên toàn thế giới lại biết đến nó. Đó là vì, Tháp Hà Nội là tên một bài toán rất nổi tiếng trong Chương trình khoa học tính toán (Computing Science) dành cho sinh viên những năm đầu tại các trường đại học ở nhiều nơi trên thế giới. Tương truyền rằng ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời, Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư. Bài toán của Hoàng đế là: cho n cái đĩa (ngài không nói chính xác là bao nhiêu) và ba cái trục: A là trục nguồn, B là trục đích, và C là trục trung chuyển. Những cái đĩa có kích cỡ khác nhau và có lỗ ở giữa để có thể ***g vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên, những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục B, với điều kiện chuyển từng cái một và luôn phải đảm bảo quy định "nhỏ trên lớn dưới", biết rằng trục C được phép sử dụng làm trục trung chuyển? Vì địa vị quân sư được coi là vinh hiển nên có rất nhiều người dự thi. Từ vị học giả đến bác nông phu, họ đua nhau trình lên Hoàng đế lời giải của mình. Nhiều lời giải dài tới hàng nghìn bước, và nhiều lời giải có chữ "chuyển sang bước tiếp theo" (go to). Nhưng hoàng đế thấy mệt mỏi vì những lời giải đó, nên cuối cùng hạ chiếu: "Ta không hiểu những lời giải này. Phải có một cách giải nào khác dễ hiểu và nhanh chóng hơn". May mắn thay, cuối cùng đã có một cách giải như thế. Thật vậy, ngay sau khi chiếu vua ban ra, một vị cao tăng trông bề ngoài giống như một kỳ nhân hạ sơn tới xin yết kiến hoàng đế. Vị cao tăng nói: "Thưa Bệ hạ, bài toán đố đó dễ quá, hầu như nó tự giải cho nó". Quan trùm cấm vệ đứng hầu ngay bên cạnh vua quắc mắt nhìn gã kỳ nhân, muốn quẳng gã ra ngoài, nhưng Hoàng đế vẫn kiên nhẫn tiếp tục lắng nghe. "Nếu chỉ có 1 đĩa, thì...; nếu có nhiều hơn 1 đĩa (n>1), thì...", cứ thế vị cao tăng bình tĩnh giảng giải. Im lặng được một lát, cuối cùng Hoàng đế sốt ruột gắt: "Được, thế cao tăng có nói rõ cho ta lời giải hay không cơ chứ?". Thay vì giải thích tiếp, gã kỳ nhân mỉm cười thâm thúy rồi biến mất, bởi vì hoàng đế tuy giỏi giang nhưng rõ ràng là chưa hiểu ý nghĩa của phép truy hồi (recursion). Nhưng các bạn sinh viên ngày nay thì có thể thấy cách giải của vị cao tăng là hoàn toàn đúng. Toàn bộ đoạn chữ nghiêng ở trên được trích nguyên văn từ cuốn sách giáo khoa dành cho sinh viên ngành thuật toán và lập trình - "giải toán nâng cao và cấu trúc dữ liệu" (intermediate problem solving and data structures) do Paul Henman và Robert Veroff, hai giáo sư Đại học New Mexico, cùng biên soạn với Frank Carrano, giáo sư Đại học Rhode Island (Mỹ). Bạn nào chưa từng biết Tháp Hà Nội thì cũng nên "thử sức" một chút xem sao, vì đây là một trò chơi rất thú vị. Bạn có thể bắt đầu bằng bài toán 3 đĩa, rồi nâng lên 4 đĩa. Với 4 đĩa chắc bạn bắt đầu thấy rắc rối. Nâng tiếp lên 5 và cao hơn nữa, chẳng hạn n = 1 triệu, bài toán sẽ rắc rối đến mức không ai đủ kiên trì và đủ thì giờ để thử từng đĩa một. Vậy mà vị cao tăng dám nói là dễ quá! Xin tiết lộ, ấy là vì vị đó đã sử dụng phép truy hồi - một quy tắc toán học cho phép xác định số hạng thứ n từ số hạng đứng trước nó, tức số hạng thứ n-1. Cái giỏi của vị cao tăng là ông tìm ra một quy tắc chung, tức một thuật toán chung cho tất cả các bước chuyển đĩa. Vậy thay vì mô tả toàn bộ quá trình chuyển đĩa từng cái một như những thí sinh trước đó đã làm, vị cao tăng chỉ mô tả một quy tắc chung. Cứ làm theo quy tắc đó, lặp đi lặp lại chẳng cần suy nghĩ gì, rồi cuối cùng tự nhiên sẽ tới đích. Vì thế vị cao tăng nói rằng bài toán này "tự nó giải nó". Trong khoa học tính toán ngày nay, phép truy hồi là thuật toán cơ bản để lập trình. Ưu điểm của phương pháp truy hồi là ở chỗ nó dùng một công thức nhất định để diễn tả những phép tính lặp đi lặp lại bất chấp số lần lặp lại là bao nhiêu. Nếu số lần lặp lại lên đến con số hàng triệu hàng tỷ thì con người không đủ sức và thời gian để làm, nhưng máy tính thì có thể giải quyết trong chớp mắt. Điểm mạnh của computer là ở chỗ nó không hề biết e ngại và mệt mỏi trước những công việc lặp đi lặp lại lên đến hàng triệu hàng tỷ lần. Và vì thế, việc cộng tác giữa computer với con người là mô hình lý tưởng của lao động trí óc trong cuộc sống hiện đại. Về mặt lịch sử, Tháp Hà Nội được E. Lucas phát hiện từ năm 1883, nhưng mãi đến gần đây người ta mới nhận ra ý nghĩa hiện đại của nó. Hiện vẫn chưa rõ vì sao Lucas lại gọi chồng đĩa trong bài toán là Tháp Hà Nội, mà không gọi là Tháp Bắc Kinh, hay Tháp Tokyo. Tháp Hà Nội đã mở tung cánh cửa cho tương lai khi nhiều nghiên cứu lấy Tháp Hà Nội làm điểm xuất phát đã đạt được thành tựu mới: (1) Nâng câu hỏi của Tháp Hà Nội lên một mức cao hơn, sao cho số lần chuyển đĩa là nhỏ nhất. Các nhà toán học đã phát hiện ra rằng Tháp Hà Nội có cùng bản chất với bài toán tìm Đường Hamilton (Hamilton Path) trên một hình giả phương cấp n (n-Hypercube), một bài toán cũng rất nổi tiếng. (2) Nhà toán học D.G. Poole đã sáng tạo ra Lược Đồ Hà Nội - một tam giác có các đỉnh tương ứng với các cách sắp xếp đĩa trong Tháp Hà Nội, từ đó tìm ra những liên hệ lý thú giữa Tam giác Pascal với Lược đồ Hà Nội. Liên hệ này đã được công bố trong một công trình mang một cái tên đầy liên tưởng: Pascal biết Hà Nội (Pascal knows Hanoi). Hiện nay, tại một số đại học ở Australia, uy tín của sinh viên Việt Nam trong lĩnh vực lập trình được đánh giá ngang với sinh viên Ấn Độ - một cường quốc lập trình của thế giới, làm cho Tháp Hà Nội vốn đã nổi tiếng lại càng nổi tiếng hơn. Copi từ VnExpress Bạn co thể thí nghiệm trưc tiếp trên trang web này http://www.univ-rouen.fr/LMRS/Vulgarisation/Hanoi/hanoi.html
Mấy ông ở VNexpress còn bịa ra nguyên cả một câu chuyện cho bài toán rồi tận phía dưới mới ghi chú tác giả là Lucas, bó tay . Chữ Hanoi trong tên bài toán không hề ám chỉ Hà Nội. Bài toán được Lucas đưa ra vào 1883, quá cổ để biết đến VN. Em có xem trên 1 trang web, trong đó nói rằng chữ Hanoi thực chất có 2 dấu chấm ở trên, là tên một ngọn tháp của người Hindu, do đó nó còn có tên là Tower of Brahma puzzle . Theo truyền thuyết (của Tây ), các nhà sư cần mẫn chuyển 64 tấm từ cột 1 sang cột 2. Nếu chuyển xong hết thì thế giới sẽ đến ngày tận thế. Nhưng run-time của bài toán này ~ 2n, vậy là còn lâu mới phải lo Mọi người có thể xem thử cách giải bài này bằng khoảng 100 ngôn ngữ khác nhau ở đây
Wow, cảm ơn bạn sweetie đã khởi xướng 1 chủ đề có ý nghĩa thế này, và cũng cảm ơn các bạn gaveroche, imweasel đã giải thích rất tỉ mỉ. Vote cho mỗi bạn 5 sao nhé Tui cũng thắc mắc vấn đề này lâu rồi. Ở Hà Nội thì chắc là chỉ có Tháp Rùa bé xíu thôi, chẳng đẹp đẽ gì (xin lỗi các bạn HN nhé). Đã thế nguồn gốc thì hình như càng củ chuối hơn, nghe đâu là mộ của 1 ông quan hồi xưa muốn chơi ngông, xây mồ ở giữa hồ mà thôi. Còn bài toán Tháp Hà Nội thì nổi tiếng quá rồi, sánh ngang với những bài kinh điển như Traveling SalesPerson, Hamilton Circuit... Mấy bài này đều là những bài toán nổi tiếng nhất trong lớp NP. Hầu như các sách giáo khoa nhập môn về thuật toán đều đề cập đến nó. Ngày xưa học đến bài này cứ thắc mắc không biết tại sao nó lại mang tên như thế, lúc đầu còn tưởng có người VN nào nghĩ ra bài toán này chứ
Die Türme von HanoiThể loại: toán học giải trí Phát triển: di sản nhân loại Phát hành: giáo sư Dr. Édouard Lucas Ra mắt: 1883 Hệ máy: Mobile, POS, PPC, Commodore 64 Phiên âm tiếng Pháp là Tuerme Von Hanoi, hay Hanoi Towers, Tower Of Hanoi, Tháp Hà Nội (vt: ToH) là một trò chơi giải đố toán học. Đây là một game trí tuệ, điểm độc đáo đầu tiên là ở cái tên, lần đầu tiên thế giới biết đến một nước nửa thuộc địa ở Đông Nam Á qua tên thủ đô được đặt làm tựa đề cho một trò chơi (đồng thời cũng là kiểu chơi) mà sau này trở thành đối tượng độc đáo cho các nhà toán học say mê nghiên cứu. Trò chơi được tìm thấy xuất hiện lần đầu trong sách minh họa quan thoại Trung Quốc, nhưng có thể đã xuất hiện ở Đông Á từ thế kỷ 19 hoặc trước đó _ vì theo một truyền thuyết Ấn Độ có nói đến sự di chuyển càn khôn của 64 (ứng với thuyết Kinh Dịch) đĩa vàng giữa 3 tòa tháp Brahma, Brahmin, Golcone. Khi công việc hoàn thành là thời điểm kết thúc của vũ trụ. Đây là lý do mà đa số người Tây Á gọi trò chơi kiểu này là ‘Tòa tháp Brahma’ hay Tháp Phật. Năm 1883 nhà toán học người Pháp _ Édouard Lucas (1842 -1891) truyền bá trò chơi sang phương Tây (ToH mãi gắn liền với tên tuổi của ông do đã được đăng ký bản quyền cùng năm), ông cũng được cho là nhà bác học đầu tiên nghiên cứu toán tử ToH. Nhưng theo một giai thoại thì giữa thế kỷ XV, Lương Thế Vinh của Đại Việt đã tìm hiểu qui luật trên những chiếc đĩa – trạng lường gọi đây là ‘bài toán bất tận’ (kết luận này trùng quan điểm với điển tích ‘bài toán tự nó giải nó’). Để cho dễ nhớ Lucas chọn “Hà Nội” đặt tên cho game, với ý nghĩa công bố thuộc địa mới đô hộ của chính quyền thực dân Pháp. Ý tưởng của trò chơi đã phác họa lên mô hình sơ khai, làm cơ sở cho tháp Bá hộ Kim ra đời 3 năm sau đó. Và như một tiền định, các kiểu tháp ở Việt Nam đến nay không đâu có kiến trúc độc đáo như tháp Rùa: tầng dưới mang phong cách kiến trúc Âu châu với ô cửa cuốn gô-tích, xong phần mái cong bên trên giữ nguyên quy thức kiến trúc Việt Nam. Ba tầng tháp chồng lên nhau mô phỏng mức đơn giản nhất của game. F.E.A. Lucas mất ở tuổi 49 trong một tai nạn hi hữu: do người bồi bàn vô tình đánh vỡ đĩa tại buổi tiệc thường niên của Viện hàn lâm toán học quốc gia, gây lên một vết sước nhỏ bên má, dẫn đến nhiễm trùng máu (septicemia). Các phiên bản đầu tiên được Pháp sản xuất, minh họa ngoài bìa với lời giới thiệu “THÁP HÀ NỘI - Trò chơi trí tuệ của An Nam - Trò chơi được đem về từ Đông Kinh” và hướng dẫn. Đính kèm tiểu thuyết bán trong các hiệu sách ở Paris, Bắc Kinh, Tokyo và Sài Gòn. Trò chơi đến tay người chơi ban đầu chỉ qua 3 tờ giấy giới thiệu: vui và bổ ích, dễ học và dễ chơi, đồ chơi dễ làm. Cấp đơn giản nhất khởi đầu game là cho một tháp 3 tầng (đĩa với kích thước khác nhau) và 3 vị trí (cọc). Luật chơi: di chuyển tháp đó sang cọc cuối cùng (từ vị trí 1 sang 3), theo các quy tắc: 1 lần chỉ chuyển được 1 đĩa. Chỉ đĩa lớn hơn mới chấp nhận cái nhỏ hơn xếp chồng lên. Quá trình chồng và chuyển đĩa không yêu cầu tính liền kề (vị trí khoảng cách, hay đường kính). Đánh giá hoàn hảo mỗi màn chơi căn cứ vào số lần chuyển đĩa tối ưu. Lời giải 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. Chẳng thế mà chỉ với 3 cọc chơi, nếu số tầng tháp là 64 (ngầm hiểu là màn ‘phá đảo’) thì số lần di chuyển là 18.446.744.073.709.551.615 ( >5 tỷ thế kỷ - một đáp số đánh đố cả nhân loại +_+). Bước sang kỷ nguyên máy tính, game được viết đầu tiên bằng ngôn ngữ lập trình Pascal với những dòng lệnh giải thuật đơn giản, xong kiểu chơi không đổi và luôn hấp dẫn. Các phiên bản sau trở thành game java cho các thiết bị cầm tay, hay game flash. Tính năng tính thời gian được thêm vào, và mặc định 9 là số màn chơi cao nhất. Tháp Hà Nội còn 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), thuật giải mẫu viết bằng ngôn ngữ Prolog. Ngoài ra bài toán Tháp Hà Nội còn ứng dụng cả trong nghiên cứu tâm lý về cách giải quyết vấn đề. Tháp Luân Đôn là một biến thể khác, 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. Có lẽ đây là điều mà ngay chính tác giả khó có thể hình dung ra mức phổ biến của trò chơi, cả trong nghiên cứu thực tiễn lẫn trong giải trí đến vậy. Tuy chỉ thơm lây nhờ có tên thủ đô trong một trò chơi – kiểu chơi giải trí toán học nổi tiếng toàn thế giới, nhưng trên chặng đường dài của nền công nghiệp game non trẻ nước nhà, chúng ta hoàn toàn có thể làm ra được những tựa game made-in-Vietnam. Thậm chí ngay từ hôm nay, ToH đã có một đối thủ ngay tại quốc gia mà nó vinh dự được mang tên thủ đô, đó là Cờ Toán Việt Nam của bác Vũ Văn Bảy, trò chơi đã giành giải: Ấn tượng và Giải khuyến trong cuộc thi “Nhân tài đất Việt – 2008”. * Link chơi game: http://www.magentor.de/spiele/hanoi/hanoi_fertig.swf
