Về Mã đi tuần | Quy tắc Warnsdorff, hành trình mở và đóng

Một câu đố cổ

Trong Kavyalankara, tác phẩm của nhà thơ Ấn Độ Rudrata vào thế kỷ 9, một câu thơ được xếp trên nửa bàn cờ sao cho có thể đọc nó theo đường đi của quân mã. Leonhard Euler viết công trình toán học đầu tiên về hành trình của quân mã vào năm 1759, với các cách dựng hành trình và biến chúng thành hành trình đóng.

Một đường đi trên đồ thị

Hãy coi mỗi ô là một điểm và mỗi nước đi của quân mã là một đoạn nối giữa hai điểm. Khi đó hành trình của quân mã là một đường đi qua mọi điểm đúng một lần, mà các nhà toán học gọi là đường đi Hamilton; hành trình đóng là một chu trình Hamilton. Với hầu hết các mạng, một đường đi như vậy rất khó tìm. Mạng của quân mã thì hào phóng: nó có nhiều hành trình đến mức một quy tắc tốt tìm ra một hành trình rất nhanh.

Quy tắc Warnsdorff

H. C. von Warnsdorff mô tả quy tắc của mình vào năm 1823: luôn nhảy đến ô để lại ít nước đi tiếp nhất. Các ô dọc mép có ít ô lân cận, nên quy tắc ghé chúng sớm thay vì để chúng bị bỏ lại cô lập. Khi hai ô ngang nhau, cần phải chọn, và một lựa chọn không may vẫn có thể khiến quân mã bị kẹt. Trong ứng dụng, các số màu vàng đánh dấu những ô mà quy tắc sẽ chọn.

Tìm kiếm bằng quay lui

Giải đi theo thứ tự của Warnsdorff nhưng không tin nó một cách mù quáng. Nó tìm kiếm theo chiều sâu, và ngay khi một ô chưa đi qua không còn tới được nữa, nó bỏ nhánh đó và thử nước đi tiếp theo. Trên bàn cờ đến 10×10, nó thường tìm được hành trình ngay lập tức. Khi chính đường đi của bạn đã vây kín quân mã, nó lùi lại vài nước trước.

Màu ô và hành trình đóng

Mỗi nước đi của quân mã đều đổi màu ô. Trên bàn cờ lẻ như 5×5, số ô cùng màu với ô góc nhiều hơn số ô màu kia một ô, nên hành trình phải bắt đầu và kết thúc ở ô cùng màu với ô góc. Ở đó không thể có hành trình đóng, vì một vòng khép kín xen kẽ màu có số ô mỗi màu bằng nhau. Trên bàn cờ chẵn, hành trình đóng có từ 6×6 trở lên.

Thử trong PictorX

Mở Mã đi tuần và bấm một ô để bắt đầu. Các ô được tô sáng là những bước nhảy hợp lệ, số màu vàng là lựa chọn của Warnsdorff, và bàn cờ ghi lại thứ tự các nước đi của bạn. Kích thước đặt bàn cờ từ 5×5 đến 10×10, Hành trình đóng yêu cầu Giải tìm một vòng khép kín, và Hoàn tác rút lại bất kỳ nước đi nào. Lưu đường đi đã hoàn thành thành PNG.

Hỏi thường xuyên

Ai là người đầu tiên nghiên cứu hành trình của quân mã?

Các hành trình đã được biết đến từ lâu trước khi có người nghiên cứu chúng bằng toán học. Leonhard Euler viết công trình toán học đầu tiên vào năm 1759, và Warnsdorff đưa ra quy tắc của mình vào năm 1823.

Bàn cờ nào cũng có hành trình không?

Các bàn cờ vuông từ 5×5 trở lên có hành trình mở, và các bàn chẵn từ 6×6 trở lên còn có cả hành trình đóng. Bàn cờ 2×2, 3×3 và 4×4 hoàn toàn không có hành trình nào.

Một bàn cờ vua có bao nhiêu hành trình?

Có 26.534.728.821.064 hành trình đóng nếu một hành trình và chính hành trình đó đi theo chiều ngược lại được tính riêng. Số hành trình mở là khoảng 19,6 triệu tỷ.

PictorX có tải gì lên không?

Không. Bàn cờ được vẽ trên canvas trong trình duyệt. Lưu sẽ tải xuống một PNG, và Chỉnh sửa mở ảnh đó trong trình chỉnh sửa PictorX.