Bài toán mã đi tuần bằng đệ quy

Mã đi tuần (tốt hành trình dài của quân mã) là bài bác toán thù về Việc dịch chuyển một quân mã trên bàn cờ vua (8 x 8). Quân mã được đặt tại 1 ô bên trên một bàn cờ trống nó nên dịch chuyển theo phép tắc của cờ vua để trải qua mỗi ô bên trên bàn cờ đúng một lần. Trong bài xích này, chúng tôi xin ra mắt về bài xích toán thú vị này và những điều hoàn toàn có thể khai quật được qua bài tân oán.

Bạn đang xem: Bài toán mã đi tuần bằng đệ quy

Trong cờ vua, quân Mã là quân bao gồm phương pháp đi phức hợp tuyệt nhất. Xét một quân Mã vẫn đứng bên trên bàn cờ cùng toàn bộ các hình chữ nhật 2 x 3 thừa nhận ô nhưng quân Mã đó đang đứng làm cho đỉnh. Quân Mã kia hoàn toàn có thể đi tới các đỉnh không giống màu với đỉnh nó đã đứng của bất kể hình chữ nhật 2 x 3 như thế nào, miễn sao đỉnh kia ko ở ngay gần đỉnh nó đang đứng.Quân Mã rất có thể dancing qua tất cả những quân khác để mang đến ô nó mong mỏi, miễn sao ô kia chưa bị ai chỉ chiếm giữ lại. Nói nôm mãng cầu là quân Mã không trở nên cản. Khác cùng với cờ tướng, địa điểm mà lại quân Mã có thể bị cản trường hợp gồm quân như thế nào đứng ngay trước mặt nó, vào cờ vua, nước đi của quân Mã không có đặc thù này.Khi một quân Mã đứng ở cạnh bàn cờ, số nước đi rất có thể của nó có khả năng sẽ bị thu bé xuống còn những tuyệt nhất là một nửa số nước đi thuở đầu. Đặc biệt, nếu nó đứng sống 1 trong những bốn góc bàn cờ, nó chỉ đi được tối đa nhì nước. Câu nói “Mã ngơi nghỉ rìa cũng giống như đồ gia dụng trang trí” trường đoản cú trên đây cơ mà ra.

*

 

Xuất xđọng bài toán

Bài toán thù quân Mã đi tuần là 1 trong những dạng của bài toán thù tổng thể rộng là bài toán thù tìm kiếm lối đi Hamilton trong l‎ý thuyết thứ thị, là một trong bài tân oán NP-tương đối đầy đủ. Bài tân oán kiếm tìm hành trình dài đóng của quân mã là 1 trong bài xích tân oán cụ thể của bài xích tân oán tìm kiếm chu trình hamiltonian.

hầu hết biến thể của chủ thể này được những nhà toán học tập phân tích, trong số ấy bao gồm đơn vị toán thù học Euler. Các thay đổi rất có thể theo các hướng:

Ttốt đổi kích thước bàn cờ.

Xem thêm: Exp Là Viết Tắt Của Từ Gì Trong Thuốc, Mỹ Phẩm, Game, Viết Tắt Tiếng Anh Nào

Biến thành trò đùa nhị bạn theo bốn tưởng này.

Giảm dịu các tận hưởng trên tuyến đường đi của quân Mã.

BÀI TOÁN QUÂN MÃ ĐI TUẦN TRONG TIN HỌC

1. Ý tưởng cơ bản

Dùng thuật tân oán xoay lui; lên đường từ là một ô, Call số nước đi là t=1 , ta mang đến quân mã test đi tiếp 1 ô (tất cả 8 nước đi có thể), trường hợp ô đi tiếp này không đi qua thì lựa chọn làm bước tiến tiếp sau. Tại mỗi nước đi kiểm soát xem tổng thể nước đi bằng n x n không, nếu bởi thì mã đã trải qua toàn bộ những ô ⇒ dừng (bởi vì chỉ việc tra cứu một giải pháp). Trường hòa hợp ngược lại, Call đệ quy nhằm lựa chọn nước đi tiếp sau. Dường như, giả dụ tại một bước tìm kiếm lối đi, trường hợp không kiếm được lối đi tiếp thì thuật toán đang quay lui lại nước đi trước và kiếm tìm đường đi không giống.

2. Cấu trúc dữ liệu

Mảng board: lưu giữ bàn cờ, trong những số đó board là ô (i, j); quý hiếm của board là 0 lúc quân mã chưa trải qua, và >0 khi quân mã đã trải qua, quý hiếm board lúc này chính là sản phẩm từ nước đi trên hành trình.Mảng dr<8>, dc<8>: lưu lại các độ dời của bước đi sau đó, có tám nước đi rất có thể mang lại địa chỉ quân mã bây giờ. Do đó nhằm đi nước thiết bị i ta chỉ việc thêm vào đó dr đến cái cùng dc đến cột.dr<> = -2, -2, -1, -1, 1, 1, 2, 2 dc<> = -1, 1, -2, 2, -2, 2, -1, 1

3. Thuật giải đệ quy

Tại mỗi bước thứu tự đến quân mã thử toàn bộ những nước đi tiếp đến (tám nước đi kế tiếp). Với mỗi bước đi, soát sổ coi nếu nước đi hợp lệ (không trải qua với sống trong bàn cờ) thì test đi nước này. Nếu quân mã vẫn trải qua không còn bàn cờ thì xuất tác dụng. trái lại thì điện thoại tư vấn đệ quy tiếp đến địa điểm bắt đầu thử bên trên. Lưu ý là mọi khi địa điểm sẽ đi qua được đánh dấu thiết yếu bởi thiết yếu lắp thêm tự nước đi trên bàn cờ. Sau Lúc không test vị trí này thì đề xuất bỏ ghi lại để lựa chọn giải pháp không giống (ngôi trường hòa hợp cù lui).Nếu coi các ô của bàn cờ là các đỉnh của đồ gia dụng thị với những cạnh là nối thân nhì đỉnh tương ứng với nhì ô mã giao chân thì dễ thấy rằng hành trình của quân mã nên tra cứu đang là 1 mặt đường đi Hamilton. Ta hoàn toàn có thể xây dựng hành trình dài bởi thuật toán cù lui phối kết hợp với cách thức duyệt ưu tiên Warnsdorff: Nếu Gọi deg(x, y) là số ô kề cùng với ô (x, y) và không trải qua (kề tại đây theo nghĩa đỉnh kề chđọng không phải là ô kề cạnh) thì xuất phát từ 1 ô ta sẽ không demo xét theo lần lượt những hướng đi có thể, mà ta sẽ ưu tiên demo phía đi tới ô bao gồm deg bé dại duy nhất trước. Trong trường hợp tất cả tồn tại đường đi, phương pháp này hoạt động cùng với tốc độ giỏi vời: Với các n chẵn trong vòng trường đoản cú 6 tới 18, với tất cả địa điểm ô xuất hành, trung bình thời hạn tính tự dịp bắt đầu tới thời gian tìm thấy một nghiệm

*