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.

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

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

– LỜI GIẢI CHO BÀI TOÁN TRÊN 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Ì

Đị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.

• 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 $latex A_1$ là tập tất cả các ô đen và $latex 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 $latex A_1$ và $latex B_1$.

• Xét hình minh hoạ ở trên. Gọi $latex A_2$ là tập các ô chứa chữ A, $latex 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 $latex |A_2|=|B_2|.$ Nhận xét: Từ một ô thuộc $latex A_2$, quân Mã phải nhảy tới một ô thuộc $latex B_2$, và ở một ô thuộc $latex B_2$, quân Mã phải nhảy tới một ô thuộc $latex 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 $latex A_1$∩$latex A_2$. Khi đó, ô tiếp theo nó nhảy tới là một ô thuộc $latex B_1$ ∩ $latex B_2$, ô thứ ba nó nhảy tới lại là một ô thuộc $latex A_1$ ∩ $latex A_2$,... Hành trình này không chứa các ô thuộc tập $latex A_1$ ∩ $latex B_2$ và $latex A_2$ ∩ $latex 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 $latex A_1$ ∩ $latex B_2$, $latex A_2$ ∩ $latex B_1$, $latex A_2$ ∩ $latex 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à $latex 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

• https://vi.wikipedia.org/wiki/B%C3%A0i_to%C3%A1n_m%C3%A3_%C4%91i_tu%E1%BA%A7n
• http://10tin2k11.clan.su/news/ma_di_tu_n_hay_hanh_trinh_c_a_quan_ma/2011-10-04-29
• http://diendan.congdongcviet.com/threads/t32211::bai-toan-quan-ma-di-tuan.cpp
• Đọc thêm:
• Tổng hợp cờ vua
  Một bài viết mình luôn muốn hoàn thiện, thời gian trước, mình có viết về cờ vua nhưng lúc đó rời rạc, thiếu hệ thống, thế nên rất khó...spiderum.com
•