ปริศนาของหอคอยแห่งฮานอย (Tower of Hanoi)

ความเป็นมา (History)

ปริศนานี้คิดค้นขึ้นโดย นักคณิตศาสตร์ชาวฝรั่งเศส ชื่อ เอดูอาร์ด ลูคาส (Edouard Lucas) ในปี ค.ศ. 1883 มีตำนานเล่าขานเกี่ยวกับโบสถ์ ในอินเดีย ซึ่งมีห้องที่ภายใน มีเสา 3 หลัก และ จานทองอยู่ 64 ใบ คล้องอยู่กับเสา โดยที่พราหมณ์ในโบสถ์นั้นจะทำการเคลื่อนย้ายจานทองตามคำสั่งที่ระบุไว้ในคำพยากรณ์ โดยการเคลื่อนย้ายนั้นจะต้องเป็นไปตามเงื่อนไข คำพยากรณ์ในตำนานได้ทำนายไว้ว่า เมื่อปัญหาถูกแก้ วาระสุดท้ายของโลกจะมาถึง ดังนั้นปัญหานี้จึงมีอีกชื่อหนึ่งว่า ปัญหา "Tower of Brahma" (หอแห่งพรหม) ไม่มีข้อมูลเด่นชัดว่า ลูคาสนั้นเป็นผู้แต่งตำนานนี้ขึ้น หรือ ว่าได้รับแรงบันดาลใจจากตำนานนี้
หากตำนานนี้เป็นจริง และ พราหมณ์สามารถย้ายจานด้วยความเร็ว 1 ใบต่อวินาทีและใช้จำนวนครั้งการย้ายที่น้อยที่สุด เวลาทั้งหมดที่ใช้ในการแก้ปัญหานี้คือ 2⁶⁴ − 1 วินาที หรือ ประมาณ 585 พันล้านปี (ไม่เชื่อ ? หรือเหลือเฃื่อ!!! ก็ให้ลองพับกระดาษ A4 ให้ได้ 64 ครั้ง แล้ววัดความสูงดูนะครับ ถ้าวัดได้จะพบว่ามีความสูงมากกว่าระยะทางจากดวงอาทิตย์ถึงดาวพลูโตซะอีก ก็แค่ 1,844 พันล้านกิโลเมตรเท่านั้นเอง!!! ยิ่งไม่น่าเชื่อเข้าไปอีก แต่เป็นเรื่องจริงนะครับ)

นอกเหนือจากตำนานข้างต้นแล้ว ยังมีตำนานดัดแปลงอื่นๆอีก เช่นในบางเรื่องเล่าเป็นเรื่องของวัดกับพระ โดยที่วัดนั้นอยู่ในประเทศอื่น เช่นที่เมืองฮานอย ในประเทศเวียดนาม ในบางเรื่องก็มีการเสริมเรื่องเล่าว่า หอคอยนั้นถูกสร้างขึ้นมาพร้อมการกำเนิดของโลก หรือมีเงื่อนไขว่าพราหมณ์หรือพระ จะเคลื่อนย้ายจานได้เพียงวันละ 1 ใบ

หอคอยแห่งฮานอย (Tower of Hanoi) ถูกดัดแปลงมาเป็นเกมคณิตศาสตร์ที่ ประกอบด้วยหมุด 3 แท่ง (A, B, C) และ จานกลมแบนขนาดต่างๆ ซึ่งมีรูตรงกลางสำหรับให้หมุดลอด เกมเริ่มจากจานทั้งหมดวางอยู่ที่หมุดเดียวกัน (A) โดยเรียงตามขนาดจากใหญ่ที่สุดอยู่ทางด้านล่าง จนถึงจานขนาดเล็กที่สุดอยู่ด้านบนสุด เป็นลักษณะกรวยคว่ำตามรูป

ปัญหา (Problem)
เป้าหมายของเกมคือ พยายามย้ายกองจานทั้งหมดจากหมุด A ไปไว้ที่หมุด C โดยการเคลื่อนย้ายจานจะต้องเป็นไปตามกฎดังนี้คือ

1. สามารถย้ายจานได้เพียงครั้งละ 1 ใบ
2. ไม่สามารถวางจาน ไว้บนจานที่มีขนาดเล็กกว่าได้

วิธีการแก้ปัญหา (Solution)

ให้เริ่มจากการใช้จานเพียง 1 ใบ ซึ่งสามารถเคลื่อนย้ายได้ในครั้งเดียว (ลองทำดู)

1. ย้าย จาน #1 ไปหมุด C

เพิ่มจานเป็น 2 ใบ ใช้เวลา 3 ครั้ง (ยังทำได้อยู่..)

1. ย้าย จาน #1 ไปหมุด B
2. ย้าย จาน #2 ไปหมุด C
3. ย้าย จาน #1 จาก B ไป C ไปไว้บนจาน #2

เพิ่มจานเป็น 3 ใบ ใช้เวลา 7 ครั้ง (เริ่มยากแล้ว!!)

1. ย้าย จาน #1 ไปหมุด C
2. ย้าย จาน #2 ไปหมุด B
3. ย้าย จาน #1 จาก C ไป B ไปไว้บนจาน #2
4. ตอนนี้ เรามีจาน 2 ใบ วางตามลำดับถูกต้องที่หมุด B และ หมุด C ไม่มีจาน ให้ย้ายจาน #3 จาก A ไปไว้ที่ C ตอนนี้หมุด A จะว่าง
5. ย้ายจาน #1 ไปหมุด A
6. ย้ายจาน#2 ไปไว้บนจาน #3
7. ย้ายจาน #1 ไปไว้บนจาน #2

เพิ่มจานเป็น 4 ใบ ใช้เวลา 15 ครั้ง (มั่วแล้ว เลิกดีกว่า!!)

เกมส่วนใหญ่จะมีจาน 3 - 8 ใบ ซึ่งค่อนข้างยากสำหรับผู้เริ่มเล่น แต่สามารถแก้ได้ด้วยอัลกอริทึมที่ไม่ซับซ้อน ดังนี้

อัลกอริทึมเวียนเกิด (Recursive Algorithm)

1. ตั้งชื่อหมุดทั้งสาม A,B,C
2. สมมุติมีจานทั้งหมด n ใบ
3. ติดเบอร์ให้กับจานจากเล็กที่สุด 1 ไปจนถึงใหญ่ที่สุด n
4. ต้องการย้ายจานทั้งหมด n ใบ จากหมุด A ไปยังหมุด C
5. ต้องย้ายจานด้านบนจำนวน n-1 ใบจาก A ไปไว้ที่ B ก่อน จะทำให้เหลือจาน #n (หมายเลข n ใบใหญ่ที่สุด) เพียงใบเดียวที่หมุด A
6. ย้ายจาน #n จาก A ไปไว้ที่ C
7. ย้ายจานที่เหลือ n-1 ใบจาก B ไปที่ C ซึ่งจานทั้งหมดจะอยู่บนจาน #n

วิธีการในข้อ 7 ก็คือการทำซ้ำข้อ 4 ถึง 6 นั่นเอง (แต่จะมีการสลับหมุดกันไปมา) โดยที่ในการทำซ้ำแต่ละครั้ง จำนวนจานจะลดลงไป 1 ใบ เมื่อเหลือจานเพียงใบเดียว เราก็สามารถย้ายจานได้ทันที อัลกอริทึมแบบนี้เราเรียกว่าอัลกอริทึมเวียนเกิด (recursive algorithm) ในการแก้ปัญหานี้ จะเห็นได้ว่าจากจาน n ใบ จะเหลือปัญหาการย้ายจานจำนวน n-1 ใบ ซึ่งใช้อัลกอริทึมเดียวกันในการแก้ปัญหา และจะลดเหลือปัญหา n-2 ใบ ในการทำซ้ำครั้งต่อไป จนเหลือเพียงการย้ายจานเพียง 1 ใบ

ในความเป็นจริงแล้ว เราไม่สามารถยกจาน n-1 ใบได้ เราต้องยกจานใบแรกด้านบนก่อนเสมอ ปัญหาคือจานใบแรกด้านบนควรจะนำไปวางไว้ที่ไหนก่อน ระหว่าง B กับ C

วิธีการที่คิดมาแล้วและทำได้ทันทีเพื่อหาว่าควรย้ายจานใบแรกจาก A ไปไว้ที่ไหนคือ ถ้ามีจำนวนจานเป็นเลขคู่ จานใบแรกจะย้ายใบที่ B ก่อน (ไปทางด้าขวา) ถ้าเป็นเลขคี่ก็วางจานใบแรกไว้บน C ก่อน (ไปทางด้านซ้าย) หลังจากนั้นก็ใช้อัลกอริทึมเวียนเกิดทำการสลับจานที่เหลือ

ปัญหาหอคอยแห่งฮานอยนี้ เป็นปัญหาที่นิยมใช้ในการสอนการเขียนโปรแกรมเบื้องต้น ใช้เป็นตัวอย่างสำหรับการเขียนโปรแกรมอัลกอริทึมเวียนเกิด นอกจากนั้นแล้วยังใช้เป็นตัวอย่างของอัลกอริทึมที่ใช้เวลาทำงานเป็นแบบเลขยกกำลัง (exponential time) ซึ่งถ้ามีจานจำนวนมากๆ การแก้ปัญหานี้จะต้องใช้เวลามหาศาล (ตามความเป็นมาข้างต้น) ถึงแม้ว่าจะใช้คอมพิวเตอร์ที่เร็วที่สุดในโลกในการแก้ปัญหา ก็ไม่มีวิธีที่จะแก้ปัญหาให้เร็วขึ้นอีกได้ เนื่องจากจำนวนครั้งของการย้ายจานเพื่อแก้ปัญหานั้น มีค่าเพิ่มขึ้นในระดับเลขยกกำลังตามจำนวนจาน โดยที่จำนวนครั้งที่น้อยที่สุดของการเคลื่อนย้ายจานจะเท่ากับ 2ⁿ − 1 เสมอ โดย n คือ จำนวนจานทั้งหมด

ลองทำดู
กรณีมีจาน 3 ใบ (จำนวนจานเป็นเลขคี่)

ให้เริ่มด้วยการเคลื่อนย้ายจานใบเล็กสุด ไปทางซ้ายเสมอทีละ 1 หมุด (ถ้าอยู่ซ้ายสุดแล้วให้วนกลับไปเริ่มที่หมุดด้านขวาสุด) หลังจากนั้นให้เคลื่อนย้ายจานอื่น ที่ไม่ผิดกติกา ซึ่งทำได้เพียงลักษณะเดียวเท่านั้น และจะต้องย้ายจานใบเล็กสุดหลังจากที่มีการย้ายจานอื่นทุกครั้ง

คำตอบสำหรับจานจำนวนคี่ 3 ใบ (<<< จานเล็กสุดเคลื่อนไปทางซ้าย)

กรณีมีจาน 4 ใบ (จำนวนจานเป็นเลขคู่)

ให้เริ่มด้วยการเคลื่อนย้ายจานใบเล็กสุด ไปทางขวาเสมอทีละ 1 หมุด (ถ้าอยู่ขวาสุดแล้วให้วนกลับไปเริ่มที่หมุดด้านซ้ายสุด) หลังจากนั้นให้เคลื่อนย้ายจานอื่น ที่ไม่ผิดกติกา ซึ่งทำได้เพียงลักษณะเดียวเท่านั้น และจะต้องย้ายจานใบเล็กสุดหลังจากที่มีการย้ายจานอื่นทุกครั้ง

คำตอบสำหรับจานจำนวนคู่ 4 ใบ (จานเล็กสุดเคลื่อนไปทางขวา >>>)