ความเป็นมา ปริศนาหอคอยแห่งฮานอย (Tower of Hanoi)

ปริศนานี้คิดค้นขึ้นโดย นักคณิตศาสตร์ชาวฝรั่งเศส ชื่อ เอดูอาร์ด ลูคาส (Edouard Lucas) ในปี ค.ศ. 1883 โดยมีตำนานเกี่ยวกับห้องที่ภายในมีเสา 3 เสา และมีจานทองที่มีขนาดแตกต่างกันอยู่ 64 ใบ คล้องอยู่กับเสาที่หนึ่งตามลำดับขนาดของจาน โดยจานใบใหญ่สุดอยู่ด้านล่างสุด และจานใบเล็กสุดอยู่ด้านบนสุด ให้ผู้ดูแลห้องทำการเคลื่อนย้ายจานทองตามคำสั่งที่ระบุไว้คือย้ายจานทองจากเสาที่หนึ่งไปยังเสาที่สาม โดยใช้เสาที่สองเป็นตัวช่วยพักจาน สามารถย้ายจานได้เพียงครั้งละ 1 ใบ และไม่สามารถวางจานใหญ่ไว้บนจานที่มีขนาดเล็กกว่าได้

ถ้าสามารถย้ายจานได้อย่างถูกต้อง ใช้เวลา 1 วินาทีในการย้ายจาน 1 ใบ และใช้จำนวนครั้งการย้ายที่น้อยที่สุด เวลาทั้งหมดที่ใช้ในการย้ายจานคือ 264 − 1 วินาที = 18,446,744,073,709,552,000 วินาที = 18,446,744,073,709,552,000 ÷ 60 ÷ 60 ÷ 24 ÷ 365 = 584,942,417,355.07 ปี หรือประมาณ 585 พันล้านปี ภาษาไทยคือ ห้าแสนแปดหมื่นห้าพันล้านปี ใช้เวลามากกว่าการถือกำเนิดของโลกนี้ประมาณ ห้าแสนแปดหมื่นล้านปี เพราะคาดว่าโลกเรานี้ถูกสร้างขึ้นมาเมื่อประมาณ 4.5 พันล้านปีเท่านั้นเอง ไม่เชื่อ ? หรือเหลือเชื่อ!!! แต่ก็ต้องเชื่อเพราะคณิตศาสตร์มันให้ผลลัพธ์แบบนี้

หรืออีกตัวอย่างของอัลกอริทึมระดับ 2n คือสมมติว่าเรามีกระดาษขนาดใหญ่มากๆ และสามารถพับกระดาษได้ 64 ครั้ง โดยพับครั้งที่หนึ่งได้ความสูง 2 ชั้น พับครั้งต่อไปได้ความสูงเป็น 4,8,16 ชั้น ไปเรื่อยๆ จนพับได้ครบ 64 ครั้ง แล้วให้วัดความสูงของกระดาษ สมมติว่ากระดาษมีความหนา 0.1 mm จำนวนชั้นที่พับได้คือ 264 − 1 ชั้น = 18,446,744,073,709,552,000 ชั้น = 18,446,744,073,709,552,000 x 0.1 ÷ 1,000 ÷ 1,000 = 1,844,674,407,370 กิโลเมตร หรือ 1,844 พันล้านกิโลเมตร หรือ 1.844 ล้านล้านกิโลเมตร เท่านั้นเอง!!! ซึ่งมีความสูงมากกว่าระยะทางจากดวงอาทิตย์ถึงดาวพลูโตซะอีก (ระยะทางจากดวงอาทิตย์ถึงดาวพลูโตประมาณ​ 5 พันล้านกิโลเมตร) ยิ่งไม่น่าเชื่อเข้าไปอีก แต่ก็เป็นเรื่องจริงที่เข้าใจได้
หอคอยแห่งฮานอย (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) ซึ่งถ้ามีจานจำนวนมากๆ การแก้ปัญหานี้จะต้องใช้เวลามหาศาล (ตามความเป็นมาข้างต้น) ถึงแม้ว่าจะใช้คอมพิวเตอร์ที่เร็วที่สุดในโลกในการแก้ปัญหา ก็ไม่มีวิธีที่จะแก้ปัญหาให้เร็วขึ้นอีกได้ เนื่องจากจำนวนครั้งของการย้ายจานเพื่อแก้ปัญหานั้น มีค่าเพิ่มขึ้นในระดับเลขยกกำลังตามจำนวนจาน โดยที่จำนวนครั้งที่น้อยที่สุดของการเคลื่อนย้ายจานจะเท่ากับ 2n − 1 เสมอ โดย n คือ จำนวนจานทั้งหมด

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

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

[Tower_of_Hanoi3.gif]

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

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

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

[Tower_of_Hanoi_4.gif]

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

2020. mnet50.com