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.

I – MỞ ĐẦU

1. Nước đi của quân Mã (♘) trên bàn cờ

Hình 1: Vị trí xuất phát của quân Mã trên bàn cờ
  • 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.
Hình 2: Nước đi của quân Mã
  • 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.
Hình 3: “Mã ở rìa cũng giống như đồ trang trí

2. 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ã.

II – LỜI GIẢI CHO BÀI TOÁN TRÊN BÀN CỜ 8 x 8

Có rất nhiều lời giải cho bài toán này trên bàn cờ vua tiêu chuẩn 8 x 8, cụ thể là đến nay đã có 26.534.728.821.064 (bạn có thể đọc được con số này không?) lời giải trong đó quân Mã có thể kết thúc tại chính ô mà nó khởi đầu. Một hành trình như vậy của quân Mã được gọi là một hành trình đóng, còn một hành trình mà quân Mã đi qua tất cả các ô, mỗi ô một lần nhưng không thể quay về ô ban đầu của nó chỉ bằng một nước đi được gọi là một hành trình mở. Dưới đây là một lời giải cho bàn cờ 8 x 8.



Hình 4: Một lời giải cho bài toán Quân Mã đi tuần trên bàn cờ 8 x 8

III – MỞ RỘNG BÀI TOÁN CHO BÀN CỜ m x n BẤT KÌ

Câu hỏi đặt ra là, với cặp số (m; n) nào thì quân Mã có thể có một hành trình đóng đi qua tất cả các ô trên bàn cờ? Định lí Schwenk sau đây cho chúng ta lời giải cho câu hỏi đó.

Định lí Schwenk: Cho bàn cờ m × n bất kỳ với m ≤ n. Không có hành trình đóng nào của quân mã nếu một trong ba điều kiện dưới đây xảy ra:

  1. m và n đều lẻ.
  2. m = 1, 2, hoặc 4; n khác 1.
  3. m = 3 và n = 4, 6 hoặc 8.

Chứng minh: Ta sẽ chứng minh từng điều kiện một.

Điều kiện 1: Trên bàn cờ vua, các ô đen và trắng xen kẽ nhau, một quân mã luôn đi từ một ô tới ô khác màu. Vì m và n đều là lẻ nên khi đó số các ô đen và trắng trên bàn cờ là khác nhau. Một đường đi đóng của quân mã phải có số ô đen và trắng bằng nhau, tổng số ô trên mọi hành trình đóng là số chẵn. Do đó một hành trình đóng không thể đi qua mỗi ô đúng một lần khi số các ô trên bàn cờ là số lẻ.

Điều kiện 2:

  • Dễ thấy rằng khi m = 1 hoặc 2 không thể có hành trình của quân mã: quân mã không thể đi qua mọi ô.
  • Giả sử một bàn cờ kích thước 4 × n có một hành trình đóng của quân mã. Xét A_1 là tập tất cả các ô đen và B_1 là tập tất cả các ô trắng trên bàn cờ. Theo luật cờ, quân Mã luôn di chuyển liên tiếp giữa các phần tử thuộc A_1 và B_1.

Capture.PNG

  • Xét hình minh hoạ ở trên. Gọi A_2 là tập các ô chứa chữ A, B_2 là tập các ô chứa chữ B. Trên bảng vuông 4 x n, số ô chứa chữ A và chữ B là bằng nhau, vậy nên |A_2|=|B_2|. Nhận xét: Từ một ô thuộc A_2, quân Mã phải nhảy tới một ô thuộc B_2, và ở một ô thuộc B_2, quân Mã phải nhảy tới một ô thuộc A_2. Giả sử trong hành trình đóng của quân Mã, ô xuất phát của nó là một ô thuộc A_1∩A_2. Khi đó, ô tiếp theo nó nhảy tới là một ô thuộc B_1 ∩ B_2, ô thứ ba nó nhảy tới lại là một ô thuộc A_1 ∩ A_2,… Hành trình này không chứa các ô thuộc tập A_1 ∩ B_2 và A_2 ∩ B_1, do đó không thể chứa tất cả các ô trên bàn cờ. Chứng minh tương tự cho các trường hợp ô xuất phát của quân Mã thuộc A_1 ∩ B_2, A_2 ∩ B_1, A_2 ∩ B_2. Như vậy, với bảng vuông 4 x n, không có một hành trình đóng của quân Mã.

IV – 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).

TƯ LIỆU THAM KHẢO