Tháp Hà Nội miễn phí | Trò đố ba cọc

Cách nó hoạt động

Mở trang này. Bốn đĩa đã xếp sẵn trên cọc xuất phát. Tối thiểu là mười lăm nước.
Kéo đĩa trên cùng sang cọc khác, hoặc bấm một cọc rồi bấm cọc bạn muốn. Đặt đĩa lớn lên đĩa nhỏ sẽ bị từ chối.
Bấm Giải để xem một lời giải ngắn nhất, hoặc đi từng Bước. Sau đó lưu PNG.

Một đĩa, và không bao giờ đĩa lớn trên đĩa nhỏ

Một nước đi lấy đĩa trên cùng của một cọc và đặt nó lên cọc khác, hoặc lên một cọc trống. Chỉ có một kiểu nước đi như vậy. Đĩa bạn đặt phải nhỏ hơn đĩa nằm dưới nó. Với các luật đó, đĩa trên mỗi cọc luôn được xếp theo thứ tự, đĩa lớn nhất ở dưới cùng.

2ⁿ − 1 nước, không ít hơn

Để chuyển n đĩa, trước hết bạn dời n − 1 đĩa nằm trên đĩa lớn nhất sang chỗ khác, chuyển đĩa lớn nhất một lần, rồi chuyển n − 1 đĩa lên trên nó. Nếu n − 1 đĩa cần T nước thì n đĩa cần 2T + 1. Kết quả là 2ⁿ − 1: 1, 3, 7, 15, 31. Tám đĩa, tháp cao nhất ở đây, cần 255 nước.

Cùng câu đố, bớt một đĩa

Chuyển n − 1 đĩa trên cùng sang cọc trung gian. Chuyển đĩa lớn nhất sang đích. Chuyển n − 1 đĩa từ cọc trung gian sang đích. Mỗi việc nhỏ hơn đó lại là cùng một câu đố. Bước và Giải phát lại một đường đi ngắn nhất. Từ một tháp hoàn chỉnh, đó chính là phép đệ quy này. Từ một bàn đã xáo trộn, đó vẫn là một đường đi ngắn nhất, tìm được bằng cách duyệt các thế hợp lệ.