หอคอยฮานอย

ปริศนาหอคอยฮานอย: ย้ายจานทั้งตั้งจากหลัก A ไปยังหลักอื่นตามกติกา แก้เองหรือดูเฉลยอัตโนมัติและลำดับการย้ายได้ เช่น ใช้ในบทเรียนเรื่องการเรียกซ้ำ (recursion)

วิธีใช้

1. เลือก "จำนวนจาน" ตั้งแต่ 3 ถึง 10
2. ลากจานบนสุดไปยังหลักอื่น หรือแตะหลักเพื่อหยิบจานบนสุดแล้วแตะอีกหลักเพื่อวาง ใช้ปุ่ม 1, 2 และ 3 ก็ได้
3. กด "เลิกทำ" เพื่อย้อนการย้าย หรือ "เริ่มใหม่" เพื่อเริ่มต้นใหม่
4. หากติด ให้กด "แสดงเฉลย" เพื่อดูเฉลยจากตำแหน่งปัจจุบัน ปรับ "ความเร็ว" ได้ หรือกด "หยุดชั่วคราว" แล้วใช้ "ทีละขั้น"

หลักการทำงาน

• กติกา: ย้ายจานทีละหนึ่งใบ ย้ายได้เฉพาะจานบนสุดของหลัก และห้ามวางจานใหญ่บนจานเล็ก
• จำนวนครั้งน้อยที่สุดคือ 2ⁿ − 1 สำหรับจาน n ใบ การย้ายจาน n ใบทำได้โดยย้ายจาน n − 1 ใบไปพักไว้ ย้ายจานใบใหญ่ที่สุดหนึ่งครั้ง แล้วย้ายจาน n − 1 ใบกลับมาวางด้านบน
• สถิติดีที่สุดของแต่ละจำนวนจานบันทึกไว้ในเบราว์เซอร์นี้ เกมที่ใช้เฉลยอัตโนมัติจะไม่ถูกบันทึก

คำถามที่พบบ่อย

หอคอยฮานอยต้องย้ายน้อยที่สุดกี่ครั้ง

สำหรับจาน n ใบคือ 2ⁿ − 1: 3 ใบใช้ 7 ครั้ง 4 ใบใช้ 15 ครั้ง 5 ใบใช้ 31 ครั้ง และ 10 ใบใช้ 1,023 ครั้ง

มีวิธีง่าย ๆ ในการแก้หอคอยฮานอยไหม

ในการย้ายครั้งที่เป็นเลขคี่ ให้ย้ายจานเล็กที่สุดไปหลักถัดไปหนึ่งหลักในทิศทางเดิมเสมอ ในการย้ายครั้งที่เป็นเลขคู่ ให้ย้ายแบบเดียวที่ถูกกติกาโดยไม่ใช้จานเล็กที่สุด

ทำไมหอคอยฮานอยถูกใช้สอนเรื่องการเรียกซ้ำ

คำตอบสำหรับจาน n ใบประกอบด้วยคำตอบของจาน n − 1 ใบสองครั้ง บวกการย้ายจานใบใหญ่ที่สุดหนึ่งครั้ง ดังนั้น T(n) = 2·T(n − 1) + 1

ดูการย้ายทั้งหมดพร้อมกันได้ไหม

เปิด "ลำดับการย้ายของเฉลย" เพื่อดูการย้ายทุกครั้งในรูปแบบ "จาน 1: A → C"