ปัญหา 8 Queens: แนวทางการแก้ปัญหาด้วย Kotlin

 

 

บทนำ

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

 

ปัญหาที่ต้องการแก้ไข

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

 

อัลกอริธึมที่ใช้

ในการแก้ปัญหา 8 Queens มักใช้ "Backtracking Algorithm" มันทำงานโดยการวางควีนในตำแหน่งที่เป็นไปได้แล้ว进行การตรวจสอบว่าไม่มีควีนตัวไหนที่สามารถจับกันได้ ถ้าทำไม่ได้จะย้อนกลับไปและลองตำแหน่งใหม่จนกว่าจะหาคำตอบที่ถูกต้อง หรือจนกว่าจะหมดตัวเลือกที่เป็นไปได้

 

เขียนโค้ดด้วย Kotlin

ในส่วนนี้เราจะยกตัวอย่างโค้ดที่เขียนด้วยภาษา Kotlin สำหรับการแก้ปัญหา 8 Queens ดังนี้:

 fun main() {
    val N = 8
    val board = Array(N) { IntArray(N) }
    solveNQueens(board, 0)
}

fun printSolution(board: Array<IntArray>) {
    for (row in board) {
        for (col in row) {
            print(if (col == 1) "Q " else ". ")
        }
        println()
    }
    println()
}

fun isSafe(board: Array<IntArray>, row: Int, col: Int): Boolean {
    // เช็คบรรทัด
    for (i in 0 until col) {
        if (board[row][i] == 1) return false
    }
    // เช็คซ้ายแนวทแยง
    for (i in row downTo 0) {
        if (col - (row - i) >= 0 && board[i][col - (row - i)] == 1) return false
    }
    // เช็คขวาแนวทแยง
    for (i in row until board.size) {
        if (col + (i - row) < board.size && board[i][col + (i - row)] == 1) return false
    }
    return true
}

fun solveNQueens(board: Array<IntArray>, col: Int): Boolean {
    // ถ้าทุกควีนถูกวางลงแล้ว
    if (col >= board.size) {
        printSolution(board)
        return true
    }
    for (i in 0 until board.size) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1
            if (solveNQueens(board, col + 1)) return true
            board[i][col] = 0 // ย้อนกลับ
        }
    }
    return false
}

ในโค้ดนี้เราใช้ฟังก์ชัน `solveNQueens` เพื่อทำการวางคิวในแต่ละคอลัมน์ และตรวจสอบตำแหน่งที่ปลอดภัยด้วยฟังก์ชัน `isSafe` และเรียก `printSolution` เพื่อแสดงผลลัพธ์เมื่อสามารถวางควีนได้ครบ 8 ตัว

 

Use Cases ในโลกจริง

1. การวางแผนและจัดการทรัพยากร: เช่น การจัดสรรงบประมาณหรือระเบียบในการทำงานของทีมงาน 2. การวิเคราะห์และแก้ไขปัญหาในเกมส์: โดยเฉพาะเกมส์ที่เกี่ยวข้องกับการวางตำแหน่ง เช่น หมากรุก 3. การจัดสวน: การวางต้นไม้ในสวนเพื่อให้มีความเข้ากันและไม่บดบังซึ่งกันและกัน

 

วิเคราะห์ Complexity

- Time Complexity: ในกรณีที่เลวร้ายที่สุด, Time Complexity ของ Backtracking Algorithm นี้คือ O(N!), เนื่องจากจำนวนวิธีการวางควีนทั้งหมดที่อาจจะเกิดขึ้นใน N คอลัมน์ สำหรับ N = 8, จะมีเฉลี่ยอยู่ที่ประมาณ 120 ตัวเลือก - Space Complexity: จำเป็นต้องใช้ O(N) สำหรับ stack ของ recursive calls โดยที่ N คือจำนวนของควีนที่ต้องวาง

 

ข้อดีและข้อเสียของ Algorithm นี้

ข้อดี

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

ข้อเสีย

- ความไม่เสถียรเมื่อ N เพิ่มมากขึ้น: เมื่อ N เพิ่มขึ้น ปัญหาที่เกี่ยวข้องกับเวลาที่ใช้ในการค้นหาจะมากขึ้นตามไปด้วย จึงมีความยากในการนำไปประยุกต์หากปรับขนาดของปัญหา - การใช้หน่วยความจำมากขึ้น: เมื่อจำนวนควีนเพิ่มขึ้น จำนวนการเรียกใช้ฟังก์ชันจะเกิดขึ้นมากขึ้น การใช้หน่วยความจำที่เกิดจาก stack จะเพิ่มขึ้นเรื่อย ๆ

 

สรุป

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

เรียนรู้เกี่ยวกับการพัฒนาโปรแกรมอย่างสนุกสนาน และพบความท้าทายใหม่ๆ ได้ที่ EPT นะคะ!

 

 

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