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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Một hành trình của quân mã trên bàn cờ
Lời giải bài toán trên bàn cờ 5x5.

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

Có rất nhiều lời giải cho bài toán này, chính xác là 26.534.728.821.064 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 gọi là hành trình đóng. Có những hành trình, trong đó quân mã sau khi đi hết tất cả 64 ô của bàn cờ (kể cả ô xuất phát), thì từ ô cuối của hành trình không thể đi về ô xuất phát chỉ bằng một nước đi. Những hành trình như vậy được gọi là hành trình mở.

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

Bài toá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. [1]

Hành trình của quân mã trên nửa bàn cờ đã được giới thiệu dưới dạng thơ trong một tác phẩm tiếng Phạn [2].

Giải thuật đầu tiên đầy đủ cho bài toán về hành trình của quân mã là Giải thuật Warnsdorff, công bố lần đầu năm 1823 bởi H. C. Warnsdorff.

Định lý Schwenk[sửa | sửa mã nguồn]

Cho bàn cờ m × 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:

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

Điều kiện 1[sửa | sửa mã nguồn]

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.

mn đề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×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[sửa | sửa mã nguồn]

Đ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 × 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 × 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  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  B_1 ).

Con mã phải đi xen kẽ giữa màu xanh và màu đỏ.

. Ta lại xét hình minh họa bên phải. Ta định nghiã  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

  1. Chọn ô thứ nhất thuộc tập  A_1 \cap  A_2 .
  2. Khi đó ô thứ hai phải thuộc  B_1 \cap  B_2 .
  3. ô thứ ba thuộc tập  A_1 \cap  A_2 .
  4. ô thứ tư thuộc tập  B_1 \cap  B_2 .
  5. ...

Như thế hành trình này không chưa các ô thuộc  A_1 \cap  B_2  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[sửa | sửa mã nguồn]

Đ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:

Các hành trình mở của quân mã trên bàn cờ 3 x 4.

Hai lời giải với bàn cờ 8 x 8[sửa | sửa mã nguồn]

Hai trong số nhiều hành trình đóng trên bàn cờ 8 x 8.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener. "Solution of the Knight's Hamiltonian Path Problem on Chessboards." Discrete Applied Math, volume 50, no.2, pp.125-134. 1994.
  2. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhi: Parimal Sanskrit Series No. 30. 
  • Watkins, John J. Across the Board: the Mathematics of Chessboard Problems. Princeton UP, 2004.

Liên kết ngoài[sửa | sửa mã nguồn]