หอคอยฮานอย

หอคอยฮานอย (Tower of Hanoi) เป็นปัญหาทางคณิตศาสตร์ ประกอบด้วยเสาสามแท่งและวัตถุต่างขนาดซึ่งเจาะรูตรงกลางคล้องกับเสาตามรูป

ชุดของเล่นหอคอยแห่งฮานอย

ประวัติ

ในปี พ.ศ. ๒๔๕๖ มีนักคณิตศาสตร์ชาวฝรั่งเศสชื่อว่า Édouard Lucas ให้กำเนิดปัญหาหอคอยฮานอยซึ่งได้รับแรงบันดาลใจจากคำบอกกล่าวพราหมณ์ในวัดกาสี วิศวนาถ ณ.เมืองพาราณาสี ปัจจุบันตั้งอยู่ที่รัฐอุตตรประเทศ สาธารณรัฐอินเดีย ซึ่งภายในวัดมีเสา 3 หลักและมีจานสีทองจำนวน 64 ชิ้นคล้องกับเสา ตามคำทำนายของพราหมณ์ว่า "ถ้าปัญหาถูกแก้แล้ววาระสุดท้ายของโลกมาถึง" หมายความว่า พราหมณ์สามารถสับเปลี่ยนจานสีทองจากเสาใดเสาหนึ่งไปยังสองเสาที่เหลือที่ไม่ใช่เสาเดิมในตอนเริ่มต้น จึงเรียกปัญหาอีกชื่อหนึ่งว่า "ปัญหาหอแห่งพรหม" นอกจากนี้ปัญหาหอคอยฮานอยได้รับแรงบันดาลใจจากคำบอกกล่าวพระในวัดกรุงฮานอย ประเทศเวียดนาม ตามคำสั่งของพระว่า "พระสามารถสับเปลี่ยนจานสีทองได้วันละ 1 ชิ้น" หมายความว่า พระสามารถสับเปลี่ยนจานสีทองได้ครั้งละ 1 ชิ้น เท่านั้น อีกทั้งนำโครงสร้างสถาปัตยกรรมของวัดในกรุงฮานอยมีลักษณะว่า ห้องมีการเรียงลำดับขนาดห้องของวัดที่ใหญ่ที่สุดไปจนถึงห้องของวัดที่เล็กที่สุดจะอยู่ชั้นล่างไปหาชั้นบนที่สุด และทุกชั้นจะมีหลังคาในวัด 1 หลังเดียวกัน มาเป็นลักษณะในปัญหาของหอคอยฮานอย

เริ่มต้นและเป้าหมาย

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

กติกา

จากคำทำนายของพราหมณ์ในอินเดียและคำสั่งของพระในวัดกรุงฮานอย นำมาสร้างเป็นกฎกติกาของปัญหาหอคอยฮานอยในปัจจุบันนี้

• วัตถุ 1 ชิ้นสามารถสับเปลี่ยนได้ 1 ครั้งเท่านั้น
• ห้ามวางวัตถุที่ใหญ่อยู่ด้านบนวัตถุที่เล็ก

คำตอบ

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

ขั้นตอนวิธีเวียนเกิด

• ตั้งชื่อหมุดทั้งสาม A,B,C
• สมมุติมีจานทั้งหมด n ใบ
• ติดเบอร์ให้กับจานจากเล็กที่สุด 1 ไปจนถึงใหญ่ที่สุด n

ต้องการย้ายจานทั้งหมด n ใบจากหมุด A ไปยังหมุด B:

1. หากย้ายจาน n-1 ใบจาก A ไปไว้ที่ C ก่อน จะทำให้เหลือจาน #n (หมายเลข n ใบใหญ่ที่สุด) เพียงใบเดียวแก้วหน่อง
2. ย้ายจาน #n จาก A ไปไว้ที่ B
3. ย้ายจาน n-1 ใบจาก C ไปที่ B ซึ่งจานทั้งหมดจะอยู่บนจาน #n

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

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

เราสามารถคำนวณหาจำนวนครั้งของการเคลื่อนย้ายจาน ที่จำเป็นในการแก้ปัญหานี้ จากความสัมพันธ์เวียนเกิด (recurrence relation) ได้เท่ากับ ${\displaystyle 2^{n}-1}$  โดย ${\displaystyle n}$  คือ จำนวนจานทั้งหมด ผลลัพธ์นี้ได้จากข้อสังเกตที่ว่า ในขั้นตอนที่ 1 และ 3 ใช้เวลาในการแก้ปัญหา ${\displaystyle T_{n-1}}$  และขั้นตอนที่ 2 ใช้เวลาคงที่ ซึ่งให้ความสัมพันธ์ ${\displaystyle T_{n}=2T_{n-1}+1}$ 

โปรแกรมในการแก้ปัญหาในภาษาแฮสเคล:

hanoi n = hanoi' n 1 2 3 hanoi' 0 _ _ _ = [] hanoi' n f i t = (hanoi' (n-1) f t i) ++ (f, t) : (hanoi' (n-1) i f t) 

โดย n คือ จำนวนจานทั้งหมด โปรแกรมจะส่งคืนผลในรูปของรายการของการเคลื่อนย้ายทั้งหมดที่ต้องกระทำ

คำอธิบาย

ขั้นตอนวิธีด้านบน สามารถอธิบายด้วยภาษาชาวบ้านได้ดังนี้

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

ตอนนี้ เรามีจาน 2 ใบวางตามลำดับถูกต้องที่หมุด B และ หมุด C ไม่มีจาน

1. ย้ายจาน #3 ไปไว้ที่ C
2. และทำตามขั้นตอนที่ 1 ถึง 3 เพื่อย้ายจาน #1 และ #2 ไปไว้บนจาน #3

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

จำนวนครั้งในการเคลื่อนย้ายจาน n ใบเพื่อแก้ปัญหามีจำนวนครั้งเท่ากับ 2ⁿ-1

ในทางปฏิบัติ

 

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

 

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

ทำการเคลื่อนย้ายจาน #1 และจานอื่นที่ใหญ่กว่าสลับกัน โดยที่หากมีจานใหญ่ 2 ใบที่สามารถย้ายได้ ให้ย้ายใบที่เล็กกว่าไปไว้บนใบที่ใหญ่กว่า ในการเคลื่อนย้าย ให้เคลื่อนจานที่มีหมายเลขคี่ไปทางซ้ายทีละ 1 หมุดจนสุดแล้ววนกลับมาเริ่มที่หมุดด้านขวา และจานที่มีหมายเลขคู่ไปทางขวาทีละ 1 หมุดจนสุดแล้ววนกลับมาเริ่มที่หมุดที่หมุดด้านซ้าย

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

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

รหัสฐานสอง

เราอาจใช้เลขฐานสอง ในการระบุการเคลื่อนย้ายตำแหน่งของจาน (โดยสภาวะเริ่มต้นเป็นการเคลื่อนที่ #0 มีเลขฐานสองทุกตำแหน่งเป็น 0 และ สภาวะสุดท้ายเป็นการเคลื่อนที่ #2ⁿ−1 มีเลขฐานสองทุกตำแหน่งเป็น 1) โดยใช้วิธีการดังนี้

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

ตัวอย่าง จาน 8 ใบ:

• การย้าย #0 (00000000)
  • จานใบใหญ่ที่สุดมีค่าบิต 0 (00000000) ดังนั้นจึงอยุ่บนหมุดซ้ายสุด (หมุดเริ่มต้น)
  • จานที่เหลือมีค่าบิต 0 ด้วยเช่นกัน (00000000) จึงวางอยู่บนจานใบใหญ่สุด ดังนั้นจานทุกใบจึงอยู่ที่หมุดเริ่มต้น
• การย้าย #255 (11111111)
  • จานใบใหญ่ที่สุดมีค่าบิต 1 (11111111) ดังนั้นจึงอยู่ที่หมุดขวาสุด (หมุดเป้าหมาย)
  • จานที่เหลือมีค่าบิต 1 ด้วยเช่นกัน (11111111) จึงวางอยู่บนจานใบใหญ่สุด ดังนั้นจานทุกใบจึงอยู่ที่หมุดเป้าหมาย และเป็นคำตอบของเกม
• การย้าย #216 (11011000)
  • จานใบใหญ่ที่สุดมีค่าบิต 1 (11011000) ดังนั้นจึงอยู่ที่หมุดขวาสุด (หมุดเป้าหมาย)
  • จาน #2 มีค่าบิต 1 (11011000) ดังนั้นจึงวางอยู่บนจานใบแรกที่หมุดขวาสุด
  • จาน #3 มีค่าบิต 0 (11011000) จานหมายเลขคี่ มีค่าบิต 0 คือหมุดถัดไปทางด้านขวา (ของหมุดขวาสุด) คือหมุดซ้ายมือสุด
  • จาน #4 มีค่าบิต 1 (11011000) จานหมายเลขคู่ มีค่าบิต 1 คือหมุดถัดไปทางด้านขวา คือหมุดกลาง
  • จาน #5 มีค่าบิต 1 (11011000) เหมือนบิตก่อนหน้า จึงวางอยู่บนจานก่อนหน้าที่หมุดกลาง
  • จาน #6 มีค่าบิต 0 (11011000) จานหมายเลขคู่ มีค่าบิต 0 คือหมุดถัดไปทางด้านซ้าย คือหมุดซ้ายสุด
  • จาน #7 #8 มีค่าบิต 0 (11011000) ซึ่งมีค่าเหมือนบิตก่อนหน้า ดังนั้นจานทั้งสองจึงวางซ้อนอยู่บนจาน #6 ที่หมุดซ้ายสุด

ตามรูปแบบเลขฐานสองนี้ เราสามารถหาตำแหน่งของจานต่าง ๆ ได้ไม่ยาก ถึงแม้จะมีจานเป็นจำนวนมากก็ตาม ส่วนหาการย้ายจาน ครั้งที่ n ว่าย้ายจากหมุดไหนไปยังหมุดไหนนั้น สามารถหาได้จากเลขฐานสอง n โดยใช้การดำเนินการเป็นบิต (bitwise operation) กรณีที่ใช้วากยสัมพันธ์ของภาษาซี การย้ายครั้งที่ n จะย้ายจากหมุด (n&n-1)%3 ไปยังหมุด ((n|n-1)+1)%3 โดยที่ตำแหน่งเริ่มของจานอยู่ที่หมุด 0 และจบการย้ายที่หมุด 1 หรือหมุด 2 ขึ้นอยู่กับจำนวนจานว่าเป็นจำนวนคู่หรือจำนวนคี่ ซึ่งวิธีการนี้ ช่วยให้สร้างโปรแกรมสำหรับแก้ปัญหาด้วยคอมพิวเตอร์เป็นแบบไม่เวียนเกิด และสามารถแก้ปัญหาได้รวดเร็ว

รหัสเกรย์

รหัสเกรย์ (Gray code) ซึ่งเป็นระบบตัวเลขฐานสองแบบหนึ่ง เป็นรูปแบบจำลองอีกแบบหนึ่งซึ่งสามารถใช้ในการแก้ปัญหา ในระบบรหัสเกรย์นั้น ตัวเลขจะเขียนอยู่ในรูปผสมของตัวเลข 0 และ 1 แต่จะแตกต่างเลขฐานสองมาตรฐาน โดยรหัสเกรย์สำหรับแทนตัวเลขที่อยู่ถัดกันจะต่างกันเพียง 1 บิตเท่านั้น จำนวนบิตที่ใช้ในรหัสเกรย์นั้นมีความสำคัญ รวมทั้งเลขศูนย์ที่อยู่นำหน้าก็มีความสำคัญ ซึ่งต่างจากเลขฐานสองมาตรฐานที่เลขศูนย์ที่อยู่นำหน้านั้นไม่มีความสำคัญ

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

วิธีนี้บอกว่าจานใบไหนถูกย้ายบ้าง แต่ไม่ได้บอกว่าย้ายไปที่ไหน กฎของการย้ายจะเป็นตัวบอกการย้าย โดยการย้ายจานนั้น จานที่มีภาวะคู่หรือคี่ (parity) เหมือนกันจะไม่วางซ้อนทับกัน (จานเลขคู่จะไม่ย้ายไปวางบนหมุดที่มีจานเลขคู่อยู่ด้านบนสุด จานเลขคี่ก็จะไม่ย้ายไปวางบนจานเลขคี่) หากเราทำการย้ายตามกฎนี้ ก็จะไม่เกิดความสับสนของตำแหน่งที่จะต้องย้ายจานไปวาง[1]

แหล่งข้อมูลอื่น

ประวัติ

• Scans of Lucas's original Tower of Hanoi puzzle in French, with translations
• Tower of Hanoi Facts 2007-09-28 ที่ เวย์แบ็กแมชชีน
• Eduard Lucas [2]
• วัดกาสี วิศวนาถ [3]
• Marcel Danesi. (2004). Lucas’s Tower of Hanoi Puzzle. In John Wiley & Sons , Inc. (Ed.), The Liar Paradox And The Tower of Hanoi: The ten greatest math puzzles of all time. (pp.109-110). New York City , The United States America: Wiley

ขั้นตอนวิธี

• Theory, recursive and a per step algorithms with Java implementation ที่ cut-the-knot
• Bicolor Tower of Hanoi ที่ cut-the-knot
• Hanoimania, over 100 implementations of the Tower of Hanoi problem 2004-02-11 ที่ เวย์แบ็กแมชชีน
• Towers of Hanoi Online game
• Play Towers of Hanoi Online
• Goobix.com's Tower of Hanoi, with 8 disks, playable online
• Binary Numbers and the Standard Gray Code, with a discussion of the Gray Code solution