Mã đi tuần (hay hành trình của quân mã) là vấn đề 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 đang xem: Bài toán mã đi tuần
Mã đi tuần (hay hành trình dài của quân mã) là câu hỏi 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 ở một ô trên một bàn cờ trống nó phải dịch chuyển theo nguyên tắc của cờ vua để đi qua mỗi ô bên trên bàn cờ đúng một lần. Trong bài bác này, cửa hàng chúng tôi xin ra mắt về việc thú vị này và gần như điều rất có thể khai thác được qua bài bác toán.
I – MỞ ĐẦU
1. Nước đi của quân Mã (♘) bên trên bàn cờ
Hình 1: Vị trí lên đường của quân Mã trên bàn cờTrong cờ vua, quân Mã là quân tất cả cách đi tinh vi nhất. Xét một quân Mã đang đứng bên trên bàn cờ và tất cả các hình chữ nhật 2 x 3 nhận ô nhưng mà quân Mã đó sẽ đứng làm đỉnh. Quân Mã đó có thể đi tới các đỉnh không giống màu cùng với đỉnh nó đang đứng của bất kể hình chữ nhật 2 x 3 nào, miễn là đỉnh đó không nằm ngay bên cạnh đỉnh nó đã đứng.
Hình 2: Nước đi của quân MãQuân Mã có thể nhảy qua toàn bộ các quân khác để mang đến ô nó muốn, miễn sao ô đó không bị ai chiếm giữ. Nói nôm na là quân Mã không xẩy ra cản. Khác với cờ tướng, địa điểm mà quân Mã có thể bị cản nếu gồm quân làm sao đứng ngay trước phương diện nó, vào cờ vua, nước đi của quân Mã không có tính chất 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ó sẽ ảnh hưởng thu thuôn xuống còn nhiều nhất là một nửa số nước đi ban đầu. Đặc biệt, nếu như nó đứng ở 1 trong bốn góc bàn cờ, nó chỉ đi được buổi tối đa hai nước. Lời nói “Mã làm việc rìa cũng như đồ trang trí” từ đây cơ mà ra.
Bài toán quân Mã đi tuần là một trong những dạng của bài toán tổng quát hơn là việc tìm lối đi Hamilton vào lý thuyết đồ gia dụng thị, là một trong những bài toán NP-đầy đủ. Bài toán tìm hành trình dài đóng của quân mã là 1 trong bài toán rõ ràng của việc tìm quy trình hamiltonian.
Nhiều biến thể của chủ đề này được những nhà toán học nghiên cứu, trong các số ấy có bên toán học Euler. Các chuyển đổi có thể theo những hướng:
Thay đổi size bàn cờ.Biến thành trò nghịch hai bạn theo tư tưởng này.Giảm nhẹ các yêu cầu trê tuyến phố đi của quân Mã.
– LỜI GIẢI mang lại BÀI TOÁN TRÊN BÀN CỜ 8 x 8
Có không hề ít lời giải cho việc này trên bàn cờ vua tiêu chuẩn 8 x 8, ví dụ là đến nay đã có 26.534.728.821.064 (bạn hoàn toàn có thể đọc được số lượng này không?) lời giải trong những số ấy quân Mã gồm thể dứt tại chủ yếu ô nhưng nó khởi đầu. Một hành trình dài như vậy của quân Mã được gọi là 1 trong hành trình đóng, còn một hành trình mà quân Mã đi qua toàn bộ các ô, mỗi ô một lần tuy nhiên không thể trở lại ô lúc đầu của nó chỉ bằng một nước đi được gọi là một trong hành trình mở. Dưới đấy là một lời giải cho bàn cờ 8 x 8.
Hình 4: Một lời giải cho câu hỏi Quân Mã đi tuần trên bàn cờ 8 x 8
III – MỞ RỘNG BÀI TOÁN mang lại BÀN CỜ m x n BẤT KÌ
Câu hỏi đưa ra là, với cặp số (m; n) như thế nào thì quân Mã hoàn toàn có thể có một hành trình đóng đi qua tất cả các ô trên bàn cờ? Định lí Schwenk sau đây cho chúng ta lời giải cho câu hỏi đó.
Định lí Schwenk: đến bàn cờ m × n ngẫu nhiên với m ≤ n. Không có hành trình đóng góp nào của quân mã nếu 1 trong ba điều kiện dưới đây xảy ra:
Điều khiếu nại 1: trên bàn cờ vua, những ô black và trắng xen kẽ nhau, một quân mã luôn luôn đi từ 1 ô cho tới ô khác màu. Vày m và n gần như là lẻ nên lúc đó số những ô black và white trên bàn cờ là không giống nhau. Một đường đi đóng của quân mã phải có số ô black và trắng bởi nhau, tổng cộng ô bên trên mọi hành trình dài đóng là số chẵn. Cho nên vì vậy một hành trình dài đóng ko thể trải qua mỗi ô đúng một lần khi số những ô bên trên bàn cờ là số lẻ.
Dễ thấy rằng lúc m = 1 hoặc 2 cần yếu có hành trình dài của quân mã: quân mã ko thể đi qua mọi ô.Giả sử 1 bàn cờ kích thước 4 × n gồm một hành trình dài đóng của quân mã. Xét $latex A_1$ là tập tất cả các ô đen và $latex B_1$ là tập toàn bộ các ô white trên bàn cờ. Theo phương tiện cờ, quân Mã luôn di chuyển liên tiếp giữa các thành phần thuộc $latex A_1$ cùng $latex B_1$.
Xét hình minh hoạ sinh hoạt trên. điện thoại tư vấn $latex A_2$ là tập những ô chứa chữ A, $latex B_2$là tập những ô chứa chữ B. Nằm trong bảng vuông 4 x n, số ô chứa chữ A và chữ B là bằng nhau, vậy cần $latex |A_2|=|B_2|.$Nhận xét: xuất phát điểm từ một ô thuộc $latex A_2$, quân Mã yêu cầu nhảy tới một ô nằm trong $latex B_2$, và tại 1 ô trực thuộc $latex B_2$, quân Mã nên nhảy cho tới một ô trực thuộc $latex A_2$. Mang sử trong hành trình đóng của quân Mã, ô xuất xứ của nó là 1 ô trực thuộc $latex A_1$∩$latex A_2$. Lúc đó, ô tiếp theo sau nó nhảy đầm tới là 1 trong những ô thuộc $latex B_1$ ∩ $latex B_2$, ô thứ cha nó dancing tới lại là một trong những ô thuộc $latex A_1$ ∩ $latex A_2$,... Hành trình này không chứa những ô thuộc tập $latex A_1$ ∩ $latex B_2$ và $latex A_2$ ∩ $latex B_1$, cho nên không thể chứa tất cả các ô trên bàn cờ. Chứng minh tương tự cho những trường hợp ô xuất phát của quân Mã trực thuộc $latex A_1$ ∩ $latex B_2$, $latex A_2$ ∩ $latex B_1$, $latex A_2$ ∩ $latex B_2$. Như vậy, cùng với bảng vuông 4 x n, không có một hành trình đóng của quân Mã.
IV - BÀI TOÁN QUÂN MÃ ĐI TUẦN vào TIN HỌC
1. Ý tưởng cơ bản
Dùng thuật toán con quay lui; xuất phát từ một ô, hotline số nước đi là $latex t=1$, ta mang lại quân mã demo đi tiếp 1 ô (có 8 nước đi tất cả thể), giả dụ ô đi tiếp này chưa đi qua thì lựa chọn làm bước đi tiếp theo. Tại từng nước đi khám nghiệm xem toàn bô nước đi bằng n x n chưa, nếu bằng thì mã đã đi được qua tất cả các ô ⇒ giới hạn (do chỉ cần tìm một giải pháp). Trường đúng theo ngược lại, call đệ quy để lựa chọn nước đi tiếp theo. Kế bên ra, nếu như tại một bước tìm mặt đường đi, nếu không kiếm được đường đi tiếp thì thuật toán vẫn quay lui lại nước đi trước cùng tìm đường đi khác.2. Cấu tạo dữ liệu
Mảng board3. Thuật giải đệ quy
Tại mỗi bước lần lượt đến quân mã thử toàn bộ các nước đi sau đó (tám nước đi kếtiếp). Với từng bước một đi, khám nghiệm xem giả dụ nước đi hòa hợp lệ (chưa trải qua và làm việc trongbàn cờ) thì demo đi nước này. Nếu quân mã đã đi qua hết bàn cờ thì xuất kết quả.Ngược lại thì call đệ quy tiếp đến vị trí mới thử trên. Lưu ý là mỗi một khi vị trí sẽ điqua được ghi lại chính bởi chính sản phẩm tự nước đi trên bàn cờ. Sau khi khôngthử địa chỉ này thì yêu cầu bỏ lưu lại để chọn phương án khác (trường vừa lòng quay lui).Nếu coi các ô của bàn cờ là các đỉnh của vật thị và các cạnh là nối giữa hai đỉnh tương ứngvới nhị ô mã giao chân thì hay thấy rằng hành trình của quân mã yêu cầu tìm sẽ là một trong những đường điMã đi tuần (hay hành trình dài của quân mã) là câu hỏi về việc di chuyển một quân mã bên trên bàn cờ vua (8 x 8). Quân mã được đặt tại 1 ô trên 1 bàn cờ trống nó phải di chuyển theo nguyên tắc của cờ vua để đi qua mỗi ô bên trên bàn cờ đúng một lần. Trong bài này, cửa hàng chúng tôi xin reviews về câu hỏi thú vị này và đông đảo điều có thể khai thác được qua bài bác toán.
Trong cờ vua, quân Mã là quân có cách đi phức hợp nhất. Xét một quân Mã đã đứng bên trên bàn cờ và tất cả các hình chữ nhật 2 x 3 dìm ô mà quân Mã đó vẫn đứng làm cho đỉnh. Quân Mã đó rất có thể đi tới các đỉnh khác màu với đỉnh nó vẫn đứng của bất kỳ hình chữ nhật 2 x 3 nào, miễn sao đỉnh đó không nằm ngay bên cạnh đỉnh nó đã đứng.Quân Mã có thể nhảy qua tất cả các quân không giống để đến ô nó muốn, miễn sao ô đó chưa bị ai chỉ chiếm giữ. Nói nôm na là quân Mã không xẩy ra cản. Không giống với cờ tướng, khu vực mà quân Mã hoàn toàn có thể bị cản nếu bao gồm quân như thế nào đứng ngay trước phương diện nó, vào cờ vua, nước đi của quân Mã không tồn tại tính hóa học này.Khi một quân Mã đứng nghỉ ngơi cạnh bàn cờ, số nước đi rất có thể của nó sẽ bị thu hẹp xuống còn nhiều nhất là một nửa số nước đi ban đầu. Đặc biệt, ví như nó đứng ở một trong các bốn góc bàn cờ, nó chỉ đi được buổi tối đa nhị nước. Câu nói “Mã sinh sống rìa cũng như đồ trang trí” từ đây mà lại ra.
Xuất xứ bài xích toán
Bài toán quân Mã đi tuần là một trong dạng của vấn đề tổng quát rộng là việc tìm đường đi Hamilton trong lý thuyết trang bị thị, là 1 trong những bài toán NP-đầy đủ. Vấn đề tìm hành trình dài đóng của quân mã là một bài toán rõ ràng của vấn đề tìm quy trình hamiltonian.
Nhiều biến thể của chủ đề này được các nhà toán học tập nghiên cứu, trong những số ấy có đơn vị toán học tập Euler. Các chuyển đổi có thể theo những hướng:
Thay đổi form size bàn cờ.
Biến thành trò chơi hai bạn theo tứ tưởng này.
Giảm nhẹ những yêu cầu trên đường đi của quân Mã.
Xem thêm: 5 tự học tiếng anh giao tiếp như thế nào mới hiệu quả, 11 cách giúp bạn học tiếng anh giao tiếp tại nhà
BÀI TOÁN QUÂN MÃ ĐI TUẦN vào TIN HỌC
1. Ý tưởng cơ bản
Dùng thuật toán xoay lui; xuất phát từ là 1 ô, hotline số nước đi là t=1 , ta cho quân mã test đi tiếp 1 ô (có 8 nước đi bao gồm thể), giả dụ ô đi tiếp này chưa đi qua thì chọn làm bước tiến tiếp theo. Tại từng nước đi đánh giá xem toàn bô nước đi bởi n x n chưa, nếu bằng thì mã đã đi qua tất cả các ô ⇒ ngừng (do chỉ cần tìm một giải pháp). Trường thích hợp ngược lại, hotline đệ quy để chọn nước đi tiếp theo. Quanh đó ra, giả dụ tại một bước tìm con đườ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ới tìm lối đi khác.
2. Cấu tạo dữ liệu
Mảng board3. Thuật giải đệ quy
Tại mỗi bước lần lượt mang lại quân mã thử tất cả các nước đi sau đó (tám nước đi kế tiếp). Với từng bước đi, đánh giá xem giả dụ nước đi hợp lệ (chưa trải qua và sinh sống trong bàn cờ) thì test đi nước này. Trường hợp quân mã đã trải qua hết bàn cờ thì xuất kết quả. Ngược lại thì gọi đệ quy tiếp mang đến vị trí bắt đầu thử trên. Xem xét là mỗi lúc vị trí vẫn đi qua được khắc ghi chính bởi chính máy tự nước đi trên bàn cờ. Sau khoản thời gian không thử địa điểm này thì yêu cầu bỏ lưu lại để chọn chiến thuật khác (trường phù hợp quay lui).Nếu coi những ô của bàn cờ là các đỉnh của đồ dùng thị và những cạnh là nối thân hai đỉnh tương ứng với nhì ô mã giao chân thì hay thấy rằng hành trình dài của quân mã đề nghị tìm sẽ là 1 đường đi Hamilton. Ta hoàn toàn có thể xây dựng hành trình dài bằng thuật toán xoay lui phối hợp với phương pháp duyệt ưu tiên Warnsdorff: Nếu hotline deg(x, y) là số ô kề cùng với ô (x, y) và chưa trải qua (kề tại đây theo nghĩa đỉnh kề chứ chưa phải là ô kề cạnh) thì từ một ô ta sẽ không còn thử xét lần lượt những hướng đi có thể, nhưng ta vẫn ưu tiên demo hướng đi tới ô có deg nhỏ dại nhất trước. Trong ngôi trường hợp gồm tồn tại đường đi, cách thức này vận động với vận tốc tuyệt vời: với đa số n chẵn trong tầm từ 6 tới 18, với tất cả vị trí ô xuất phát, trung bình thời gian tính tự lúc bước đầu tới cơ hội tìm ra một nghiệm