ปัญหาการเดินของนักม้า (Knight's Tour Problem)

บทนำ

ในหมากรุก นักม้า (Knight) เดินได้แบบพิเศษ: 2 ช่องแนวนอน + 1 ช่องแนวตั้ง หรือ 2 ช่องแนวตั้ง + 1 ช่องแนวนอน ทุกทิศทาง รูปร่างเหมือนตัวอักษร 'L'

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

อาจมีหลายคำตอบ จะหาคำตอบหนึ่งใดก็ได้

อินพุตและเอาต์พุต

Input: ขนาดกระดานหมากรุก (ปกติ 8x8)
Output: การเดินของนักม้า แต่ละช่องมีตัวเลขบอกลำดับการเดิน
 0  59 38 33 30 17  8 63
 37 34 31 60  9 62 29 16
 58  1 36 39 32 27 18  7
 35 48 41 26 61 10 15 28
 42 57  2 49 40 23  6 19
 47 50 45 54 25 20 11 14
 56 43 52  3 22 13 24  5
 51 46 55 44 53  4 21 12

อัลกอริทึม

isValid(x, y, solution)

Input: ตำแหน่ง x, y และเมทริกซ์คำตอบ
Output: True ถ้า (x,y) อยู่ในกระดานและยังไม่ถูกใช้

Begin
    if 0 ≤ x < ขนาดกระดาน AND 0 ≤ y < ขนาดกระดาน AND (x,y) ว่าง then return true
End

knightTour(x, y, move, sol, xMove, yMove)

Input: ตำแหน่ง (x,y), จำนวนการเดิน, เมทริกซ์คำตอบ, รายการการเคลื่อนที่ x และ y
Output: เมทริกซ์คำตอบที่อัปเดตแล้ว

Begin
    if move = ขนาดกระดาน² then return true  // ครบทุกช่อง
    for k := 0 ถึง 7 do
        xNext := x + xMove[k]
        yNext := y + yMove[k]
        if isValid(xNext, yNext, sol) then
            sol[xNext, yNext] := move
            if knightTour(xNext, yNext, move+1, sol, xMove, yMove) then return true
            else sol[xNext, yNext] := -1  // backtrack
    done
    return false
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <iomanip>
#define N 8
using namespace std;

int sol[N][N];

bool isValid(int x, int y, int sol[N][N]) {
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void displaySolution() {
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) cout << setw(3) << sol[x][y] << " ";
        cout << endl;
    }
}

int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
    int xNext, yNext;
    if (move == N*N) return true;
    for (int k = 0; k < 8; k++) {
        xNext = x + xMove[k];
        yNext = y + yMove[k];
        if (isValid(xNext, yNext, sol)) {
            sol[xNext][yNext] = move;
            if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true) return true;
            else sol[xNext][yNext] = -1;  // backtracking
        }
    }
    return false;
}

bool findKnightTourSol() {
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++) sol[x][y] = -1;
    int xMove[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int yMove[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    sol[0][0] = 0;  // เริ่มที่ (0,0)
    if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
        cout << "Solution does not exist";
        return false;
    } else displaySolution();
    return true;
}

int main() { findKnightTourSol(); }

ผลลัพธ์

0  59 38 33 30 17  8 63
37 34 31 60  9 62 29 16
58  1 36 39 32 27 18  7
35 48 41 26 61 10 15 28
42 57  2 49 40 23  6 19
47 50 45 54 25 20 11 14
56 43 52  3 22 13 24  5
51 46 55 44 53  4 21 12