แก้ปัญหาหอคอยฮานอยด้วย python
เขียนเมื่อ 2016/03/01 20:15
แก้ไขล่าสุด 2024/02/12 20:14
หอคอยฮานอย (Tours de Hanoï) เป็นปัญหาทางคณิตศาสตร์ที่คิดขึ้นโดยฟร็องซัว เอดูอาร์ อนาตอล ลูว์กา (François Édouard Anatole Lucas, ปี 1842 - 1891) นักคณิตศาสตร์ชาวฝรั่งเศส
รูปแบบและกติกา
เกมนี้เป็นเกมง่ายๆที่มีส่วนประกอบเป็นแค่แผ่นจานหลายๆอันซ้อนๆกัน โดยที่อันที่วางอยู่ด้านล่างสุดจะมีขนาดใหญ่สุด แล้วอันที่เรียงซ้อนขึ้นมาก็มีขนาดเล็กลดหลั่นกันลงมา
นอกจากนั้นก็อาจมีเสาสามแท่งเป็นหลักสำหรับเสียบแผ่นจาน เสาอาจมีหรือไม่มีก็ได้ เพียงแต่ต้องรู้ว่ามีหลักสำหรับวางแผ่นจานอยู่ ๓ ตำแหน่ง
กติกาการเล่นก็ง่ายๆคือให้ย้ายแผ่นจานทั้งหมดจากหลักหนึ่งไปยังอีกหลักหนึ่ง ถ้าย้ายได้หมดก็จบเกม
แต่มีข้อกำหนดว่า
- ย้ายแผ่นจานได้ทีละแผ่นเท่านั้น
- ห้ามย้ายออกไปที่อื่นนอกจากในหลัก ๓ ตำแหน่งนี้
- ไม่สามารถนำแผ่นจานที่ใหญ่กว่าทับแผ่นจานที่เล็กกว่าได้
วิเคราะห์ปัญหา
ถ้าได้ลองเล่นดูไปเรื่อยๆจะเริ่มจับหลักได้ว่าการจะจบเกมนี้ได้เร็วที่สุดนั้นจะต้องย้ายแผ่นจานด้วยหลักที่ตายตัวอย่างหนึ่ง
สมมุติมีจาน n ใบ ให้จานบนสุดเป็นจานใบที่ 1 และถัดมาเป็นใบที่ 2 และล่างสุดเป็นใบที่ n (ในภาพ n=5)
และให้หลักทั้ง ๓ ชื่อ ก. ข. ค. ไล่จากซ้ายไปขวา
หลักการคือ
- จานใบที่ 1 จะขยับทุก 2 ตา ใบที่ 2 ขยับทุก 22 = 4 ตา ใบที่ 3 ขยับทุก 23 = 8 ตา ใบที่ n ขยับทุก 2n ตา
- ทิศทางการย้ายของแต่ละจานต้องมีความตายตัว คือ ก. -> ข. -> ค. -> ก. หรือ ก. -> ค. -> ข. -> ก. ตลอดเกม โดยจานที่ 1, 3, 5,... จะมีทิศทางเหมือนกัน ส่วน 2, 4, 6,... จะเป็นทิศตรงกันข้าม
- ใบที่ n จะขยับครั้งเดียวเท่านั้น และเป็นการขยับตอนกลางเกม และใบที่ n-1 จะขยับแค่ 2 ครั้ง ใบที่ n-2 ขยับ 22 = 4 ครั้ง ใบที่ 1 ขยับ 2n-1 ครั้ง
- จำนวนครั้งที่ขยับรวมทั้งหมดคือ 2n-1 ครั้ง
การเขียนโปรแกรมเพื่อแก้ปัญหา
เกมนี้มีชื่อเสียงในเรื่องที่ว่าสามารถแก้ปัญหาได้โดยง่ายด้วยการใช้ฟังก์ชันเวียนเกิด
เขียนโค้ดแก้ปัญหาด้วยภาษาไพธอน
ผลลัพธ์
จะเห็นว่าจำนวนครั้งที่ย้ายคือ 25-1 = 31 ครั้ง
ใช้โปรแกรมจำลองสามมิติเพื่อจำลองภาพการย้าย
เพื่อให้เห็นภาพชัดจึงลองสร้างภาพเคลื่อนไหวให้เห็นขั้นตอน
ในที้นี้ลองใช้โปรแกรมมายาซึ่งเขียนโค้ดเพื่อสร้างแผ่นจานและตั้งคีย์เฟรมด้วยภาษาไพธอน
เขียนโค้ดคล้ายเดิมแต่ต่างออกไปตรงที่เปลี่ยนจากการ print เป็นการตั้งคีย์เฟรมเพื่อย้ายตำแหน่งแผ่นจาน
คลิปแสดงภาพการย้ายแผ่นจาน ภาพในนี้มีการแต่งลายเพิ่มให้กับแผ่นจาน ภาพประกอบทั้งหมดมาจากตัวละครจากหนังสือสอนความรู้เรื่องโพรโทคอลอินเทอร์เน็ต รายละเอียดเกี่ยวกับหนังสือเขียนไว้แล้วใน https://phyblas.hinaboshi.com/20160229
รูปแบบและกติกา
เกมนี้เป็นเกมง่ายๆที่มีส่วนประกอบเป็นแค่แผ่นจานหลายๆอันซ้อนๆกัน โดยที่อันที่วางอยู่ด้านล่างสุดจะมีขนาดใหญ่สุด แล้วอันที่เรียงซ้อนขึ้นมาก็มีขนาดเล็กลดหลั่นกันลงมา
นอกจากนั้นก็อาจมีเสาสามแท่งเป็นหลักสำหรับเสียบแผ่นจาน เสาอาจมีหรือไม่มีก็ได้ เพียงแต่ต้องรู้ว่ามีหลักสำหรับวางแผ่นจานอยู่ ๓ ตำแหน่ง
กติกาการเล่นก็ง่ายๆคือให้ย้ายแผ่นจานทั้งหมดจากหลักหนึ่งไปยังอีกหลักหนึ่ง ถ้าย้ายได้หมดก็จบเกม
แต่มีข้อกำหนดว่า
- ย้ายแผ่นจานได้ทีละแผ่นเท่านั้น
- ห้ามย้ายออกไปที่อื่นนอกจากในหลัก ๓ ตำแหน่งนี้
- ไม่สามารถนำแผ่นจานที่ใหญ่กว่าทับแผ่นจานที่เล็กกว่าได้
วิเคราะห์ปัญหา
ถ้าได้ลองเล่นดูไปเรื่อยๆจะเริ่มจับหลักได้ว่าการจะจบเกมนี้ได้เร็วที่สุดนั้นจะต้องย้ายแผ่นจานด้วยหลักที่ตายตัวอย่างหนึ่ง
สมมุติมีจาน n ใบ ให้จานบนสุดเป็นจานใบที่ 1 และถัดมาเป็นใบที่ 2 และล่างสุดเป็นใบที่ n (ในภาพ n=5)
และให้หลักทั้ง ๓ ชื่อ ก. ข. ค. ไล่จากซ้ายไปขวา
หลักการคือ
- จานใบที่ 1 จะขยับทุก 2 ตา ใบที่ 2 ขยับทุก 22 = 4 ตา ใบที่ 3 ขยับทุก 23 = 8 ตา ใบที่ n ขยับทุก 2n ตา
- ทิศทางการย้ายของแต่ละจานต้องมีความตายตัว คือ ก. -> ข. -> ค. -> ก. หรือ ก. -> ค. -> ข. -> ก. ตลอดเกม โดยจานที่ 1, 3, 5,... จะมีทิศทางเหมือนกัน ส่วน 2, 4, 6,... จะเป็นทิศตรงกันข้าม
- ใบที่ n จะขยับครั้งเดียวเท่านั้น และเป็นการขยับตอนกลางเกม และใบที่ n-1 จะขยับแค่ 2 ครั้ง ใบที่ n-2 ขยับ 22 = 4 ครั้ง ใบที่ 1 ขยับ 2n-1 ครั้ง
- จำนวนครั้งที่ขยับรวมทั้งหมดคือ 2n-1 ครั้ง
การเขียนโปรแกรมเพื่อแก้ปัญหา
เกมนี้มีชื่อเสียงในเรื่องที่ว่าสามารถแก้ปัญหาได้โดยง่ายด้วยการใช้ฟังก์ชันเวียนเกิด
เขียนโค้ดแก้ปัญหาด้วยภาษาไพธอน
t = 0 # ตั้งจำนวนตาเริ่มต้น
def hanoi(n,a,b,c): # นิยามฟังก์ชันฮานอย พารามิเตอร์คือจำนวนจาน ตามด้วยชื่อหลักทั้งสาม
global t
if(n>0): # จะมีการกระทำเกิดขึ้นตราบใดที่ n มากกว่า 0
hanoi(n-1,a,c,b) # เรียกใช้ฟังก์ชันเดิมที่ n น้อยกว่าอยู่ 1 โดยสลับ b กับ c
t += 1 # นับบวกจำนวนตา
print('%d. ย้ายจานที่ %d จาก %s ไป %s'%(t,n,a,b)) # แสดงวิธีการย้าย
hanoi(n-1,c,b,a) # เรียกใช้ฟังก์ชันเดิมที่ n น้อยกว่าอยู่ 1 โดยสลับ a กับ c
hanoi(5,'ก.','ข.','ค.') # เรียกใช้ฟังก์ชันเพื่อเล่นเกมที่มี 5 จาน
def hanoi(n,a,b,c): # นิยามฟังก์ชันฮานอย พารามิเตอร์คือจำนวนจาน ตามด้วยชื่อหลักทั้งสาม
global t
if(n>0): # จะมีการกระทำเกิดขึ้นตราบใดที่ n มากกว่า 0
hanoi(n-1,a,c,b) # เรียกใช้ฟังก์ชันเดิมที่ n น้อยกว่าอยู่ 1 โดยสลับ b กับ c
t += 1 # นับบวกจำนวนตา
print('%d. ย้ายจานที่ %d จาก %s ไป %s'%(t,n,a,b)) # แสดงวิธีการย้าย
hanoi(n-1,c,b,a) # เรียกใช้ฟังก์ชันเดิมที่ n น้อยกว่าอยู่ 1 โดยสลับ a กับ c
hanoi(5,'ก.','ข.','ค.') # เรียกใช้ฟังก์ชันเพื่อเล่นเกมที่มี 5 จาน
ผลลัพธ์
1. ย้ายจานที่ 1 จาก ก. ไป ข.
2. ย้ายจานที่ 2 จาก ก. ไป ค.
3. ย้ายจานที่ 1 จาก ข. ไป ค.
4. ย้ายจานที่ 3 จาก ก. ไป ข.
5. ย้ายจานที่ 1 จาก ค. ไป ก.
6. ย้ายจานที่ 2 จาก ค. ไป ข.
7. ย้ายจานที่ 1 จาก ก. ไป ข.
8. ย้ายจานที่ 4 จาก ก. ไป ค.
9. ย้ายจานที่ 1 จาก ข. ไป ค.
10. ย้ายจานที่ 2 จาก ข. ไป ก.
11. ย้ายจานที่ 1 จาก ค. ไป ก.
12. ย้ายจานที่ 3 จาก ข. ไป ค.
13. ย้ายจานที่ 1 จาก ก. ไป ข.
14. ย้ายจานที่ 2 จาก ก. ไป ค.
15. ย้ายจานที่ 1 จาก ข. ไป ค.
16. ย้ายจานที่ 5 จาก ก. ไป ข.
17. ย้ายจานที่ 1 จาก ค. ไป ก.
18. ย้ายจานที่ 2 จาก ค. ไป ข.
19. ย้ายจานที่ 1 จาก ก. ไป ข.
20. ย้ายจานที่ 3 จาก ค. ไป ก.
21. ย้ายจานที่ 1 จาก ข. ไป ค.
22. ย้ายจานที่ 2 จาก ข. ไป ก.
23. ย้ายจานที่ 1 จาก ค. ไป ก.
24. ย้ายจานที่ 4 จาก ค. ไป ข.
25. ย้ายจานที่ 1 จาก ก. ไป ข.
26. ย้ายจานที่ 2 จาก ก. ไป ค.
27. ย้ายจานที่ 1 จาก ข. ไป ค.
28. ย้ายจานที่ 3 จาก ก. ไป ข.
29. ย้ายจานที่ 1 จาก ค. ไป ก.
30. ย้ายจานที่ 2 จาก ค. ไป ข.
31. ย้ายจานที่ 1 จาก ก. ไป ข.
2. ย้ายจานที่ 2 จาก ก. ไป ค.
3. ย้ายจานที่ 1 จาก ข. ไป ค.
4. ย้ายจานที่ 3 จาก ก. ไป ข.
5. ย้ายจานที่ 1 จาก ค. ไป ก.
6. ย้ายจานที่ 2 จาก ค. ไป ข.
7. ย้ายจานที่ 1 จาก ก. ไป ข.
8. ย้ายจานที่ 4 จาก ก. ไป ค.
9. ย้ายจานที่ 1 จาก ข. ไป ค.
10. ย้ายจานที่ 2 จาก ข. ไป ก.
11. ย้ายจานที่ 1 จาก ค. ไป ก.
12. ย้ายจานที่ 3 จาก ข. ไป ค.
13. ย้ายจานที่ 1 จาก ก. ไป ข.
14. ย้ายจานที่ 2 จาก ก. ไป ค.
15. ย้ายจานที่ 1 จาก ข. ไป ค.
16. ย้ายจานที่ 5 จาก ก. ไป ข.
17. ย้ายจานที่ 1 จาก ค. ไป ก.
18. ย้ายจานที่ 2 จาก ค. ไป ข.
19. ย้ายจานที่ 1 จาก ก. ไป ข.
20. ย้ายจานที่ 3 จาก ค. ไป ก.
21. ย้ายจานที่ 1 จาก ข. ไป ค.
22. ย้ายจานที่ 2 จาก ข. ไป ก.
23. ย้ายจานที่ 1 จาก ค. ไป ก.
24. ย้ายจานที่ 4 จาก ค. ไป ข.
25. ย้ายจานที่ 1 จาก ก. ไป ข.
26. ย้ายจานที่ 2 จาก ก. ไป ค.
27. ย้ายจานที่ 1 จาก ข. ไป ค.
28. ย้ายจานที่ 3 จาก ก. ไป ข.
29. ย้ายจานที่ 1 จาก ค. ไป ก.
30. ย้ายจานที่ 2 จาก ค. ไป ข.
31. ย้ายจานที่ 1 จาก ก. ไป ข.
จะเห็นว่าจำนวนครั้งที่ย้ายคือ 25-1 = 31 ครั้ง
ใช้โปรแกรมจำลองสามมิติเพื่อจำลองภาพการย้าย
เพื่อให้เห็นภาพชัดจึงลองสร้างภาพเคลื่อนไหวให้เห็นขั้นตอน
ในที้นี้ลองใช้โปรแกรมมายาซึ่งเขียนโค้ดเพื่อสร้างแผ่นจานและตั้งคีย์เฟรมด้วยภาษาไพธอน
เขียนโค้ดคล้ายเดิมแต่ต่างออกไปตรงที่เปลี่ยนจากการ print เป็นการตั้งคีย์เฟรมเพื่อย้ายตำแหน่งแผ่นจาน
t = 0 # เวลาเริ่มต้น
def hanoi(n,a,b,c):
if(n>0):
global t
hanoi(n-1,a,c,b)
mc.setKeyframe(chan[n-1],at='tx',v=a*15,t=t) # ตั้งคีย์เฟรมตำแหน่งจานก่อนย้าย
mc.setKeyframe(chan[n-1],at='ty',v=ty[n-1],t=t) # ตั้งคีย์เฟรมความสูงจานก่อนย้าย
mc.setKeyframe(chan[n-1],at='ty',v=6,t=t+11) # ตั้งคีย์เฟรมความสูงจานระหว่างย้าย
mc.setKeyframe(chan[n-1],at='ty',v=6,t=t+14)
ty[n-1] = d[b]+0.5 # กำหนดความสูงจานหลังย้าย
d[b] += 1 # เพิ่มจำนวนจานหลัก b
d[a] -= 1 # ลดจำนวนจานหลัก a
mc.setKeyframe(chan[n-1],at='tx',v=b*15,t=t+25) # ตั้งคีย์เฟรมตำแหน่งจานหลังย้าย
mc.setKeyframe(chan[n-1],at='ty',v=ty[n-1],t=t+25) # ตั้งคีย์เฟรมความสูงจานหลังย้าย
t += 25 # บวกเวลาเพิ่ม 25 เฟรม = 1 วินาที
hanoi(n-1,c,b,a)
chan = [] # ลิสต์เก็บชื่อจานบนหลัก
ty = [] # ลิสต์ของความสูงของจาน
d = [5,0,0] # ลิสต์แสดงจำนวนจานในแต่ละหลัก ประกอบด้วยหลัก 0, 1, 2 โดยเริ่มต้นแผ่นจานอยู่ที่หลัก 0
for i in range(1,6):
chan += mc.polyCylinder(r=i+2,h=1,sx=20+i**2,ch=0) # สร้างแผ่นจาน พร้อมใส่ชื่อลงลิสต์
ty += [5.5-i] # กำหนดความสูงเริ่มต้น โดยใส่ลงในลิสต์
hanoi(5,0,1,2) # เรียกใช้ฟังก์ชันฮานอยเพื่อเล่นเกมที่มี 5 จาน
def hanoi(n,a,b,c):
if(n>0):
global t
hanoi(n-1,a,c,b)
mc.setKeyframe(chan[n-1],at='tx',v=a*15,t=t) # ตั้งคีย์เฟรมตำแหน่งจานก่อนย้าย
mc.setKeyframe(chan[n-1],at='ty',v=ty[n-1],t=t) # ตั้งคีย์เฟรมความสูงจานก่อนย้าย
mc.setKeyframe(chan[n-1],at='ty',v=6,t=t+11) # ตั้งคีย์เฟรมความสูงจานระหว่างย้าย
mc.setKeyframe(chan[n-1],at='ty',v=6,t=t+14)
ty[n-1] = d[b]+0.5 # กำหนดความสูงจานหลังย้าย
d[b] += 1 # เพิ่มจำนวนจานหลัก b
d[a] -= 1 # ลดจำนวนจานหลัก a
mc.setKeyframe(chan[n-1],at='tx',v=b*15,t=t+25) # ตั้งคีย์เฟรมตำแหน่งจานหลังย้าย
mc.setKeyframe(chan[n-1],at='ty',v=ty[n-1],t=t+25) # ตั้งคีย์เฟรมความสูงจานหลังย้าย
t += 25 # บวกเวลาเพิ่ม 25 เฟรม = 1 วินาที
hanoi(n-1,c,b,a)
chan = [] # ลิสต์เก็บชื่อจานบนหลัก
ty = [] # ลิสต์ของความสูงของจาน
d = [5,0,0] # ลิสต์แสดงจำนวนจานในแต่ละหลัก ประกอบด้วยหลัก 0, 1, 2 โดยเริ่มต้นแผ่นจานอยู่ที่หลัก 0
for i in range(1,6):
chan += mc.polyCylinder(r=i+2,h=1,sx=20+i**2,ch=0) # สร้างแผ่นจาน พร้อมใส่ชื่อลงลิสต์
ty += [5.5-i] # กำหนดความสูงเริ่มต้น โดยใส่ลงในลิสต์
hanoi(5,0,1,2) # เรียกใช้ฟังก์ชันฮานอยเพื่อเล่นเกมที่มี 5 จาน
คลิปแสดงภาพการย้ายแผ่นจาน ภาพในนี้มีการแต่งลายเพิ่มให้กับแผ่นจาน ภาพประกอบทั้งหมดมาจากตัวละครจากหนังสือสอนความรู้เรื่องโพรโทคอลอินเทอร์เน็ต รายละเอียดเกี่ยวกับหนังสือเขียนไว้แล้วใน https://phyblas.hinaboshi.com/20160229