ปัญหาของราชินี 8 ตัว (8 Queens Problem) และการแก้ปัญหาด้วยภาษา Swift

 

 

ความรู้เบื้องต้นเกี่ยวกับ 8 Queens Problem

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

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

 

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

เราสามารถใช้ Recursive Backtracking ในการแก้ปัญหา 8 Queens การทำงานของอัลกอริธึมนี้คือ

1. เริ่มจากวางราชินีตัวแรกในแถวแรก

2. ตรวจสอบว่ามีตำแหน่งที่เป็นไปได้สำหรับราชินีในแถวถัดไปหรือไม่

3. หากพบ ให้ดำเนินการวางราชินีต่อไปในแถวถัดไป

4. หากไม่สามารถวางได้ให้ย้อนกลับไปเพื่อทำการวางราชินีในตำแหน่งถัดไปที่เป็นไปได้

5. ทำซ้ำขั้นตอนนี้จนกว่าจะวางราชินีครบทั้ง 8 ตัวหรือไม่สามารถวางได้จริงๆ

ตัวอย่างโค้ดในภาษา Swift

 import Foundation

var board = Array(repeating: Array(repeating: false, count: 8), count: 8)

func isSafe(row: Int, col: Int) -> Bool {
    // ตรวจสอบแนวตั้ง
    for i in 0..<row {
        if board[i][col] {
            return false
        }
    }

    // ตรวจสอบแนวทะแยงซ้าย
    for i in stride(from: row, through: 0, by: -1) {
        let j = col - (row - i)
        if j >= 0, board[i][j] {
            return false
        }
    }

    // ตรวจสอบแนวทะแยงขวา
    for i in stride(from: row, through: 0, by: -1) {
        let j = col + (row - i)
        if j < 8, board[i][j] {
            return false
        }
    }

    return true
}

func solveQueens(row: Int) -> Bool {
    if row == 8 {
        printBoard()
        return true
    }

    for col in 0..<8 {
        if isSafe(row: row, col: col) {
            board[row][col] = true
            if solveQueens(row: row + 1) {
                return true
            }
            board[row][col] = false // Backtrack
        }
    }

    return false
}

func printBoard() {
    for i in 0..<8 {
        for j in 0..<8 {
            print(board[i][j] ? "Q" : ".", terminator: " ")
        }
        print()
    }
    print("\n")
}

solveQueens(row: 0)

การทำความเข้าใจติดตั้งโค้ด

1. `isSafe(row:col:)` ฟังก์ชันนี้ใช้ในการตรวจสอบถ้าวางราชินีในตำแหน่งนั้น ณ แถวและคอลัมน์ที่ระบุ

2. `solveQueens(row:)` ใช้ในการหาตำแหน่งว่าวางราชินีที่แถวที่กำหนด

3. `printBoard()` แสดงสถานะของกระดานหมากรุก

 

Use Cases ในโลกจริง

แม้ว่า 8 Queens Problem จะเป็นปัญหาเชิงทฤษฎีในหมากรุก แต่แนวทางของมันยังสามารถนำไปประยุกต์ใช้งานในด้านต่าง ๆ ได้ เช่น:

1. การวางแผนของเส้นทาง - สามารถนำไปปรับใช้ในปัญหาการจัดการพนักงานในชุดงานที่แตกต่างกัน 2. การจัดการความต้องการของทรัพยากร - ใช้ในการวางแผนทั้งในด้านการผลิตและการจัดการสต็อกสินค้า 3. การออกแบบฐานข้อมูล - ช่วยในการจัดระเบียบสูตรในฐานข้อมูลที่ไม่ทำให้เกิดการซ้ำซ้อน

 

Complexity Analysis

- Time Complexity: ในกรณีที่เลวร้ายที่สุดสำหรับ 8 Queens Problem คือ O(N!) ซึ่งเป็นค่าใช้จ่ายในการวนลูปค้นหาทุกสถานภาพ - Space Complexity: O(N) ซึ่งขึ้นอยู่กับระดับของการเรียกซ้ำ (Recursive Call Stack)

 

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

ข้อดี

1. ใช้งานง่าย: สามารถเขียนโค้ดได้ง่ายดาย 2. สามารถแก้ไขได้เร็ว: สำหรับกรณีที่มีขนาดไม่ใหญ่มาก เช่น 8 Queens 3. เป็นแนวทางการเรียนรู้: ผู้เรียนสามารถเข้าใจแนวทางในเชิงโปรแกรมได้ง่าย

ข้อเสีย

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

 

เชิญร่วมเรียนรู้ที่ EPT

ก้าวเข้าสู่โลกของการเขียนโปรแกรมที่ EPT เพื่อเรียนรู้เกี่ยวกับการแก้ปัญหาที่ซับซ้อนมากขึ้นรวมถึงการเขียนโค้ดที่ประหยัดเวลาและทรัพยากร ไม่ว่าจะเป็นในด้านการพัฒนาเกม การออกแบบระบบ หรือการใช้งานเชิงเชิงลึก มาเป็นตัวของคุณในโลกของเทคโนโลยีและการเขียนโปรแกรมที่ EPT!

นี่คือโอกาสในการพัฒนาทักษะและความสามารถของคุณในโลกที่เปลี่ยนแปลงอย่างรวดเร็วแห่งนี้!

 

 

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