[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à […]
Nguồn: https://codegym.vn/blog/thuat-toan/moi-ngay-1-thuat-toan-bai-toan-hiep-si-ma-di-tuan-knights-tour-problem/