Tháp Hà Nội

Cách chơi Tháp Hà Nội

1. Chọn số đĩa (từ 3 đến 8). Tất cả bắt đầu xếp chồng ở cọc 1, đĩa lớn nhất ở dưới và đĩa nhỏ nhất ở trên.
2. Chạm vào một cọc để chọn đĩa trên cùng rồi chạm vào cọc bạn muốn chuyển đến. Bạn cũng có thể kéo đĩa sang cọc khác.
3. Mỗi lần chỉ chuyển một đĩa và không bao giờ đặt đĩa lên một đĩa nhỏ hơn nó.
4. Bạn thắng khi cả tháp nằm ở một cọc khác. Bộ đếm cho biết số bước của bạn và mức tối thiểu có thể; nếu bí, nút Giải sẽ chạy lời giải ngắn nhất.

Một trò chơi kinh điển về logic và đệ quy

Tháp Hà Nội là một câu đố toán học do nhà toán học người Pháp Édouard Lucas đặt ra năm 1883. Với n đĩa, số bước tối thiểu là 2 mũ n trừ 1: 7 với ba đĩa, 15 với bốn, 31 với năm và 255 với tám. Mỗi đĩa thêm vào làm công việc gấp đôi rồi cộng thêm một.

Có một cách giải có hệ thống. Để chuyển tháp n đĩa, trước hết chuyển n−1 đĩa trên cùng sang cọc còn lại, sau đó đưa đĩa lớn nhất đến đích và cuối cùng chuyển n−1 đĩa lên trên nó. Đây là ví dụ điển hình của đệ quy. Một quy tắc thực hành khác: đĩa nhỏ nhất di chuyển ở mọi nước đi lẻ, luôn theo cùng một chiều (với số đĩa lẻ đi từ cọc 1 đến 3, từ 3 đến 2 và từ 2 về 1; với số đĩa chẵn, từ 1 đến 2, từ 2 đến 3 và từ 3 về 1); ở các nước đi chẵn chỉ có một nước đi hợp lệ giữa hai cọc còn lại.

Truyền thuyết kể rằng các nhà sư chuyển một tháp 64 đĩa vàng; cần hơn 18 tỷ tỷ bước, tức hàng trăm tỷ năm nếu mỗi giây một bước. Mọi thứ chơi trong trình duyệt: không gửi gì đến máy chủ và chỉ kết quả tốt nhất của bạn được lưu trên thiết bị.

Lưu ý

• Kỷ lục (ít bước nhất) được lưu theo số đĩa, chỉ trong trình duyệt này: nếu bạn xóa dữ liệu trang web, nó sẽ mất.
• Nếu dùng Giải, ván đó không được tính vào kỷ lục. Nút này tính lời giải tốt nhất từ vị trí hiện tại của bạn, không phải từ đầu.
• Với 8 đĩa cần tối thiểu 255 bước; lời giải tự động chạy với nhịp độ khá nhanh và bạn có thể dừng bất cứ lúc nào.

Câu hỏi thường gặp