Bài toán Du hành của Mã (Knight's Tour)

Giới thiệu

Trong cờ vua, mã di chuyển theo hình chữ L: 2 ô ngang + 1 ô dọc hoặc 2 ô dọc + 1 ô ngang.

Bài toán: bàn cờ trống, mã bắt đầu từ ô bất kỳ. Kiểm tra mã có thể đi qua tất cả ô đúng 1 lần không. Nếu có, ghi số bước đến mỗi ô.

Có thể có nhiều lời giải, tìm một lời giải nào đó.

Đầu vào và Đầu ra

Đầu vào: Kích thước bàn cờ (thường 8x8)
Đầu ra: Các nước đi của mã. Mỗi ô chứa số thứ tự bước đi.
 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

Thuật toán

isValid(x, y, solution)

Đầu vào: Tọa độ x, y và ma trận lời giải.

Đầu ra: True nếu (x,y) trong bàn cờ và chưa gán giá trị.

Begin
  nếu 0 ≤ x < N VÀ 0 ≤ y < N VÀ (x,y) trống thì trả về true
End

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

Đầu vào: Vị trí (x,y), số bước, ma trận lời giải, mảng các nước đi khả thi.

Đầu ra: Ma trận lời giải cập nhật nếu tồn tại.

Begin
  nếu move = N*N thì return true  // đã đi hết bàn cờ
  với k := 0 đến số nước đi khả thi làm:
    xNext := x + xMove[k], yNext := y + yMove[k]
    nếu isValid(xNext, yNext, sol) thì
      sol[xNext][yNext] := move
      nếu knightTour(xNext, yNext, move+1, sol, xMove, yMove) thì return true
      ngược lại xóa move khỏi sol[xNext][yNext] (backtrack)
  done
  return false
End

Ví dụ (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)) return true;
      sol[xNext][yNext] = -1;  // backtrack
    }
  }
  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;  // bắt đầu từ (0,0)
  if (!knightTour(0, 0, 1, sol, xMove, yMove)) {
    cout << "Solution does not exist";
    return false;
  }
  displaySolution();
  return true;
}

int main() { findKnightTourSol(); }

Kết quả đầu ra

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