แก้ปัญหา หอคอย ฮานอย (Tower of Hanoi) กัน

วันนี้จะมาเขียนโปรแกรมแก้ปัญหา Tower of Hanoi กัน ปัญหานี้มีอยู่ว่า มีเสา 3 เสา แล้วในนั้นมันจะมีแผ่น disk อยู่ที่เสา โดยที่แผ่นใหญ่ต้องอยู่ด่านล่างของแผ่นเล็กเสมอ โดยปัญหาก็คือเราจะย้าย disk ทั้งหมดจากอีกเสา ไปอีกเสา ได้อย่างไร และ ทำด้วยจำนวนวิธีที่จำนวนการย้ายน้อยที่สุด

– เรามาเริ่มจากขั้นแรกก่อนโดยดูจากกรณีถ้ามี disk แค่แผ่นเดียว เราจะย้ายก็จับย้ายตรงๆเลย เช่นถ้ามี disk อยู่เสาซ้ายอยากย้ายมาเสาขวาก็ย้ายมาได้เลย

– ต่อไปลองดูกรณีถ้ามี 2 disk ถ้าเราจะย้ายจาก ซ้ายไปขวา เราก็ต้องเอา อันบนสุดย้ายไปเสากลางก่อน แล้วก็ย้าย disk แผ่น 2 ไปเสาซ้าย แล้วค่อยย้าย disk อันเล็กกว่าที่เราย้ายไปตรงกลางให้มาวางเสาซ้าย

– ต่อไปถ้ามี 3 disk ย้ายจากซ้ายไปขวา เริ่มมองเห็นทางที่จะรีเคอซีฟได้แล้ว นั่นก็คือ เราต้องย้าย แผ่นบนทั้งหมดยกเว้นแผ่นล่าง ไปอยู่เสา กลาง แล้วย้ายแผ่นล่างสุดไปเสาซ้ายแล้วย้ายทั้งหมดที่เราย้ายไปเสากลางมาอยู่เสา ซ้าย

จากที่ยกตัวอย่างจะเห็นว่ากรณีพื้นฐานคือ 1 แผ่นเราย้ายได้เลย ส่วนกรณีทั่วไป n แผ่น เราต้องทำการย้าย แผ่นที่อยู่บนทั้งหมดยกเว้นแผ่นล่าง ก็คือ n-1 แผ่น ไปอยู่ตรงกลาง แล้วก็ย้าย แผ่นล่างสุด 1 แผ่น ไปอยู่ด้านซ้าย เสร็จแล้วก็ย้าย n-1 ที่เสากลาง มาอยู่ด้านซ้ายอีกที เป็นอันเสร็จพิธี

เห่อๆ ยกตัวอย่างอาจจะงงๆ มาดูโค้ดกันเลยดีกว่า

– ประกาศ type ของ function
move::Int->String->String->String->[String]
–ก็คือ input มีดังนี้ จำนวนดิส คำที่บอกว่าเป็นเสาเริ่มต้น,เสากลาง,เสาที่จะย้ายไป ตามลำดับ
–ส่วน output ก็คือลิสประโยคที่จะบอกว่าจะย้ายดิสอะไรจากไหนไปไหนเพื่อที่จะทำให้ย้ายดิสทั้งหมดจากเสาเริ่มต้นไปเสาที่จะย้ายไปได้

– กรณีย้ายแผ่นเดียว
move 1 from center to = ["move top disk from "++from++" to "++to]

– กรณีย้าย n แผ่น
move n from center to = (move (n-1) from to center)++(move 1 from center to)++(move (n-1) center from to)

แค่นี้หละครับก็ได้แล้ว ลองเทสดูจะได้ผลลัพธ์แบบนี้
*Main> move 1 “left” “center” “right”
["move top disk from left to right"]

*Main> hanoi 2 “left” “center” “right”
["move top disk from left to center",
"move top disk from left to right",
"move top disk from center to right"]

*Main> hanoi 3 “left” “center” “right”
["move top disk from left to right",
"move top disk from left to center",
"move top disk from right to center",
"move top disk from left to right",
"move top disk from center to left",
"move top disk from center to right",
"move top disk from left to right"]

ลองไปย้ายตามผลลัพธ์ที่ออกมาดูนะครับจะรู้ว่าย้ายได้อย่างถูกต้อง