Bài toán Tháp Hà Nội

Tháp Hà Nội (còn được gọi là Bài toán Đền Benares ^[1] hoặc Tháp Brahma hoặc Tháp Lucas ^[2] và đôi khi được gọi là Tháp , hoặc đơn giản là câu đố kim tự tháp ^[3] ) là một trò chơi toán học hoặc câu đố bao gồm ba thanh và một số đĩa có đường kính khác nhau , có thể trượt vào bất kỳ thanh nào. Câu đố bắt đầu bằng các đĩa được xếp chồng lên nhau trên một thanh theo thứ tự kích thước giảm dần, đĩa nhỏ nhất ở trên cùng, do đó gần giống với hình nón . Mục tiêu của câu đố là di chuyển toàn bộ chồng đĩa sang một trong các thanh khác, tuân theo các quy tắc sau: ^[4]

Mỗi lần chỉ có thể di chuyển một đĩa.
Mỗi lần di chuyển bao gồm việc lấy đĩa trên cùng từ một trong các chồng và đặt nó lên trên một chồng khác hoặc lên một thanh rỗng.
Không được đặt bất kỳ đĩa nào lên trên một đĩa nhỏ hơn nó.

Với ba đĩa, câu đố có thể được giải trong bảy lần di chuyển. Số lần di chuyển tối thiểu cần thiết để giải câu đố Tower of Hanoi là 2 ⁿ − 1 , trong đó n là số đĩa.

Một giải pháp hoạt hình của câu đố Tháp Hà Nội cho T (4, 3)

Nguồn gốc

Câu đố được phát minh bởi nhà toán học người Pháp Édouard Lucas , lần đầu tiên được trình bày vào năm 1883 như một trò chơi do "N. Claus (de Siam)" (một chữ đảo ngược của "Lucas d'Amiens") phát hiện, ^[5]^[6]^[7] và sau đó được xuất bản dưới dạng một tập sách vào năm 1889 ^[8] và trong một tập sách xuất bản sau khi Lucas' Récréations mathématiques . ^[9] Đi kèm với trò chơi là một tập sách hướng dẫn, mô tả nguồn gốc được cho là của trò chơi ở Tonkin và tuyên bố rằng theo truyền thuyết , những người Bà la môn tại một ngôi đền ở Benares đã thực hiện chuyển động của "Tháp thiêng Brahma ", bao gồm sáu mươi bốn đĩa vàng, theo cùng các quy tắc như trong trò chơi, và việc hoàn thành tòa tháp sẽ dẫn đến ngày tận thế. ^[10] Nhiều biến thể về truyền thuyết này liên quan đến bản chất cổ xưa và huyền bí của câu đố đã xuất hiện gần như ngay lập tức. ^[5]

Triển lãm tương tác Tháp Hà Nội tại Bảo tàng Universum của Thành phố Mexico

Nếu truyền thuyết là đúng, và nếu các linh mục có thể di chuyển đĩa với tốc độ một đĩa mỗi giây, sử dụng số lần di chuyển nhỏ nhất, họ sẽ mất 2 ⁶⁴ − 1 giây hoặc khoảng 585 tỷ năm để hoàn thành, ^[11] tức là khoảng 42 lần tuổi hiện tại ước tính của vũ trụ .

Có nhiều biến thể của truyền thuyết này. Ví dụ, trong một số câu chuyện, ngôi đền là một tu viện , và các linh mục là các nhà sư . Ngôi đền hoặc tu viện có thể ở nhiều địa điểm khác nhau bao gồm cả Hà Nội , và có thể liên quan đến bất kỳ tôn giáo nào. Trong một số phiên bản, các yếu tố khác được đưa vào, chẳng hạn như thực tế là tòa tháp được xây dựng vào thời kỳ đầu của thế giới, hoặc các linh mục hoặc nhà sư chỉ có thể di chuyển một lần mỗi ngày.

Giải pháp

Câu đố có thể chơi bằng bất kỳ số lượng đĩa nào, mặc dù nhiều phiên bản đồ chơi có khoảng 7 đến 9 đĩa. Số lượt di chuyển tối thiểu cần thiết để giải câu đố Tháp Hà Nội là 2 ⁿ − 1 , trong đó n là số đĩa. ^[12] Đây chính xác là số Mersenne ^thứn không có yêu cầu về tính nguyên tố.

Giải pháp lặp lại

Một giải pháp đơn giản cho trò chơi xếp hình đồ chơi là luân phiên di chuyển giữa mảnh nhỏ nhất và mảnh không nhỏ nhất. Khi di chuyển mảnh nhỏ nhất, hãy luôn di chuyển nó đến vị trí tiếp theo theo cùng một hướng (sang phải nếu số mảnh ban đầu là chẵn, sang trái nếu số mảnh ban đầu là lẻ). Nếu không có vị trí tháp nào theo hướng đã chọn, hãy di chuyển mảnh đến đầu đối diện, nhưng sau đó tiếp tục di chuyển theo đúng hướng. Ví dụ, nếu bạn bắt đầu với ba mảnh, bạn sẽ di chuyển mảnh nhỏ nhất đến đầu đối diện, sau đó tiếp tục theo hướng bên trái. Khi đến lượt di chuyển mảnh không nhỏ nhất, chỉ có một nước đi hợp lệ. Làm như vậy sẽ hoàn thành trò chơi xếp hình trong ít nước đi nhất. ^[13]

Câu lệnh đơn giản hơn về giải pháp lặp lại:

Giải pháp lặp đi lặp lại tương đương với việc thực hiện nhiều lần chuỗi các bước sau cho đến khi đạt được mục tiêu:

Di chuyển một đĩa từ chốt A sang chốt B hoặc ngược lại, tùy theo nước đi nào hợp lệ.
Di chuyển một đĩa từ chốt A sang chốt C hoặc ngược lại, tùy theo nước đi nào hợp lệ.
Di chuyển một đĩa từ chốt B sang chốt C hoặc ngược lại, tùy theo nước đi nào hợp lệ.

Theo cách tiếp cận này, ngăn xếp sẽ dừng ở chốt B nếu số đĩa là lẻ và ở chốt C nếu số đĩa là chẵn.

Giải pháp đệ quy

Chìa khóa để giải một bài toán đệ quy là nhận ra rằng nó có thể được chia nhỏ thành một tập hợp các bài toán con nhỏ hơn, mỗi bài toán con đều áp dụng cùng một quy trình giải chung mà chúng ta đang tìm kiếm ^{[ cần trích dẫn ]} , và sau đó giải pháp tổng thể được tìm thấy theo một cách đơn giản nào đó từ các giải pháp của các bài toán con đó. Mỗi bài toán con được tạo ra này "nhỏ hơn" đảm bảo rằng trường hợp cơ sở cuối cùng sẽ đạt được. Đối với Tháp Hà Nội:

dán nhãn các chốt A, B, C,
hãy để n là tổng số đĩa và
đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng).

Giả sử tất cả n đĩa được phân bổ theo các sắp xếp hợp lệ giữa các chốt; giả sử có m đĩa trên cùng trên một chốt nguồn và tất cả các đĩa còn lại đều lớn hơn m , do đó chúng có thể được bỏ qua một cách an toàn; để di chuyển m đĩa từ chốt nguồn đến chốt đích bằng cách sử dụng một chốt dự phòng mà không vi phạm các quy tắc:

Di chuyển m − 1 đĩa từ nguồn đến chốt dự phòng , theo cùng quy trình giải chung . Các quy tắc không bị vi phạm, theo giả định. Điều này để lại đĩa m như một đĩa trên cùng trên chốt nguồn.
Di chuyển đĩa m từ chốt nguồn đến chốt đích , được đảm bảo là một bước di chuyển hợp lệ, theo giả định — một bước đơn giản .
Di chuyển m − 1 đĩa mà ta vừa đặt lên đĩa dự phòng, từ đĩa dự phòng đến chốt đích theo cùng quy trình giải tổng quát , sao cho chúng được đặt lên trên đĩa m mà không vi phạm các quy tắc.
Trường hợp cơ bản là di chuyển 0 đĩa (ở bước 1 và 3), nghĩa là không làm gì cả—điều này không vi phạm các quy tắc.

Giải pháp Tháp Hà Nội đầy đủ sau đó di chuyển n đĩa từ chốt nguồn A đến chốt đích C, sử dụng B làm chốt dự phòng.

Cách tiếp cận này có thể đưa ra bằng chứng toán học chặt chẽ bằng phương pháp quy nạp toán học và thường được dùng làm ví dụ về đệ quy khi dạy lập trình.

Minh họa về giải pháp đệ quy cho câu đố Towers of Hanoi với 4 đĩa. Trong tệp SVG, hãy nhấp vào nút màu xám để mở rộng hoặc thu gọn tệp

Phân tích logic của giải pháp đệ quy:

Như trong nhiều câu đố toán học, việc tìm ra lời giải trở nên dễ dàng hơn khi giải một bài toán tổng quát hơn một chút: cách di chuyển một tháp đĩa h (chiều cao) từ một chốt xuất phát f = A (từ) đến một chốt đích t = C (đến), B là chốt thứ ba còn lại và giả sử t ≠ f . Trước tiên, hãy quan sát rằng bài toán này đối xứng với các hoán vị tên của các chốt ( nhóm đối xứng S ₃ ). Nếu biết một lời giải khi di chuyển từ chốt A đến chốt C , thì bằng cách đổi tên các chốt, có thể sử dụng cùng một lời giải cho mọi lựa chọn chốt xuất phát và đích khác. Nếu chỉ có một đĩa (hoặc thậm chí không có đĩa nào cả), thì bài toán này trở nên đơn giản. Nếu h = 1, thì di chuyển đĩa từ chốt A đến chốt C . Nếu h > 1, thì ở đâu đó dọc theo trình tự di chuyển, đĩa lớn nhất phải được di chuyển từ chốt A sang một chốt khác, tốt nhất là đến chốt C . Tình huống duy nhất cho phép di chuyển này là khi tất cả các đĩa h − 1 nhỏ hơn đều nằm trên chốt B. Do đó, trước tiên tất cả các đĩa h − 1 nhỏ hơn phải đi từ A đến B. Sau đó di chuyển đĩa lớn nhất và cuối cùng di chuyển các đĩa h − 1 nhỏ hơn từ chốt B đến chốt C. Sự hiện diện của đĩa lớn nhất không cản trở bất kỳ di chuyển nào của các đĩa h − 1 nhỏ hơn và có thể tạm thời bỏ qua. Bây giờ, vấn đề được thu gọn thành việc di chuyển các đĩa h − 1 từ chốt này sang chốt khác, đầu tiên từ A đến B và sau đó từ B đến C , nhưng có thể sử dụng cùng một phương pháp trong cả hai lần bằng cách đổi tên các chốt. Có thể sử dụng cùng một chiến lược để giảm vấn đề h − 1 thành h − 2, h − 3, v.v. cho đến khi chỉ còn lại một đĩa. Điều này được gọi là đệ quy. Thuật toán này có thể được sơ đồ hóa như sau.

Xác định các đĩa theo thứ tự kích thước tăng dần theo số tự nhiên từ 0 đến nhưng không bao gồm h . Do đó, đĩa 0 là đĩa nhỏ nhất và đĩa h − 1 là đĩa lớn nhất.

Sau đây là quy trình di chuyển một tháp đĩa h từ chốt A sang chốt C , với B là chốt thứ ba còn lại:

Nếu h > 1, thì trước tiên hãy sử dụng quy trình này để di chuyển h − 1 đĩa nhỏ hơn từ chốt A sang chốt B.
Bây giờ đĩa lớn nhất, tức là đĩa h có thể được di chuyển từ chốt A sang chốt C.
Nếu h > 1, thì lại sử dụng quy trình này để di chuyển h − 1 đĩa nhỏ hơn từ chốt B sang chốt C.

Theo quy nạp toán học , có thể dễ dàng chứng minh rằng quy trình trên yêu cầu số lần di chuyển tối thiểu có thể và giải pháp được tạo ra là giải pháp duy nhất có số lần di chuyển tối thiểu này. Sử dụng các mối quan hệ đệ quy , số lần di chuyển chính xác mà giải pháp này yêu cầu có thể được tính bằng: $2^{h}-1$ . Kết quả này thu được bằng cách lưu ý rằng bước 1 và 3 thực hiện $T_{h-1}$ di chuyển, và bước 2 thực hiện một bước di chuyển, đưa ra $T_{h}=2T_{h-1}+1$ .

Giải pháp không đệ quy:

Danh sách các bước di chuyển của một tòa tháp được mang từ một chốt này sang một chốt khác, như được tạo ra bởi thuật toán đệ quy, có nhiều quy luật. Khi đếm các bước di chuyển bắt đầu từ 1, thứ tự của đĩa được di chuyển trong khi di chuyển m là số lần m có thể chia hết cho 2. Do đó, mọi bước di chuyển lẻ đều liên quan đến đĩa nhỏ nhất. Người ta cũng có thể quan sát thấy rằng đĩa nhỏ nhất đi qua các chốt f , t , r , f , t , r , v.v. đối với chiều cao lẻ của tòa tháp và đi qua các chốt f , r , t , f , r , t , v.v. đối với chiều cao chẵn của tòa tháp. Điều này cung cấp thuật toán sau, dễ thực hiện bằng tay hơn so với thuật toán đệ quy.

Trong các động thái xen kẽ:

Di chuyển đĩa nhỏ nhất đến chốt mà nó chưa từng xuất hiện gần đây.
Di chuyển một đĩa khác một cách hợp pháp (chỉ có một khả năng).

Ở lần di chuyển đầu tiên, đĩa nhỏ nhất sẽ được chuyển đến chốt t nếu h lẻ và đến chốt r nếu h chẵn.

Ngoài ra, hãy lưu ý rằng:

Các đĩa có thứ tự chẵn sẽ chuyển động theo cùng hướng như đĩa nhỏ nhất.
Các đĩa có thứ tự chẵn lẻ sẽ di chuyển theo chiều ngược lại.
Nếu h chẵn thì chốt thứ ba còn lại trong các lần di chuyển liên tiếp là t , r , f , t , r , f , v.v.
Nếu h lẻ, chốt thứ ba còn lại trong các lần di chuyển liên tiếp là r , t , f , r , t , f , v.v.

Với kiến thức này, một tập hợp các đĩa ở giữa một giải pháp tối ưu có thể được phục hồi mà không cần thêm thông tin trạng thái nào ngoài vị trí của mỗi đĩa:

Gọi các bước di chuyển được nêu chi tiết ở trên là bước di chuyển "tự nhiên" của đĩa.
Kiểm tra đĩa trên cùng nhỏ nhất không phải là đĩa 0 và lưu ý nước đi (hợp lệ) duy nhất của nó là gì: nếu không có đĩa nào như vậy, thì chúng ta đang ở nước đi đầu tiên hoặc nước đi cuối cùng.
Nếu nước đi đó là nước đi "tự nhiên" của đĩa, thì đĩa chưa được di chuyển kể từ nước đi 0 cuối cùng của đĩa và nước đi đó phải được thực hiện.
Nếu nước đi đó không phải là nước đi "tự nhiên" của đĩa thì hãy di chuyển đĩa 0.

Giải pháp nhị phân

Vị trí đĩa có thể được xác định trực tiếp hơn từ biểu diễn nhị phân (cơ số 2) của số lần di chuyển (trạng thái ban đầu là lần di chuyển số 0, với tất cả các chữ số là 0 và trạng thái cuối cùng là với tất cả các chữ số là 1), bằng cách sử dụng các quy tắc sau:

Mỗi đĩa có một chữ số nhị phân ( bit ).
Bit quan trọng nhất (bên trái) biểu thị đĩa lớn nhất. Giá trị 0 biểu thị đĩa lớn nhất nằm trên chốt ban đầu, trong khi giá trị 1 biểu thị đĩa lớn nhất nằm trên chốt cuối cùng (chốt bên phải nếu số đĩa lẻ và chốt giữa nếu không).
Chuỗi bit được đọc từ trái sang phải và mỗi bit có thể được sử dụng để xác định vị trí của đĩa tương ứng.
Một bit có cùng giá trị với bit trước đó có nghĩa là đĩa tương ứng được xếp chồng lên đĩa trước đó trên cùng một chốt.
(Tức là: chuỗi thẳng 1 hoặc 0 có nghĩa là các đĩa tương ứng đều nằm trên cùng một chốt.)
Một bit có giá trị khác với bit trước đó có nghĩa là đĩa tương ứng ở vị trí bên trái hoặc bên phải của đĩa trước đó. Việc nó ở bên trái hay bên phải được xác định theo quy tắc này:
- Giả sử chốt ban đầu nằm ở bên trái.
- Cũng giả sử "gói"—do đó chốt bên phải được tính là một chốt "bên trái" của chốt bên trái, và ngược lại.
- Giả sử n là số đĩa lớn hơn nằm trên cùng một cọc với đĩa lớn đầu tiên của chúng và cộng thêm 1 nếu đĩa lớn nhất nằm trên cọc bên trái. Nếu n chẵn, đĩa nằm lệch một cọc sang phải, nếu n lẻ, đĩa nằm lệch một cọc sang trái (trong trường hợp số đĩa chẵn và ngược lại).

Ví dụ, trong một Hà Nội có 8 đĩa:

Di chuyển 0 = 00000000.
- Đĩa lớn nhất là 0, do đó nó nằm ở chốt bên trái (ban đầu).
- Tất cả các đĩa khác cũng bằng 0, vì vậy chúng được xếp chồng lên trên. Do đó, tất cả các đĩa đều nằm trên chốt ban đầu.
Di chuyển 2 ⁸ − 1 = 11111111.
- Đĩa lớn nhất là 1, do đó nó nằm ở chốt giữa (cuối cùng).
- Tất cả các đĩa khác cũng là 1, vì vậy chúng được xếp chồng lên trên. Do đó, tất cả các đĩa đều nằm trên chốt cuối cùng và câu đố đã hoàn thành.
Di chuyển 216 ₁₀ = 11011000.
- Đĩa lớn nhất là 1, do đó nó nằm ở chốt giữa (cuối cùng).
- Đĩa thứ hai cũng là 1, do đó nó được xếp chồng lên trên đĩa thứ hai, trên chốt ở giữa.
- Đĩa thứ ba là 0, do đó nó nằm trên một chốt khác. Vì n lẻ ( n = 1), nên nó lệch một chốt về bên trái, tức là nằm trên chốt bên trái.
- Đĩa thứ tư là 1, vì vậy nó nằm trên một chốt khác. Vì n lẻ ( n = 1), nó lệch một chốt sang trái, tức là ở chốt bên phải.
- Đĩa thứ năm cũng là 1, do đó nó được xếp chồng lên trên, ở chốt bên phải.
- Đĩa thứ sáu là 0, do đó nó nằm trên một chốt khác. Vì n chẵn ( n = 2), nên đĩa lệch một chốt sang phải, tức là nằm trên chốt bên trái.
- Đĩa thứ bảy và thứ tám cũng bằng 0, do đó chúng được xếp chồng lên trên, ở chốt bên trái.

Các chốt nguồn và đích cho lần di chuyển thứ m cũng có thể được tìm thấy một cách trang nhã từ biểu diễn nhị phân của m bằng cách sử dụng các phép toán bitwise . Để sử dụng cú pháp của ngôn ngữ lập trình C , di chuyển m là từ chốt này (m & m - 1) % 3sang chốt khác ((m | m - 1) + 1) % 3, trong đó các đĩa bắt đầu ở chốt 0 và kết thúc ở chốt 1 hoặc 2 tùy thuộc vào số lượng đĩa là chẵn hay lẻ. Một công thức khác là từ chốt này (m - (m & -m)) % 3sang chốt khác (m + (m & -m)) % 3.

Hơn nữa, đĩa cần di chuyển được xác định bằng số lần số lần di chuyển ( m ) có thể chia cho 2 (tức là số bit không ở bên phải), đếm lần di chuyển đầu tiên là 1 và xác định các đĩa bằng các số 0, 1, 2, v.v. theo thứ tự kích thước tăng dần. Điều này cho phép triển khai máy tính không đệ quy rất nhanh để tìm vị trí của các đĩa sau m lần di chuyển mà không cần tham chiếu đến bất kỳ lần di chuyển hoặc phân phối đĩa nào trước đó.

Phép toán đếm số lượng số không liên tiếp ở cuối một số nhị phân đưa ra một giải pháp đơn giản cho vấn đề này: các đĩa được đánh số từ số không và khi di chuyển m , số lượng đĩa đếm số không theo sau được di chuyển khoảng cách tối thiểu có thể sang bên phải (quay lại vòng sang bên trái nếu cần).

Giải pháp mã màu xám

Hệ thống số nhị phân của mã Gray cung cấp một cách giải quyết khác cho câu đố. Trong hệ thống Gray, các số được biểu thị bằng tổ hợp nhị phân gồm 0 và 1, nhưng thay vì là hệ thống số vị trí chuẩn , mã Gray hoạt động dựa trên tiền đề rằng mỗi giá trị chỉ khác với giá trị trước đó một bit thay đổi.

Nếu đếm theo mã Gray một bit có kích thước bằng số đĩa trong một Tháp Hà Nội cụ thể, bắt đầu từ số không và đếm lên, thì bit thay đổi sau mỗi lần di chuyển sẽ tương ứng với đĩa cần di chuyển, trong đó bit ít quan trọng nhất là đĩa nhỏ nhất và bit quan trọng nhất là đĩa lớn nhất.

Đếm các bước di chuyển từ 1 và xác định các đĩa bằng các số bắt đầu từ 0 theo thứ tự kích thước tăng dần, thứ tự của đĩa được di chuyển trong lần di chuyển thứ m là số lần m có thể chia hết cho 2.

Kỹ thuật này xác định đĩa nào cần di chuyển, nhưng không xác định được vị trí cần di chuyển. Đối với đĩa nhỏ nhất, luôn có hai khả năng. Đối với các đĩa khác, luôn có một khả năng, ngoại trừ khi tất cả các đĩa đều nằm trên cùng một chốt, nhưng trong trường hợp đó, hoặc là đĩa nhỏ nhất phải di chuyển hoặc mục tiêu đã đạt được. May mắn thay, có một quy tắc chỉ ra vị trí cần di chuyển đĩa nhỏ nhất. Giả sử f là chốt bắt đầu, t là chốt đích và r là chốt thứ ba còn lại. Nếu số đĩa là lẻ, đĩa nhỏ nhất sẽ di chuyển theo các chốt theo thứ tự f → t → r → f → t → r , v.v. Nếu số đĩa là chẵn, điều này phải được đảo ngược: f → r → t → f → r → t , v.v. ^[15]

Vị trí của sự thay đổi bit trong giải pháp mã Gray cho biết kích thước của đĩa được di chuyển ở mỗi bước: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... (chuỗi A001511 trong OEIS ), ^[16] một chuỗi cũng được gọi là hàm thước đo , hoặc nhiều hơn một so với lũy thừa của 2 trong số lần di chuyển. Trong Ngôn ngữ Wolfram , IntegerExponent[Range[2^8 - 1], 2] + 1đưa ra các lần di chuyển cho câu đố 8 đĩa.

Biểu diễn đồ họa

Trò chơi có thể được biểu diễn bằng một đồ thị vô hướng , các nút biểu diễn sự phân phối của các đĩa và các cạnh biểu diễn các nước đi. Đối với một đĩa, đồ thị là một hình tam giác:

Đồ thị của hai đĩa là ba hình tam giác được kết nối để tạo thành các góc của một hình tam giác lớn hơn.

Một chữ cái thứ hai được thêm vào để biểu diễn đĩa lớn hơn. Rõ ràng là ban đầu nó không thể di chuyển được.

Hình tam giác nhỏ trên cùng hiện đại diện cho khả năng di chuyển một lần với hai đĩa:

gọi các chốt là a, b và c
liệt kê các vị trí đĩa từ trái sang phải theo thứ tự kích thước tăng dần

Các cạnh của tam giác ngoài cùng biểu diễn những cách ngắn nhất để di chuyển một tòa tháp từ một chốt này sang một chốt khác. Cạnh ở giữa các cạnh của tam giác lớn nhất biểu diễn một động thái của đĩa lớn nhất. Cạnh ở giữa các cạnh của mỗi tam giác nhỏ hơn tiếp theo biểu diễn một động thái của mỗi đĩa nhỏ hơn tiếp theo. Các cạnh của tam giác nhỏ nhất biểu diễn các động thái của đĩa nhỏ nhất.

Nhìn chung, đối với một câu đố có n đĩa, có 3 ⁿ nút trong đồ thị; mỗi nút có ba cạnh đến các nút khác, ngoại trừ ba nút góc, có hai cạnh: luôn có thể di chuyển đĩa nhỏ nhất đến một trong hai chốt khác và có thể di chuyển một đĩa giữa hai chốt đó ngoại trừ trường hợp tất cả các đĩa được xếp chồng lên nhau trên một chốt. Các nút góc biểu diễn ba trường hợp trong đó tất cả các đĩa được xếp chồng lên nhau trên một chốt. Sơ đồ cho n + 1 đĩa được lấy bằng cách lấy ba bản sao của sơ đồ n đĩa—mỗi bản sao biểu diễn tất cả các trạng thái và di chuyển của các đĩa nhỏ hơn cho một vị trí cụ thể của đĩa lớn nhất mới—và nối chúng ở các góc bằng ba cạnh mới, biểu diễn ba cơ hội duy nhất để di chuyển đĩa lớn nhất. Do đó, hình kết quả có 3 ^{n + 1} nút và vẫn còn ba góc chỉ có hai cạnh.

Biểu đồ trò chơi ở cấp độ 7 cho thấy mối liên quan đến tam giác Sierpiński

Khi thêm nhiều đĩa hơn, biểu đồ biểu diễn của trò chơi sẽ giống như một hình fractal , tam giác Sierpiński . Rõ ràng là phần lớn các vị trí trong câu đố sẽ không bao giờ đạt được khi sử dụng giải pháp ngắn nhất có thể; thực tế, nếu các linh mục trong truyền thuyết sử dụng giải pháp dài nhất có thể (mà không quay lại bất kỳ vị trí nào), họ sẽ mất 3 ⁶⁴ − 1 lần di chuyển, hoặc hơn 10 ²³ năm.

Con đường dài nhất không lặp lại cho ba đĩa có thể được hình dung bằng cách xóa các cạnh không sử dụng:

Ngẫu nhiên, đường đi dài nhất không lặp lại này có thể đạt được bằng cách cấm mọi di chuyển từ a đến c .

Chu trình Hamilton cho ba đĩa là:

Biểu đồ cho thấy rõ ràng rằng:

Trong mọi cách phân phối đĩa tùy ý, chỉ có duy nhất một cách ngắn nhất để di chuyển tất cả các đĩa vào một trong ba chốt.
Giữa mỗi cặp phân phối đĩa tùy ý có một hoặc hai đường dẫn ngắn nhất khác nhau.
Từ mỗi phân phối đĩa tùy ý, có một hoặc hai đường đi không tự cắt dài nhất khác nhau để di chuyển tất cả các đĩa đến một trong ba chốt.
Giữa mỗi cặp phân phối đĩa tùy ý có một hoặc hai đường đi không tự cắt dài nhất khác nhau.
Giả sử N _h là số đường đi không tự cắt để di chuyển một tháp gồm h đĩa từ chốt này sang chốt khác. Khi đó:
- N1 ₌ 2
- N _h +1 = ( N _h ) ² + ( N _h ) ³

Điều này cho N _h là 2, 12, 1872, 6563711232, ... (chuỗi A125295 trong OEIS )

Biến thể

Tuyến tính Hà Nội

Nếu tất cả các lần di chuyển phải diễn ra giữa các chốt liền kề (tức là các chốt A, B, C đã cho, người ta không thể di chuyển trực tiếp giữa các chốt A và C), thì việc di chuyển một chồng n đĩa từ chốt A đến chốt C mất 3 ⁿ − 1 lần di chuyển. Giải pháp sử dụng tất cả 3 ⁿ vị trí hợp lệ, luôn thực hiện lần di chuyển duy nhất không hoàn tác lần di chuyển trước đó. Vị trí có tất cả các đĩa tại chốt B đạt được ở giữa chừng, tức là sau (3 ⁿ − 1) / 2 lần di chuyển. ^[17]^[18]

Chu kỳ Hà Nội

Trong Cyclic Hanoi, chúng ta được cung cấp ba chốt (A, B, C), được sắp xếp thành một vòng tròn với hướng theo chiều kim đồng hồ và ngược chiều kim đồng hồ được xác định lần lượt là A – B – C – A và A – C – B – A. Hướng chuyển động của đĩa phải theo chiều kim đồng hồ. ^[19] Chỉ cần biểu diễn trình tự các đĩa cần di chuyển là đủ. Có thể tìm ra lời giải bằng cách sử dụng hai thủ tục đệ quy lẫn nhau:

Để di chuyển n đĩa ngược chiều kim đồng hồ đến chốt mục tiêu lân cận:

di chuyển n − 1 đĩa ngược chiều kim đồng hồ đến chốt mục tiêu
di chuyển đĩa # n một bước theo chiều kim đồng hồ
di chuyển n − 1 đĩa theo chiều kim đồng hồ đến chốt bắt đầu
di chuyển đĩa # n một bước theo chiều kim đồng hồ
di chuyển n − 1 đĩa ngược chiều kim đồng hồ đến chốt mục tiêu

Để di chuyển n đĩa theo chiều kim đồng hồ đến chốt mục tiêu lân cận:

di chuyển n − 1 đĩa ngược chiều kim đồng hồ đến một chốt dự phòng
di chuyển đĩa # n một bước theo chiều kim đồng hồ
di chuyển n − 1 đĩa ngược chiều kim đồng hồ đến chốt mục tiêu

Giả sử C(n) và A(n) biểu diễn chuyển động của n đĩa theo chiều kim đồng hồ và ngược chiều kim đồng hồ, khi đó ta có thể viết cả hai công thức:

	C(n) = A(n−1) n A(n−1)	Và	A(n) = A(n−1) n C(n−1) n A(n−1).

Vì vậy	C(1) = 1	Và	A(1) = 1 1,
	C(2) = 1 1 2 1 1	Và	A(2) = 1 1 2 1 2 1 1.

Giải pháp cho Cyclic Hanoi có một số đặc điểm thú vị:

Các mẫu di chuyển khi chuyển một tháp đĩa từ chốt này sang chốt khác là đối xứng với các điểm trung tâm.
Đĩa nhỏ nhất là đĩa đầu tiên và cuối cùng di chuyển.
Các nhóm di chuyển đĩa nhỏ nhất xen kẽ với các di chuyển đơn lẻ của các đĩa khác.
Số lượng đĩa di chuyển được chỉ định bởi C(n) và A(n) là tối thiểu.

Với bốn chốt và hơn thế nữa

Mặc dù phiên bản ba chốt có một giải pháp đệ quy đơn giản đã được biết đến từ lâu, giải pháp tối ưu cho bài toán Tháp Hà Nội với bốn chốt (gọi là câu đố Reve) vẫn chưa được xác minh cho đến năm 2014, bởi Bousch. ^[20]

Tuy nhiên, trong trường hợp có bốn chốt hoặc nhiều hơn, thuật toán Frame–Stewart đã được biết đến mà không có bằng chứng về tính tối ưu kể từ năm 1941. ^[21]

Để có được phép suy luận chính thức về số lượng chính xác các bước di chuyển tối thiểu cần thiết để giải quyết vấn đề bằng cách áp dụng thuật toán Frame–Stewart (và các phương pháp tương đương khác), hãy xem bài báo sau. ^[22]

Đối với các biến thể khác của bài toán Tháp Hà Nội bốn chân, hãy xem bài báo khảo sát của Paul Stockmeyer. ^[23]

Các cấu hình trò chơi được gọi là Towers of Bucharest và Towers of Klagenfurt tạo ra mã Gray tam phân và ngũ phân . ^[24]

Thuật toán Frame–Stewart

Thuật toán Frame–Stewart được mô tả dưới đây:

Cho phép $N$ là số đĩa.
Cho phép $r$ là số chốt.
Định nghĩa $T(n,r)$ là số lần di chuyển tối thiểu cần thiết để chuyển n đĩa bằng r chốt.

Thuật toán có thể được mô tả theo cách đệ quy:

Đối với một số $tôi$ , $1\leq k<n$ , chuyển phần trên cùng $tôi$ đĩa đến một chốt duy nhất khác với chốt bắt đầu hoặc chốt đích, lấy $T(k,r)$ di chuyển.
Không làm xáo trộn chốt hiện đang chứa đỉnh $tôi$ đĩa, chuyển phần còn lại $n-k$ đĩa đến chốt đích, chỉ sử dụng phần còn lại $r-1$ chốt, lấy $T(n-k,r-1)$ di chuyển.
Cuối cùng, chuyển phần trên cùng $tôi$ đĩa đến chốt đích, lấy $T(k,r)$ di chuyển.

Toàn bộ quá trình diễn ra $2T(k,r)+T(n-k,r-1)$ di chuyển. Do đó, số lượng $tôi$ nên được chọn mà số lượng này là tối thiểu. Trong trường hợp 4 chốt, tối ưu $tôi$ bằng nhau $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ , Ở đâu $\left\lfloor \cdot \right\rceil$ là hàm số nguyên gần nhất . ^[25] Ví dụ, trong khóa học CIS 194 của UPenn về Haskell, trang bài tập đầu tiên ^[26] liệt kê giải pháp tối ưu cho trường hợp 15 đĩa và 4 chốt là 129 bước, thu được cho giá trị k ở trên .

Thuật toán này được cho là tối ưu cho bất kỳ số lượng chốt nào; số lần di chuyển của nó là 2 ^{Θ ( n ^{1/( r −2)} )} (với r cố định ).

Đường đi ngắn nhất chung và số 466/885

Một khái quát thú vị về mục tiêu ban đầu của câu đố là bắt đầu từ một cấu hình đĩa nhất định, trong đó tất cả các đĩa không nhất thiết phải nằm trên cùng một chốt và đến đích trong một số lần di chuyển tối thiểu ở một cấu hình nhất định khác. Nhìn chung, có thể khá khó để tính toán một chuỗi di chuyển ngắn nhất để giải quyết vấn đề này. Một giải pháp đã được đề xuất bởi Andreas Hinz và dựa trên quan sát rằng trong một chuỗi di chuyển ngắn nhất, đĩa lớn nhất cần di chuyển (rõ ràng là người ta có thể bỏ qua tất cả các đĩa lớn nhất sẽ chiếm cùng một chốt trong cả cấu hình ban đầu và cuối cùng) sẽ di chuyển chính xác một lần hoặc chính xác hai lần.

Toán học liên quan đến vấn đề tổng quát này trở nên thú vị hơn nữa khi người ta xem xét số lượng trung bình các bước di chuyển trong một chuỗi di chuyển ngắn nhất giữa hai cấu hình đĩa ban đầu và cuối cùng được chọn ngẫu nhiên. Hinz và Chan Tat-Hung đã độc lập khám phá ra ^[27]^[28] (xem thêm ^[29]^{: Chương 1, trang 14} ) rằng số lượng trung bình các bước di chuyển trong Tháp n đĩa được đưa ra bởi công thức chính xác sau:

{\frac {466}{885}}\cdot 2^{n}-{\frac {1}{3}}-{\frac {3}{5}}\cdot \left({\frac {1}{3}}\right)^{n}+\left({\frac {12}{59}}+{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5+{\sqrt {17}}}{18}}\right)^{n}+\left({\frac {12}{59}}-{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5-{\sqrt {17}}}{18}}\right)^{n}.

Với n đủ lớn , chỉ có số hạng thứ nhất và thứ hai không hội tụ về 0, do đó ta có biểu thức tiệm cận : $466/885\cdot 2^{n}-1/3+o(1)$ , BẰNG $n\to \infty$ . Do đó, theo trực giác, chúng ta có thể diễn giải phân số của $466/885\approx 52.6\%$ như thể hiện tỷ lệ lao động mà người ta phải thực hiện khi đi từ một cấu hình được chọn ngẫu nhiên sang một cấu hình được chọn ngẫu nhiên khác, so với độ khó khi phải vượt qua con đường "khó khăn nhất" về độ dài $2^{n}-1$ bao gồm việc di chuyển tất cả các đĩa từ chốt này sang chốt khác. Một lời giải thích thay thế cho sự xuất hiện của hằng số 466/885, cũng như một thuật toán mới và được cải tiến một chút để tính toán đường đi ngắn nhất, đã được đưa ra bởi Romik. ^[30]

Hà Nội từ tính

[ biên tập ]

Trong Tháp từ Hà Nội, mỗi đĩa có hai mặt riêng biệt là Bắc và Nam (thường có màu "đỏ" và "xanh"). Các đĩa không được đặt cùng cực với nhau—nam châm trong mỗi đĩa ngăn chặn việc di chuyển bất hợp pháp này. Ngoài ra, mỗi đĩa phải được lật khi di chuyển.

Tháp đôi Hà Nội

[ biên tập ]

Biến thể của câu đố Tháp Hà Nội nổi tiếng này được đưa ra cho học sinh lớp 3–6 tại 2ème Championnat de France des Jeux Mathématiques et Logiques được tổ chức vào tháng 7 năm 1988. ^[31]

Cấu hình ban đầu của Tháp đôi Hà Nội (n=4)

Các quy tắc của câu đố về cơ bản là giống nhau: các đĩa được chuyển giữa các chốt từng cái một. Không bao giờ được đặt một đĩa lớn hơn lên trên một đĩa nhỏ hơn. Sự khác biệt là bây giờ đối với mọi kích thước đều có hai đĩa: một đĩa đen và một đĩa trắng. Ngoài ra, bây giờ có hai tháp đĩa có màu xen kẽ. Mục tiêu của câu đố là làm cho các tháp đơn sắc (cùng màu). Các đĩa lớn nhất ở dưới cùng của các tháp được cho là hoán đổi vị trí.

Cấu hình cuối cùng của Tháp đôi Hà Nội (n=4)

Tháp Hanoy

Một biến thể của câu đố đã được chuyển thể thành trò chơi bài đơn với chín lá bài dưới tên gọi Tower of Hanoy . ^[32]^[33] Người ta không biết liệu cách viết thay đổi của tên gốc là cố ý hay vô tình.

Các ứng dụng

Tháp Hà Nội thường được sử dụng trong nghiên cứu tâm lý về giải quyết vấn đề . Ngoài ra còn có một biến thể của nhiệm vụ này được gọi là Tháp London để chẩn đoán và điều trị rối loạn chức năng điều hành bằng phương pháp thần kinh học . ^[36]

Zhang và Norman ^[37] đã sử dụng một số biểu diễn đẳng cấu (tương đương) của trò chơi để nghiên cứu tác động của hiệu ứng biểu diễn trong thiết kế nhiệm vụ. Họ đã chứng minh tác động đến hiệu suất của người dùng bằng cách thay đổi cách biểu diễn các quy tắc của trò chơi, sử dụng các biến thể trong thiết kế vật lý của các thành phần trò chơi. Kiến thức này đã tác động đến sự phát triển của khuôn khổ TURF ^[38] để biểu diễn tương tác giữa con người và máy tính .

Tháp Hà Nội cũng được sử dụng như một chương trình luân phiên sao lưu khi thực hiện sao lưu dữ liệu máy tính khi có nhiều băng/phương tiện liên quan.

Hình ảnh địa hình AFM 3D của tấm nano palladium nhiều lớp trên tấm bán dẫn silicon, có cấu trúc giống Tháp Hà Nội.

Như đã đề cập ở trên, Tháp Hà Nội được ưa chuộng vì có thể dạy các thuật toán đệ quy cho sinh viên mới bắt đầu học lập trình. Một phiên bản hình ảnh của câu đố này được lập trình trong trình soạn thảo emacs , truy cập bằng cách nhập Mx hanoi. Ngoài ra còn có một thuật toán mẫu được viết bằng Prolog . ^{[ cần trích dẫn ]}

Tháp Hà Nội cũng được các nhà tâm lý học thần kinh sử dụng như một bài kiểm tra để đánh giá các khiếm khuyết ở thùy trán . ^[39]

Năm 2010, các nhà nghiên cứu đã công bố kết quả của một thí nghiệm cho thấy loài kiến Linepithema humile có thể giải thành công phiên bản 3 đĩa của bài toán Tháp Hà Nội thông qua động lực học phi tuyến tính và tín hiệu pheromone. ^[40]

Năm 2014, các nhà khoa học đã tổng hợp các tấm nano palladium nhiều lớp có cấu trúc giống như Tháp Hà Nội.

Nền Văn Hóa phổ biến

Trong truyện khoa học viễn tưởng "Now Inhale", của Eric Frank Russell , một con người bị giam giữ trên một hành tinh nơi có phong tục địa phương là bắt tù nhân chơi một trò chơi cho đến khi thắng hoặc thua trước khi bị hành quyết. Nhân vật chính biết rằng một con tàu cứu hộ có thể mất một năm hoặc hơn để đến nơi, vì vậy anh ta chọn chơi Towers of Hanoi với 64 đĩa. Câu chuyện này ám chỉ đến truyền thuyết về các nhà sư Phật giáo chơi trò chơi cho đến tận thế. ^[41]^[42]^[43]

Trong câu chuyện The Celestial Toymaker của Doctor Who năm 1966 , nhân vật phản diện cùng tên buộc Doctor phải chơi một trò chơi Tower of Hanoi gồm mười quân cờ, 1.023 nước đi có tên là The Trilogic Game với các quân cờ tạo thành hình kim tự tháp khi xếp chồng lên nhau. ^[42]^[44]

Năm 2007, khái niệm về bài toán Towers Of Hanoi đã được sử dụng trong Giáo sư Layton và Hộp Diabolical trong các câu đố 6, 83 và 84, nhưng các đĩa đã được thay đổi thành bánh kếp. Câu đố dựa trên một tình huống khó xử khi đầu bếp của một nhà hàng phải di chuyển một đống bánh kếp từ đĩa này sang đĩa khác với các nguyên tắc cơ bản của câu đố gốc (tức là ba đĩa mà bánh kếp có thể được di chuyển vào, không thể đặt một chiếc bánh kếp lớn hơn vào một chiếc bánh kếp nhỏ hơn, v.v.)

Trong bộ phim Rise of the Planet of the Apes năm 2011 , câu đố này, được gọi trong phim là "Lucas Tower", được sử dụng như một bài kiểm tra để nghiên cứu trí thông minh của loài vượn . ^[42]

Câu đố thường xuất hiện trong các trò chơi phiêu lưu và giải đố . Vì dễ thực hiện và dễ nhận biết nên nó rất phù hợp để sử dụng làm câu đố trong trò chơi đồ họa lớn hơn (ví dụ: Star Wars: Knights of the Old Republic và Mass Effect ). ^[45] Một số cách thực hiện sử dụng đĩa thẳng, nhưng một số khác ngụy trang câu đố ở một dạng khác. Có một phiên bản arcade của Sega . ^[46]

Phiên bản 15 đĩa của câu đố xuất hiện trong trò chơi Sunless Sea như một ổ khóa cho một ngôi mộ. Người chơi có tùy chọn nhấp qua từng bước di chuyển của câu đố để giải quyết nó, nhưng trò chơi lưu ý rằng sẽ mất 32.767 bước để hoàn thành. Nếu một người chơi đặc biệt tận tâm nhấp qua đến cuối câu đố, thì sẽ tiết lộ rằng việc hoàn thành câu đố không mở khóa được cánh cửa.

Lần đầu tiên nó được sử dụng như một thử thách trong Survivor Thailand vào năm 2002 nhưng thay vì những chiếc nhẫn, các mảnh ghép được làm giống như một ngôi đền. Sook Jai đã đưa ra thử thách để loại bỏ Jed mặc dù Shii-Ann biết rõ cách hoàn thành câu đố. Bài toán này được đưa vào như một phần của thử thách phần thưởng trong một tập phim năm 2011 của phiên bản Mỹ của loạt phim truyền hình Survivor . Cả hai người chơi ( Ozzy Lusth và Benjamin "Coach" Wade ) đều vật lộn để hiểu cách giải câu đố và được các thành viên trong bộ lạc của họ hỗ trợ.

Trong Genshin Impact , câu đố này được thể hiện trong nhiệm vụ tụ tập của Faruzan, "Cơ chế học sớm", nơi cô ấy đề cập đến việc coi nó như một cơ chế và sử dụng nó để tạo ra một nguyên mẫu đồ chơi cho trẻ em. Cô ấy gọi nó là chồng tháp .

------------------------------

Liên quan:

https://doccophai.blogspot.com/tartaria-bi-mat-kabbalah-do-thai-thienduong

https://doccophai.blogspot.com/ma-tran-sinh-vat-ien-so-phan-nhan-loai