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ở.^[1]^[2]

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.^[3] 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

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.^[4]

Đị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à:^[5]

Với bàn cờ vua cỡ $m\times n,m\leq n$ , 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:

$m$ và $n$ đều là số lẻ.
$m=1,m=2,m=4$
$m=3$ và $n=4,n=6,n=8$

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

Điều kiện cần

Phần này chứng minh rằng tại sao trên bàn cờ thỏa mãn một trong ba điều trên lại không tồn tại đường Mã đi tuần.

Khi m và n đều là số lẻ, khi ấy số ô có màu đen trên bàn cờ hoặc số ô có màu trắng trên bàn cờ, một trong hai số phải là số lẻ và số còn lại là số chẵn. Do quân Mã đi từ ô trắng phải sang ô đen (và ngược lại, nếu đang đứng ở ô đen thì phải sang ô trắng), nên nếu bàn cờ cỡ m x n này mà tồn tại chu trình Hamilton thì chu trình đó phải có hai màu xen kẽ, từ ấy số ô màu trắng và số ô màu đen phải bằng nhau, điều này là vô lý.
Trường hợp m = 1, m = 2 thì bàn cờ khi này không đủ rộng để quân Mã có thể đi, nên hiển nhiên không tồn tại đường Mã đi tuần.
Đối với trường hợp m = 4, giả sử rằng bàn cờ có 4 hàng này có một đường Mã đi tuần. Bằng việc tạm "tô màu" hàng một và hàng 4 là màu xanh, hàng hai và hàng ba là màu đỏ, khi ấy có các nhận xét sau.
- Các ô màu xanh chỉ "kề" với các ô màu đỏ (với kề ở đây theo nghĩa, hai ô trên bàn cờ là kề nhau nếu quân Mã có thể đi từ ô này sang ô kia)
- Do mỗi màu xanh và đỏ có 2n đỉnh, nên chu trình Hamilton nếu có trên bàn cờ này sẽ có các ô kề nhau khác màu nhau (ví dụ, xanh - đỏ - xanh - đỏ - ...)
- Bằng lập luận tương tự trường hợp m và n đều lẻ, khi ấy thấy rằng các ô trắng và ô đen cũng phải xen kẽ nhau như vậy, từ ấy suy ra rằng các ô màu xanh và các ô màu đỏ chỉ có đúng một màu trắng hoặc đen trên bàn cờ, điều này là vô lý.
- Tương tự lập luận này, bàn cờ có cỡ 3 x 4 cũng không có đường Mã đi tuần.
Để chứng minh rằng bàn cờ cỡ 3 x 6 và 3 x 8 không có đường Mã đi tuần, tính chất sau được sử dụng: " Đối với đồ thị G có một chu trình Hamilton, nếu ta xóa đi k đỉnh (và các cạnh nối với các đỉnh đó) thì phần còn lại tạo nên tối đa k thành phần liên thông "

Điều kiện đủ

Phần này để chỉ ra rằng nếu loại bỏ các bàn cờ có kích cỡ như trên, thì đường Mã đi tuần sẽ tồn tại trên bàn cờ. Sơ đồ chứng minh của Schwenk đưa ra gồm các bước như sau.

Chỉ ra rằng nếu trên bàn cờ cỡ m x n tồn tại đường Mã đi tuần, thì bàn cờ cỡ m x (n+4) và (m+4) x n cũng tồn tại đường Mã đi tuần. Schwenk chỉ ra việc này bằng cách chứng minh rằng, nếu đường Mã đi tuần trên bàn cờ cỡ m x n tồn tại một số cạnh nhất định, thì trên bàn cờ cỡ m x (n+4) và (m+4) x n cũng sẽ tồn tại các cạnh đó (nhưng được "tịnh tiến" đi vài cột, vài hàng)
Sau đó, bằng việc chỉ ra một chu trình Hamilton trên các bàn cờ "cơ sở" là 5 x 6, 6 x 6, 7 x 6, 5 x 8, 6 x 8, 7 x 8, 8 x 8, 3 x 10 và 3 x 12, chứng minh được hoàn thành bằng giả thiết quy nạp.

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

Xem thêm

Tham khảo

Chú thích

↑ Brown, Alfred James (2017). Knight's Tours and Zeta Functions (MS thesis). San José State University. tr. 3. doi:10.31979/etd.e7ra-46ny.
↑ Hooper, David; Whyld, Kenneth (1996) [First pub. 1992]. "knight's tour". The Oxford Companion to Chess (ấn bản thứ 2). Oxford University Press. tr. 204. ISBN 0-19-280049-3.
↑ Deitel, H. M.; Deitel, P. J. (2003). Java How To Program Fifth Edition (ấn bản thứ 5). Prentice Hall. tr. 326–328. ISBN 978-0131016217.
↑ Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q.
↑ Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight's Tour?" (PDF). Mathematics Magazine. 64 (5): 325–332. doi:10.1080/0025570X.1991.11977627. S2CID 28726833. Bản gốc (PDF) lưu trữ ngày 26 tháng 5 năm 2019.

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 Lưu trữ ngày 6 tháng 8 năm 2004 tại Wayback Machine
The knight's tour Lưu trữ ngày 29 tháng 6 năm 2018 tại Wayback Machine
Knight's tour notes
A Simple backtracking implementation in C++ Lưu trữ ngày 14 tháng 11 năm 2013 tại Wayback Machine
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

[1] Brown, Alfred James (2017). Knight's Tours and Zeta Functions (MS thesis). San José State University. tr. 3. doi:10.31979/etd.e7ra-46ny.

[2] Hooper, David; Whyld, Kenneth (1996) [First pub. 1992]. "knight's tour". The Oxford Companion to Chess (ấn bản thứ 2). Oxford University Press. tr. 204. ISBN 0-19-280049-3.

[3] Deitel, H. M.; Deitel, P. J. (2003). Java How To Program Fifth Edition (ấn bản thứ 5). Prentice Hall. tr. 326–328. ISBN 978-0131016217.

[Conrad1994-4] Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q.

[5] Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight's Tour?" (PDF). Mathematics Magazine. 64 (5): 325–332. doi:10.1080/0025570X.1991.11977627. S2CID 28726833. Bản gốc (PDF) lưu trữ ngày 26 tháng 5 năm 2019.

[1]

[2]

[3]

[4]

[5]