ผลต่างระหว่างรุ่นของ "หอคอยฮานอย"

[[ไฟล์:Tower_of_Hanoi.jpeg|300px|thumb|ชุดของเล่น หอคอยแห่งฮานอย]]

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

หากตำนานนี้เป็นจริง และ พราหมณ์สามารถย้ายจานด้วยความเร็ว 1 ใบต่อวินาทีและใช้จำนวนครั้งการย้ายที่น้อยที่สุด เวลาทั้งหมดที่ใช้ในการแก้ปัญหานี้คือ 2⁶⁴ − 1 วินาที หรือ ประมาณ 585 พันล้านปี (อายุของจักรวาลในตอนนี้ประมาณ 13,700 ล้านปี)

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

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

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

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

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

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

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

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

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

# ย้าย จาน #2 ไปหมุด B

# ย้าย จาน #1 จาก C ไป B ไปไว้บนจาน #2

# ย้าย จาน #3 ไปไว้ที่ C

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

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

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

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

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

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

* บิตที่มีค่าความสำคัญมากที่สุด (บิตที่มีค่ามากที่สุด หรือ บิตทางซ้ายมือสุด) แทนจานใบใหญ่ที่สุด

* บิตที่มีค่าความสำคัญมากที่สุด บิตที่มีค่า 0 หมายถึงจานใบใหญ่ที่สุดอยู่บนหมุดเริ่มต้น และ บิตที่มีค่า 1 หมายถึงอยู่ที่หมุดเป้าหมาย

* สายบิต (อ่านจากบิตซ้าย ไปบิตขวา) ใช้บอกตำแหน่งของจานแต่ละใบตามลำดับ

* ในการอ่านสายบิต บิตที่มีค่าเดียวกับบิตก่อนหน้า หมายความว่า จานใบนั้นจะวางอยู่บนจานใบที่แทนด้วยบิตก่อนหน้านั้น

** ซึ่งในกรณีที่ตัวเลขในสายบิต มีค่าเป็น 0 หรือ 1 ทั้งหมด หมายความว่าจานทั้งหมดอยู่บนหมุดเดียวกัน

* บิตที่มีค่าต่างจากบิตก่อนหน้า มีความหมายว่า จานใบนั้นอยู่บนหมุดถัดจาก หมุดที่วางจานใบก่อนหน้า ไปทางซ้ายหรือทางขวา ซึ่งระบุโดย

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

** หากเป็นจานหมายเลขคู่ ค่าบิต 1 หมายถึง หมุดถัดไปทางขวา และ ค่าบิต 0 หมายถึง หมุดถัดไปทางซ้าย

** รูปแบบดังกล่าวสมมติ ตำแหน่งเริ่มต้น คือหมุดทางด้านซ้าย และ หมุดสุดท้ายคือหมุดทางด้านขวา

** และสมมติการเคลื่อนที่แบบวนรอบ คือ หมุดทางด้านซ้ายสุด ถือเป็นหมุดทางขวาของหมุดที่อยู่ขวาสุด และ หมุดขวาสุด ถือเป็นหมุดทางด้านซ้ายของหมุดซ้ายสุด

** จานใบใหญ่ที่สุด มีค่าบิต 0 ('''0'''0000000) ดังนั้นจึงอยุ่บนหมุดซ้ายสุด (หมุดเริ่มต้น)

** จานใบใหญ่ที่สุด มีค่าบิต 1 ('''1'''1111111) ดังนั้นจึงอยู่ที่หมุดขวาสุด (หมุดเป้าหมาย)

** จานที่เหลือมีค่าบิต 1 ด้วยเช่นกัน (1'''1111111''') จึงวางอยู่บนจานใบใหญ่สุด ดังนั้นจานทุกใบจึงอยู่ที่หมุดเป้าหมาย และ เป็นคำตอบของเกม

** จานใบใหญ่ที่สุด มีค่าบิต 1 ('''1'''1011000) ดังนั้นจึงอยู่ที่หมุดขวาสุด (หมุดเป้าหมาย)

** จาน #3 มีค่าบิต 0 (11'''0'''11000) จานหมายเลขคี่ มีค่าบิต 0 คือหมุดถัดไปทางด้านขวา (ของหมุดขวาสุด) คือ หมุดซ้ายมือสุด

** จาน #4 มีค่าบิต 1 (110'''1'''1000) จานหมายเลขคู่ มีค่าบิต 1 คือหมุดถัดไปทางด้านขวา คือ หมุดกลาง

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

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

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

วิธีนี้บอกว่าจานใบไหนถูกย้ายบ้าง แต่ไม่ได้บอกว่าย้ายไปที่ไหน กฎของการย้ายจะเป็นตัวบอกการย้าย โดยการย้ายจานนั้น จานที่มี[[ภาวะคู่หรือคี่ (คณิตศาสตร์)|ภาวะคู่หรือคี่]] (parity) เหมือนกันจะไม่วางซ้อนทับกัน (คือ จานเลขคู่ จะไม่ย้ายไปวางบนหมุดที่มีจานเลขคู่อยู่ด้านบนสุด จานเลขคี่ ก็จะไม่ย้ายไปวางบนจานเลขคี่) หากเราทำการย้ายตากตามกฎนี้ ก็จะไม่เกิดความสับสนของตำแหน่งที่จะต้องย้ายจานไปวาง [http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html#tower]