8 Queens Problem: การแก้ปัญหาหญิงทั้ง 8 ในเกมหมากรุกด้วยภาษา Objective-C

 

 

บทนำ

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

 

8 Queens Problem คืออะไร?

8 Queens Problem เป็นปัญหาที่สำรวจวิธีการวางราชินี 8 ตัวบนกระดานหมากรุกขนาด 8x8 โดยที่ราชินีแต่ละตัวจะไม่ทำให้ราชินีตัวอื่นๆ อยู่ในตำแหน่งที่สามารถโจมตีได้ ซึ่งราชินี (Queen) ในเกมหมากรุกสามารถเดินได้ทั้งแนวตั้ง แนวนอน และแนวทแยงในทุกทิศทาง นี่จึงทำให้วิธีการวางราชินีเหมือนกับการจัดการปัญหา “Constraint Satisfaction Problem”

 

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

แนวทางที่นิยมใช้ในการแก้ปัญหา 8 Queens Problem คือ “Backtracking Algorithm” โดย Initial State จะเริ่มจากตารางที่ว่างเปล่าและเรียงราชินีลงในแต่ละแถวและคอลัมน์ จนกว่าจะสามารถวางได้ครบสิบแปดตัวโดยไม่ให้เกิดการชนกัน ต่อไปนี้เป็นโค้ดในภาษา Objective-C ที่สามารถใช้ในการแก้ปัญหานี้:

 #import <Foundation/Foundation.h>

#define N 8 // ขนาดของกระดาน

// ฟังก์ชั่นเพื่อตรวจสอบว่าราชินีไม่ทำให้เกิดการชนกันหรือไม่
BOOL isSafe(int board[N][N], int row, int col) {
    int i, j;

    // ตรวจสอบคอลัมน์
    for (i = 0; i < row; i++)
        if (board[i][col])
            return NO;

    // ตรวจสอบแนวทแยงซ้าย
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return NO;

    // ตรวจสอบแนวทแยงขวา
    for (i = row, j = col; i >= 0 && j < N; i--, j++)
        if (board[i][j])
            return NO;

    return YES;
}

// ฟังก์ชั่นหลักสำหรับการหาวิธีการวางราชินี
BOOL solveNQueensUtil(int board[N][N], int row) {
    if (row >= N)
        return YES;

    for (int i = 0; i < N; i++) {
        if (isSafe(board, row, i)) {
            board[row][i] = 1; // วางราชินีที่ (row, i)

            if (solveNQueensUtil(board, row + 1))
                return YES;

            board[row][i] = 0; // ยกเลิกการวางราชินี
        }
    }

    return NO;
}

// ฟังก์ชั่นที่จะเริ่มการหาวิธีการวางราชินี
void solveNQueens() {
    int board[N][N];
    memset(board, 0, sizeof(board)); // เริ่มต้นกระดานเป็นว่างเปล่า

    if (solveNQueensUtil(board, 0)) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                printf("%d ", board[i][j]);
            printf("\n");
        }
    } else {
        printf("ไม่สามารถวางราชินี 8 ตัวได้!\n");
    }
}

int main() {
    solveNQueens();
    return 0;
}

 

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

โค้ดด้านบนใช้ "Backtracking Algorithm" เพื่อแก้ไข 8 Queens Problem โดยมีฟังก์ชั่นหลักคือ `solveNQueensUtil` ที่ทำหน้าที่ค้นหาวิธีการวางราชินีในแต่ละแถว

1. isSafe: ฟังก์ชั่นนี้จะตรวจสอบว่าการวางราชินีที่ตำแหน่งที่กำหนดปลอดภัยหรือไม่ (ไม่มีราชินีตัวอื่นอยู่ในแนวโจมตี) 2. solveNQueensUtil: ฟังก์ชั่นนี้จะทำให้เรา recursively วางราชินีในกระดาน โดยหากพบว่าตำแหน่งใดไม่ปลอดภัย จะกลับไปที่ตำแหน่งก่อนหน้าเพื่อหาตำแหน่งใหม่ 3. solveNQueens: ฟังก์ชั่นนี้จะเริ่มกระบวนการและแสดงผลลัพธ์เมื่อหารูปแบบของการวางราชินีที่ถูกต้องได้

 

Use Case ในชีวิตจริง

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

 

Complexity Analysis

- Time Complexity: ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดคือ O(N!) เนื่องจากต้องเช็คตำแหน่งทั้งหมดในตารางในแต่ละแถว โดยจะต้องพยายามวางราชินีในตารางทั้งหมดถึง N แถว - Space Complexity: ความซับซ้อนของพื้นที่คือ O(N) เนื่องจากจะต้องใช้พื้นที่ใน stack recursion สำหรับการเรียกใช้งานฟังก์ชั่นที่ซ้อนกัน

 

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

ข้อดี

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

ข้อเสีย

- ไม่เหมาะกับข้อมูลขนาดใหญ่: เนื่องจาก Time Complexity สูงอาจทำให้ไม่สามารถทำงานได้อย่างมีประสิทธิภาพเมื่อปัญหามีขนาดใหญ่ขึ้น - การหาทางเลือกที่ดีที่สุด: Backtracking อาจไม่สามารถให้ทางเลือกที่ดีที่สุดเสมอไป ซึ่งอาจทำให้การตัดสินใจไม่แม่นยำ

 

สรุป

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

หากคุณต้องการเรียนรู้การเขียนโปรแกรมเพิ่มเติม ร่วมเป็นส่วนหนึ่งของ EPT วันนี้!

 

 

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