Bài toán mã đi tuần

Bài toán mã đi tuần (Tiếng Anh: Knight's tour) là bài toán về việc đi tìm dãy nước đi cho 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. Nếu quân mã dừng lại ở ô khởi đầu thì đường đi của quân mã gọi là đóng, nếu không thì ta gọi là mở.

Bài toán mã đi tuần thường được sử dụng làm bài tập xây dựng chương trình giải cho sinh viên ngành khoa học máy tính. Bài toán này cũng có nhiều biến thể bằng việc thay đổi kích cỡ bàn cờ 8 x 8 quen thuộc thành các kích cỡ khác, thậm chí bàn cờ không còn có hình chữ nhật nữa.

Lý thuyết giải
trái|nhỏ|270x270px|Đồ thị mã đi tuần biểu diễn tất cả các chu trình mã đi tuần có thể trên [[bàn cờ vua 8x8 tiêu chuẩn. Con số trên mỗi đỉnh thể hiện số nước đi có thể thực hiện khi quân mã đứng ở ô đó trên bàn cờ.]]

Bài toán mã đi tuần là trường hợp cụ thể của đường đi Hamilton trong lý thuyết đồ thị. Khi đường đi của quân mã là đóng, nó trở thành chu trình Hamilton. Tuy nhiên, không giống với bài toán chu trình Hamilton tổng quát thì bài toán mã đi tuần có thể được giải với thời gian tuyến tính.

Định lý Schwenk
Cho bàn cờ m&nbsp;&times;&nbsp;n bất kỳ với m nhỏ hơn hoặc bằng 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:

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

Điều kiện 1
Dễ dàng chứng minh rằng khi điều kiện 1 thỏa mãn, không thể có hành trình đóng của quân mã.

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. Chẳng hạn bàn cờ 5&times;5 có 13 ô đen và 12 ô trắng.

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
Điều kiện 2 xảy ra khi độ dài cạnh ngắn là 1, 2, hoặc 4, cũng không thể có đường đi đóng.

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 ô (trừ trường hợp bàn cờ 1x1).

Cũng có thể thấy rằng bàn cờ 4 &times; n không có hành trình đóng của quân mã.

Giả sử một bàn cờ kích thước 4 &times; n có một hành trình đóng của quân mã. Ta xét hai tập con các ô trên bàn cờ, A_1 và B_1 , A_1 gồm các ô thuộc nửa màu đen và B_1 gồm các ô màu trắng. Theo quy tắc cờ vua quân mã luôn di chuyến liên tiếp giữa hai tập các ô đen và tập các ô trắng và ngược lại ( A_1 và B_1 ).

.
Ta lại xét hình minh họa bên phải. Ta định nghĩa A_2 là tập các ô màu xanh lá cây và B_2 là tập các ô màu đỏ trên hình vẽ. Các tập này có số ô bằng nhau. Chú y rằng từ một ô trong A_2 quân mã chỉ có thể nhảy sang một ô trong B_2 . Ngoài ra, vì quân mã phải đi qua tất cả các ô, nên ngược lại khi quân mã đứng ở một ô trong B_2 ở bước tiếp theo nó phải nhảy về một ô thuộc A_2 (nếu không như vậy số thì trên hành trình kín ấy quân mã phải có hai ô liên tiếp trong A_2 điều đó không xảy ra).

Ta sẽ tìm thấy mâu thuẫn trong lập luận sau đây.

Vì có một hành trình đóng của quân mã, nên có thể chọn bất kỳ ô nào làm ô thứ nhất của hành trình
Chọn ô thứ nhất thuộc tập A_1 \cap A_2 .
Khi đó ô thứ hai phải thuộc B_1 \cap B_2 .
Ô thứ ba thuộc tập A_1 \cap A_2 .
Ô thứ tư thuộc tập B_1 \cap B_2 .
...

Như thế hành trình này không chưa các ô thuộc A_1 \cap B_2 và B_1 \cap A_2 do đó không thể chứa tất cả các ô trên bàn cờ..

Điều kiện 3
Điều kiện 3 được chứng minh cho từng trường hợp.
Tuy nhiên, chúng vẫn có thể có lời giải với hành trình mở.
Chẳng hạn với bàn cờ 3 x 4 ta có 4 hành trình mở sau:

Hai lời giải với bàn cờ 8 x 8

Xem thêm
Bài toán tám quân hậu
Mã (cờ vua)

Tham khảo
;Chú thích

;Nguồn

Watkins, John J. Across the Board: the Mathematics of Chessboard Problems. Princeton UP, 2004.

Liên kết ngoài

The ultimate Knight's Tour page of Links
The knight's tour
Knight's tour notes
A Simple backtracking implementation in C++
Number of knight's tours on a 2n X 2n chessboard Sloane's Integer Sequence A001230
8 by 8 Knight's Tour strategy
Playable 8 by 8 Knight's Tour