หอคอยแห่งฮานอย (Tower of Hanoi)

เมื่อวันพุธที่ผ่านมานั้นมี Programming Day โดยอาจารย์เดฟได้ให้ทำโจทย์ต่างๆ แต่มีข้อนึงต้องแก้ปัญหา หอคอยแห่งฮานอย (Tower of Hanoi) ซึ่งผมใช้ภาษารูบี้ (Ruby) ในการเขียนโปรแกรม โดยอาจารย์ได้แนะนำการทำดังนี้

1. กำหนดปัญหาดังรูปด้านล่าง และกำหนดให้แผ่นจานล่างสุดเป็น head ที่เหลือเป็น tail

tower_of_hanoi_1.png

2. เราสมมติให้ tail ไปอยู่กองกลางดังรูป

tower_of_hanoi_2.png

3. จากนั้นให้ head ไปอยู่กองสุดท้ายดังรูป

tower_of_hanoi_3.png

4. สุดท้ายย้าย tail มาไว้ที่กองสุดท้ายดังรูป

tower_of_hanoi_4.png

#     _
#    |_|
#   |___|
#  |_____|
# |_______|
#     A                 B               C
#
#
#
#                      _
#                     |_|
#  _______           |___|
# |_______|         |_____|
#     A                B                C
#
#
#                      _
#                     |_|
#                    |___|           _______
#                   |_____|         |_______|
#     A                B                C
#
#
#
#                                       _
#                                      |_|
#                                     |___|
#                                    |_____|
#                                   |_______|
#     A                 B               C
 
def hanoi(n, from, to, by)
  if(n > 0)
    # ย้ายส่วนของ tail จาก A ไปไว้ที่ B
    hanoi(n-1, from, by, to)
    # ย้ายส่วนของ head จาก A ไปไว้ที่ C
    puts "Move disk #{n} from #{from} to #{to}"
    # ย้ายส่วนของ tail จาก B ไปไว้ที่ C
    hanoi(n-1, by, to, from)
  end
end
 
print "Input number of disk: "
hanoi(gets().to_i, "A", "C", "B")

ผลจากการทำงาน คือ

Input number of disk: 3
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C