Khác biệt giữa bản sửa đổi của “Bài toán mã đi tuần”

[[Tập tin:Knight's tour anim.gif|phải|nhỏ|200px|Một hành trình của quân mã trên bàn cờ]][[Tập tin:Knights-Tour-Animation.gif|phải|nhỏ|200px|Lời giải bài toán trên bàn cờ 5x5.]]

 

 

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.

|location = Delhi

}}

 

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

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

 

 

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×5 có 13 ô đen và 12 ô trắng.

[[Tập tin:Grid4xnColoredSquares.jpg|nhỏ|Con mã phải đi xen kẽ giữa màu xanh và màu đỏ.|200px|phải]]. Ta lại xét hình minh họa bên phải. Ta định nghiã <math> A_2 </math> là tập các ô màu xanh lá cây và <math> B_2 </math> 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 <math> A_2 </math> quân mã chỉ có thể nhảy sang một ô trong <math> B_2 </math>. 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 <math> B_2 </math> ở bước tiếp theo nó phải nhảy về một ô thuộc <math> A_2 </math> (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 <math> A_2 </math> điều đó không xảy ra).

 

 

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