การเดินทางของพระบุ้งหมากรุก (Knight's Tour Problem) และการเขียนโปรแกรมด้วยภาษา C++

ในโลกของการเขียนโปรแกรม ปัญหาที่ท้าทายและจำเป็นต้องใช้ความสามารถทางด้านอัลกอริธึมอย่างมากคือ "การเดินทางของพระบุ้งหมากรุก" หรือที่เรียกว่า Knight's Tour Problem ในแบบที่เป็นโจทย์คลาสสิกของโลกการเขียนโปรแกรมและแก้ปัญหาทางคณิตศาสตร์

อัลกอริธึมของการเดินทางของพระบุ้งหมากรุก (Knight's Tour Algorithm) คืออะไร?

ปัญหาการเดินทางของพระบุ้งหมากรุก กล่าวถึงลักษณะการเคลื่อนไหวของม้าในเกมหมากรุกบนกระดานหมากรุกขนาด N x N โดยม้าจำเป็นต้องเดินทั้งหมด N^2 ครั้ง (เดินมุมไปมุมมา ตามกฎการเดินของม้าในหมากรุก) โดยที่ไม่มีช่องใดถูกเดินซ้ำ ซึ่งโจทย์นี้เป็นการพิสูจน์ความเป็นไปได้ว่าม้าสามารถเดินทะลุทุกช่องบนกระดานหมากรุกได้หรือไม่

เพื่อแก้ปัญหานี้ นักพัฒนาจำเป็นต้องรู้จักกับอัลกอริธึมที่เรียกว่า "Warnsdorff's Rule" ซึ่งเป็นหลักในการตัดสินใจเลือกการเดินของม้า โดยเลือกเดินไปยังตำแหน่งที่มีตัวเลือกการเคลื่อนไหวถัดไปน้อยที่สุด เพื่อเพิ่มโอกาสให้ม้าสามารถเดินครบทุกช่องได้

ยกตัวอย่าง Code ในภาษา C++:

#include 
#include 
#define N 8

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[], int yMove[]);

/* ฟังก์ชันนี้เพื่อตรวจสอบว่า i,j คือ Index ที่ถูกต้องภายในกระดานขนาด N*N หรือไม่ */
bool isSafe(int x, int y, int sol[N][N]) {
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

/* ฟังก์ชันนี้สำหรับแสดงผลลัพธ์ของการเดินทัวร์ของม้า */
void printSolution(int sol[N][N]) {
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++)
            std::cout << std::setw(2) << sol[x][y] << " ";
        std::cout << std::endl;
    }
}

/* ฟังก์ชันนี้แก้ปัญหา Knight Tour โดยใช้การย่อยปัญหาเป็นส่วนๆ Backtracking */
int solveKT() {
    int sol[N][N];

    /* Initialization of solution matrix */
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            sol[x][y] = -1;

    /* xMove[] และ yMove[] เป็น moves ของม้าในการเดินบนกระดาน */
    int xMove[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int yMove[] = {1, 2, 2, 1, -1, -2, -2, -1};

    // จุดเริ่มต้นของม้า
    sol[0][0] = 0;

    /* เริ่มทัวร์โดยใช้ฟังก์ชัน solveKTUtil() */
    if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0) {
        std::cout << "Solution does not exist";
        return 0;
    } else
        printSolution(sol);

    return 1;
}

/* ฟังก์ชันนี้เป็นการใช้ Backtracking เพื่อแก้ปัญหา */
int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N], int yMove[N]) {
    int k, next_x, next_y;
    if (movei == N * N)
        return 1;

    /* ลองทุกการเคลื่อนที่ต่อไปของ Knight และใช้ฟังก์ชัน Recursive ในการจบทัวร์ */
    for (k = 0; k < 8; k++) {
        next_x = x + xMove[k];
        next_y = y + yMove[k];
        if (isSafe(next_x, next_y, sol)) {
            sol[next_x][next_y] = movei;
            if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1)
                return 1;
            else
                sol[next_x][next_y] = -1; // Backtracking
        }
    }
    return 0;
}

// Main Function
int main() {
    solveKT();
    return 0;
}

Usecase ในโลกจริง:

ปัญหาการเดินทางของพระบุ้งหมากรุกไม่เพียงแค่เป็นปัญหาทางคณิตศาสตร์ที่ท้าทายเท่านั้น แต่ยังสามารถประยุกต์ใช้เพื่อการศึกษาลักษณะต่างๆ ของกราฟไซคลิกหรือเพื่อแก้ปัญหาทางวิศวกรรมเช่นการวางแผนเส้นทางในหุ่นยนต์หรือการวิเคราะห์เส้นทางเครือข่าย

ความซับซ้อน (Complexity) และข้อดีข้อเสีย:

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

ข้อดีคือ Knight's Tour Algorithm ช่วยให้ฝึกคิดวิเคราะห์และพัฒนาทักษะการแก้ปัญหาแบบตรรกะได้เป็นอย่างดี

ข้อเสียคือ อาจไม่เหมาะกับกรณีที่ต้องการความรวดเร็วในคำนวณหรือมีข้อจำกัดทางด้านทรัพยากรคอมพิวเตอร์เนื่องจากความซับซ้อนที่สูง

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

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