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

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 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. Có rất nhiều lời giải cho bài toán này, chính xác là 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ật được gọi là hành trình. | Bài toán mã đi tuần 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 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. Có rất nhiều lời giải cho bài toán này chính xác là 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ật đượ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. 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. 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. Hai lời giải với bàn cờ 8 x 8 theo Bách khoa toàn thư mở Wikipedia Ý tưởng cơ bản dùng thuật toán quay lui xuất phát từ 1 ô gọi số nước đi là t 1 ta cho quân mã thử đi tiếp 1 ô có 8 nước đi có thể nếu ô đi tiếp này chưa đi qua thì chọn làm bước đi tiếp theo. Tại mỗi nước đi kiểm tra xem tổng số nước đi bằng n n chưa nếu bằng thì mã đã đi qua tất cả các ô dừng do chỉ cần tìm một giải pháp . Trường hợp ngược lại gọi đệ quy để chọn nước đi tiếp theo. Ngoài ra nếu tại một bước tìm đường đi nếu không tìm được đường đi tiếp thì thuật toán sẽ quay lui lại nước đi trước và tìm đường đi .