แก้ไขปัญหา 8 Queens ด้วยภาษา Haskell

 

 

1. 8 Queens Problem คืออะไร?

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

 

2. วิธีการแก้ปัญหา

ในที่นี้เราจะใช้ภาษา Haskell ซึ่งเป็นภาษาที่เป็นแนวฟังก์ชัน (Functional Programming) มาช่วยในการแก้ปัญหานี้ การใช้ภาษา Haskell จะช่วยทำให้โค้ดเรียบง่ายและสื่อความหมายได้ดีในกรณีของการจัดเรียง

แนวทางในการแก้ปัญหา

1. Permutation - หาทุกการจัดเรียงของราชินีในแถวเดียว. 2. Validation - ตรวจสอบว่าการจัดเรียงดังกล่าวนั้นมีการโจมตีกันหรือไม่โดยใช้แนวทางที่มีประสิทธิภาพ

ตัวอย่าง Code

 type Board = [Int]

isSafe :: Board -> Int -> Int -> Bool
isSafe board row col = not (col `elem` [0..(row-1)] ||
                             (row - col) `elem` [board!!r - r | r <- [0..(row-1)]] ||
                             (row + col) `elem` [board!!r + r | r <- [0..(row-1)]])

placeQueens :: Int -> Board -> [[Board]]
placeQueens 0 board = [board]
placeQueens row board = concat [placeQueens (row-1) (board ++ [col]) | col <- [0..7], isSafe board row col]

solveEightQueens :: [[Board]]
solveEightQueens = placeQueens 8 []

การอธิบายโค้ด

- `type Board = [Int]` - กำหนดชนิดของ Board เป็นลิสต์ที่เก็บตำแหน่งของราชินีแต่ละตัว

- `isSafe` - ฟังก์ชันนี้จะใช้ในการตรวจสอบว่าราชินีตัวที่ `row` และ `col` สามารถวางได้อย่างปลอดภัยหรือไม่

- `placeQueens` - ฟังก์ชันนี้เป็นส่วนหลักที่ใช้ในการวางราชินี โดยจะเรียกใช้ตัวเอง (recursive) เพื่อวางราชินีไปเรื่อย ๆ จนกว่าจะครบ 8 ตัว

- `solveEightQueens` - ตัวเรียกใช้ฟังก์ชันนี้เพื่อให้ได้ผลลัพธ์เป็นการจัดเรียงของราชินีทั้งหมด

 

3. Use Case ในโลกจริง

ปัญหา 8 Queens มีการใช้งานที่กว้างขวางในหลากหลายสาขา อาทิเช่น:

- การออกแบบฐานข้อมูล: การวางข้อมูลในโครงสร้างที่ให้ความปลอดภัยในการเข้าถึง - การจัดตารางเวลา: การหาวิธีที่ดีที่สุดในการจัดกิจกรรมหรือการประชุม - การทดลองทางวิทยาศาสตร์: การหาวิธีจัดเรียงสิ่งของในพื้นที่ที่จำกัด

 

4. การวิเคราะห์ Complexity

Time Complexity

- ในกรณีที่เลวร้ายที่สุด ความซับซ้อนคือ O(N!) เพราะเราต้องลองทุกการจัดเรียงของราชินีในแต่ละขั้น ตอนนี้จะเป็นปัญหา NP-Hard ซึ่งหมายความว่าไม่มีวิธีการที่ทราบผลลัพธ์เร็วกว่า

Space Complexity

- ความซับซ้อนทางพื้นที่คือ O(N) เนื่องจากจะต้องเก็บสถานะการจัดเรียงในแต่ละระดับ

 

5. ข้อดีข้อเสียของ Algorithm นี้

ข้อดี

1. เข้าใจง่าย: โค้ดเขียนในลักษณะอยู่ในระดับสูงทำให้เข้าใจได้ง่าย 2. ใช้ Recursive: การใช้วิธี Recursive ช่วยให้การแก้ปัญหาชัดเจนมากขึ้น 3. เหมาะสำหรับการศึกษาทักษะการเขียนโปรแกรม: การแก้ปัญหานี้สามารถช่วยฝึกทักษะการคิดอย่างมีระบบ และการเข้าใจในธรรมชาติของอัลกอริธึม

ข้อเสีย

1. ความเร็ว: ใช้เวลานาน และมีการใช้หน่วยความจำมากในชุดข้อมูลที่ใหญ่ 2. ไม่มีการใช้วิธีการที่มีประสิทธิภาพ: วิธีนี้อาจไม่เหมาะสมในปัญหาที่มีความซับซ้อนสูงกว่าหรือขนาดใหญ่กว่า 8 Queens

 

6. มาเรียนรู้ Programming ที่ EPT!

หากคุณสนใจในการเขียนโปรแกรมและต้องการเรียนรู้การแก้ปัญหาที่ซับซ้อนแบบนี้ ยังมีการเรียนรู้ในด้านตัวแปร อัลกอริธึม และโครงสร้างข้อมูลอีกมากมายที่คุณสามารถรับเห็นจาก EPT (Expert-Programming-Tutor) เรียนรู้วิธีการเขียนโปรแกรมในรูปแบบที่มีประสิทธิภาพ และสนุกสนานกับการเรียนรู้ในโลกของเทคโนโลยี หากคุณเป็นคนที่มีความสนใจในคอมพิวเตอร์ บอกเลยว่าไม่ควรพลาด!

---

บทความนี้หวังว่าจะช่วยให้คุณเข้าใจในเกี่ยวกับ 8 Queens Problem และวิธีการใช้ภาษา Haskell ในการแก้ปัญหาเชิงคอมพิวเตอร์ต่าง ๆ ได้ดีขึ้น!

 

 

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