[Mỗi ngày 1 thuật toán] Bài toán Hiệp Sĩ – Mã đi tuần (Knight’s Tour Problem)

Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán Hiệp sĩ – Mã đi tuần (Knight’s Tour Problem). Để giải bài toán này, CodeGym sẽ cung cấp cho bạn ba đoạn mã nguồn quan trọng, bao gồm: C++, Java, và Python. 

1. Ý tưởng chính của bài toán

Bài toán Hiệp Sĩ yêu cầu tìm một đường đi của quân mã trên bàn cờ N x N sao cho nó thăm tất cả các ô đúng một lần. Quân mã di chuyển theo hình chữ “L”, nghĩa là từ vị trí của mình nó có thể di chuyển được tới các ô có chữ X như trong hình dưới đây:

Bài toán này có tính chất đệ quy một cách tự nhiên:

• Chia nhỏ vấn đề: Bài toán có thể được chia nhỏ thành các bài toán con nhỏ hơn: từ một ô bất kỳ, tìm đường đi đến các ô tiếp theo.
• Điều kiện dừng: Khi đã đi qua tất cả các ô trên bàn cờ hoặc không còn nước đi hợp lệ nào, quá trình tìm kiếm kết thúc.
• Tự gọi lại: Để tìm các đường đi khác, ta quay lại một ô trước đó và thử một nước đi khác.

2. Ví dụ minh hoạ

Ví dụ dưới đây biểu diễn một tuyến đường hợp lệ:

3. Mã nguồn C++

4. Mã nguồn Java

5. Mã nguồn Python

6. Giải thích

• Bắt đầu từ một ô bất kỳ trên bàn cờ.
• Xét tất cả các ô mà quân mã có thể di chuyển đến từ ô hiện tại.
• Đánh dấu ô hiện tại là đã đi qua.
• Gọi đệ quy để tìm đường đi từ các ô tiếp theo.
• Nếu không tìm thấy đường đi, quay lại và thử một nước đi khác.
• Nếu đã đi qua tất cả các ô trên bàn cờ thì đã tìm được một đường đi.
• Nếu không tìm được nước đi hợp lệ nào từ ô hiện tại thì quay lại.

7. Lưu ý

• Hiệu suất: Bài toán mã đi tuần là một bài toán NP-hard, do đó thời gian tính toán có thể rất lâu đối với các bàn cờ lớn.
• Cắt tỉa: Có thể sử dụng các kỹ thuật cắt tỉa để giảm không gian tìm kiếm và tăng hiệu suất.
• Các biến thể: Có nhiều biến thể của bài toán mã đi tuần, ví dụ như tìm tất cả các đường đi, tìm đường đi ngắn nhất,…

8. Ứng dụng

• Tìm kiếm đường đi: Bài toán có ứng dụng trong các bài toán tìm đường đi tối ưu trong đồ thị.
• Tối ưu hóa: Các thuật toán tìm kiếm đường đi của quân mã có thể được áp dụng để giải quyết các bài toán tối ưu hóa khác.

Xem thêm các bài viết thú vị về Thuật toán tại đây!