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

phải|nhỏ|220px|Lời giải bài toán trên bàn cờ 5 x 5.
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 
Nhà toán học Allen J. Schwenk đã đưa ra điều kiện cần và đủ để một bàn cờ vua hình chữ nhật (mà không bị "thủng" ô cờ nào) có lời giải cho bài toán Mã đi tuần (đóng) là: Với bàn cờ vua cỡ , bàn cờ ấy tồn tại đường Mã đi tuần nếu và chỉ nếu một trong ba trường hợp sau không xảy ra: 

  và  đều là số lẻ.

  và Phần chứng minh dưới đây tóm tắt lại cách chứng minh định lí như sau.

 Hai lời giải với bàn cờ 8 x 8
nhỏ|giữa|500px|Hai trong số nhiều hành trình đóng trên 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

Thể loại:Cờ vua và toán học
Thể loại:Lý thuyết đồ thị
Mã đi tuần
Thể loại:Giải thuật lý thuyết đồ thị