พิชิตปัญหา Knight's Tour Problem ด้วยภาษา Java

คุณเคยได้ยินเกี่ยวกับการเดินของม้าในเกมหมากรุกไหมครับ? Knight's Tour Problem คือหนึ่งในปัญหาทางคณิตศาสตร์และทางอัลกอริทึมที่น่าสนใจและท้าทาย ที่ชวนให้นักเรียนรูปแบบการเดินของชิ้นม้า (Knight) บนกระดานหมากรุก ชิ้นม้านั้นลักษณะเฉพาะโดยจะเดินแบบ "L" หรือเป็นการเดินข้าม 2 ช่องและเลี้ยว 1 ช่องในทิศทางใดก็ตาม ปัญหานี้ก็คือการหาวิธีที่ชิ้นม้าจะสามารถเดินเยือนทุกช่องบนกระดานหมากรุก 8x8 โดยไม่ซ้ำช่องใดช่องหนึ่ง ซึ่งแต่ละขั้นตอนต้องเป็นการเดินแบบ "L" นั้นเองครับ

จะใช้ Algorithm นี้แก้ปัญหาอะไรบ้าง?

Knight's Tour Problem ไม่เพียงแต่ให้ความบันเทิงในด้านของเกมหมากรุกเท่านั้น แต่ยังสามารถนำมาประยุกต์ใช้ในงานวิจัยที่เกี่ยวเนื่องกับปัญหาทางด้านกราฟทฤษฎี สร้างระบบการนำทางที่เกี่ยวข้องกับการพยากรณ์และระบบการควบคุมเส้นทางเคลื่อนที่ (pathfinding) ในหุ่นยนต์ หรือแม้กระทั่งงานวิจัยเกี่ยวกับเครือข่ายประสาทเทียม (neural networks) เพื่อฝึกฝนและทดสอบความสามารถของระบบในการคาดการณ์และแก้ไขปัญหาทางด้านรูปแบบและลำดับความเรียงเหตุการณ์ครับ

ตัวอย่าง code ในภาษา Java:

public class KnightsTour {
    private static final int N = 8;

    // สร้างเมธอดที่จะประเมินค่าว่าการเดินถัดไปนั้นเป็นไปได้หรือไม่
    private static boolean isMovePossible(int x, int y, int[][] solution) {
        return (x >= 0 && x < N && y >= 0 && y < N && solution[x][y] == -1);
    }

    // สร้างเมธอดพิมพ์รูปแบบการเดินของม้าออกมา
    private static void printSolution(int[][] solution) {
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                System.out.print(solution[x][y] + "\t");
            }
            System.out.println();
        }
    }

    // สร้างเมธอดที่จะทำการแก้ปัญหา Knight's Tour โดยใช้ Backtracking
    private static boolean solveKT() {
        int[][] solution = new int[N][N];

        // สร้าง matrix N x N และเริ่มต้นค่าทั้งหมดด้วย -1
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                solution[x][y] = -1;
            }
        }

        // การเดินของม้ามีทิศทางดังกำหนดในข้างล่างนี้ถูกสร้างโดยใช้ xMove[] และ yMove[]
        int[] xMove = {2, 1, -1, -2, -2, -1, 1, 2};
        int[] yMove = {1, 2, 2, 1, -1, -2, -2, -1};

        // เริ่มต้นชิ้นม้าจากช่องแรกของกระดาน
        solution[0][0] = 0;

        // เริ่มต้นการหาวิธีการเดินถ้าสามารถหาวิธีได้จะ return true
        if (!solveKTUtil(0, 0, 1, solution, xMove, yMove)) {
            System.out.println("Solution does not exist");
            return false;
        } else {
            printSolution(solution);
        }
        return true;
    }

    // เมธอดสำหรับการใช้ Backtracking เพื่อหาวิธีการเดิน
    private static boolean solveKTUtil(int x, int y, int movei, int[][] solution, int[] xMove, int[] yMove) {
        int nextX, nextY;
        if (movei == N * N) {
            return true;
        }

        // ลองทุกๆทางเดินที่เป็นไปได้จากพิกัดปัจจุบัน
        for (int k = 0; k < N; k++) {
            nextX = x + xMove[k];
            nextY = y + yMove[k];
            if (isMovePossible(nextX, nextY, solution)) {
                solution[nextX][nextY] = movei;
                if (solveKTUtil(nextX, nextY, movei + 1, solution, xMove, yMove)) {
                    return true;
                } else {
                    // Backtracking: กลับมาตรวจสอบถ้าการเคลื่อนที่ไม่นำไปสู่การแก้ปัญหา
                    solution[nextX][nextY] = -1;
                }
            }
        }
        return false;
    }

    public static void main(String args[]) {
        solveKT();
    }
}

Complexity ของการแก้ปัญหานี้ ถ้าพิจารณาในเมธอด `solveKTUtil` เราสามารถเห็นได้ว่าเมธอดนี้เป็นการเรียกตัวเอง สำหรับแต่ละสถานะของกระดาน มี 8 ทางเลือกสำหรับการเคลื่อนที่ครั้งถัดไป และไทม์คอมเพล็กไซตี้สำหรับปัญหานี้ก็จะเข้าข่ายเป็น O(8^(N*N)) เนื่องจากในสถานการณ์ที่แย่ที่สุด อัลกอริทึมนี้จะต้องทดลองทุกๆ การเดินที่เป็นไปได้เพื่อหาวิธีการเดินที่สมบูรณ์

ข้อดีข้อเสียของ Algorithm นี้:

ข้อดี:

- สามารถหาวิธีการเดินที่สมบูรณ์ผ่านการลองผิดลองถูก (brute force)

- เป็นไปในลักษณะ Systematic ในการค้นหาวิธีการเดิน

ข้อเสีย:

- ไทม์คอมเพล็กไซตี้สูงมาก เนื่องจากระดับความซับซ้อนของปัญหาโดยตรง

- ไม่มีการรับประกันว่าจะพบวิธีการเดินที่สมบูรณ์ในกระดานขนาดใหญ่หรือไม่

สรุป, Knight's Tour Problem คือการศึกษาที่น่าสนใจและท้าทาย ที่ไม่เพียงแต่ให้ความรู้เกี่ยวกับการเดินหมากรุกเท่านั้น แต่ยังช่วยให้เราเข้าใจแนวคิดในการแก้ปัญหาที่ซับซ้อนผ่านอัลกอริทึมและการประยุกต์ใช้ในพื้นที่ต่างๆ ของการวิจัยและภาคปฏิบัติ ถ้าคุณพบว่าเรื่องนี้น่าสนใจและอยากท่องโลกของการเขียนโปรแกรมเพื่อแก้ปัญหาที่ซับซ้อนแบบนี้ ที่ EPT พวกเราสอนการเขียนโค้ดและทฤษฎีอัลกอริทึมอย่างลึกซึ้ง ร่วมเรียนรู้และเติบโตไปพร้อมกับเราสิครับ!

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