Bài toán quân mã đi tuần và những điều thú vị ẩn sau nó

Mã đi tuần (hay hành trình của quân mã) là bài toán về việc di chuyển một quân mã trên bàn cờ vua (8 x 8). Quân mã được đặt ở một ô trên một bàn cờ trống nó phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần. Trong bài này, chúng tôi xin giới thiệu về bài toán thú vị này và những điều có thể khai thác được qua bài toán.

  • Trong cờ vua, quân Mã là quân có cách đi phức tạp nhất. Xét một quân Mã đang đứng trên bàn cờ và tất cả các hình chữ nhật 2 x 3 nhận ô mà quân Mã đó đang đứng làm đỉnh. Quân Mã đó có thể đi tới các đỉnh khác màu với đỉnh nó đang đứng của bất kì hình chữ nhật 2 x 3 nào, miễn là đỉnh đó không nằm ngay cạnh đỉnh nó đang đứng.
  • Quân Mã có thể nhảy qua tất cả các quân khác để đến ô nó muốn, miễn là ô đó chưa bị ai chiếm giữ. Nói nôm na là quân Mã không bị cản. Khác với cờ tướng, nơi mà quân Mã có thể bị cản nếu có quân nào đứng ngay trước mặt nó, trong cờ vua, nước đi của quân Mã không có tính chất này.
  • Khi một quân Mã đứng ở cạnh bàn cờ, số nước đi có thể của nó sẽ bị thu hẹp xuống còn nhiều nhất là một nửa số nước đi ban đầu. Đặc biệt, nếu nó đứng ở một trong bốn góc bàn cờ, nó chỉ đi được tối đa hai nước. Câu nói “Mã ở rìa cũng giống như đồ trang trí” từ đây mà ra.

 

Xuất xứ bài toán

Bài toán quân Mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm đường đi Hamilton trong l‎ý thuyết đồ thị, là một bài toán NP-đầy đủ. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm chu trình hamiltonian.

Nhiều biến thể của chủ đề này được các nhà toán học nghiên cứu, trong đó có nhà toán học Euler. Các biến đổi có thể theo các hướng:

Thay đổi kích thước bàn cờ.

Biến thành trò chơi hai người theo tư tưởng này.

Giảm nhẹ các yêu cầu trên đường đi của quân Mã.

BÀI TOÁN QUÂN MÃ ĐI TUẦN TRONG TIN HỌC

1. Ý tưởng cơ bản

Dùng thuật toán quay lui; xuất phát từ 1 ô, gọi số nước đi là  t=1 , ta cho quân mã thử đi tiếp 1 ô (có 8 nước đi có thể), nếu ô đi tiếp này chưa đi qua thì chọn làm bước đi tiếp theo. Tại mỗi nước đi kiểm tra xem tổng số nước đi bằng n x n chưa, nếu bằng thì mã đã đi qua tất cả các ô ⇒ dừng (do chỉ cần tìm một giải pháp). Trường hợp ngược lại, gọi đệ quy để chọn nước đi tiếp theo. Ngoài ra, nếu tại một bước tìm đường đi, nếu không tìm được đường đi tiếp thì thuật toán sẽ quay lui lại nước đi trước và tìm đường đi khác.

2. Cấu trúc dữ liệu

  • Mảng board[MAX][MAX]: lưu bàn cờ, trong đó board[i][j] là ô (i, j); giá trị của board[i][j] là 0 khi quân mã chưa đi qua, và >0 khi quân mã đã đi qua, giá trị board[i][j] lúc này chính là thứ tự nước đi trên hành trình.
  • Mảng dr[8], dc[8]: lưu các độ dời của bước đi kế tiếp, có tám nước đi có thể cho vị trí quân mã hiện tại. Do đó để đi nước thứ i ta chỉ cần cộng thêm dr[i] cho dòng và dc[i] cho cột.
    dr[] = {-2, -2, -1, -1,  1, 1,  2, 2} dc[] = {-1,  1, -2,  2, -2, 2, -1, 1}

3. Thuật giải đệ quy

  • Tại mỗi bước lần lượt cho quân mã thử tất cả các nước đi kế tiếp (tám nước đi kế tiếp). Với mỗi bước đi, kiểm tra xem nếu nước đi hợp lệ (chưa đi qua và ở trong bàn cờ) thì thử đi nước này. Nếu quân mã đã đi qua hết bàn cờ thì xuất kết quả. Ngược lại thì gọi đệ quy tiếp cho vị trí mới thử trên. Lưu ý là mỗi khi vị trí đã đi qua được đánh dấu chính bằng chính thứ tự nước đi trên bàn cờ. Sau khi không thử vị trí này thì phải bỏ đánh dấu để chọn giải pháp khác (trường hợp quay lui).
  • Nếu coi các ô của bàn cờ là các đỉnh của đồ thị và các cạnh là nối giữa hai đỉnh tương ứng với hai ô mã giao chân thì dễ thấy rằng hành trình của quân mã cần tìm sẽ là một đường đi Hamilton. Ta có thể xây dựng hành trình bằng thuật toán quay lui kết hợp với phương pháp duyệt ưu tiên Warnsdorff: Nếu gọi deg(x, y) là số ô kề với ô (x, y) và chưa đi qua (kề ở đây theo nghĩa đỉnh kề chứ không phải là ô kề cạnh) thì từ một ô ta sẽ không thử xét lần lượt các hướng đi có thể, mà ta sẽ ưu tiên thử hướng đi tới ô có deg nhỏ nhất trước. Trong trường hợp có tồn tại đường đi, phương pháp này hoạt động với tốc độ tuyệt vời: Với mọi n chẵn trong khoảng từ 6 tới 18, với mọi vị trí ô xuất phát, trung bình thời gian tính từ lúc bắt đầu tới lúc tìm ra một nghiệm < 1 giây. Tuy nhiên trong trường hợp n lẻ, có lúc không tồn tại đường đi, do phải duyệt hết mọi khả năng nên thời gian thực thi lại hết sức tồi tệ. (Có xét ưu tiên như trên hay xét thứ tự như trước kia thì cũng vậy thôi).