[Mỗi ngày 1 thuật toán] Bài toán N quân hậu và giải pháp đệ quy

Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán N quân hậu (N – Queens 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: Tìm tất cả các cách để đặt N quân hậu lên một bàn cờ kích thước N x N sao cho không có hai quân hậu nào đe dọa lẫn nhau.

Bài toán N quân hậu là một bài toán tìm kiếm toàn diện. Bắt buộc phải duyệt qua tất cả các khả năng đặt quân hậu trên bàn cờ để tìm ra các cấu hình hợp lệ. Đệ quy là một công cụ lý tưởng cho những bài toán như vậy, vì tính chất đệ quy tự nhiên:

• Chia nhỏ vấn đề: Bài toán N quân hậu có thể được chia nhỏ thành các bài toán con nhỏ hơn. Đặt quân hậu vào hàng tiếp theo sau khi đã đặt các quân hậu ở các hàng trước đó.
• Điều kiện dừng: Khi đã đặt đủ N quân hậu mà không vi phạm bất kỳ quy tắc nào, ta tìm được một giải pháp.
• Tự gọi lại: Để tìm các giải pháp khác, ta quay lại hàng trước đó và thử đặt quân hậu ở một vị trí khác.

Ý tưởng chính để không có hai quân hậu nào cùng nằm trên một hàng, một cột hoặc một đường chéo:

• Bởi mỗi hàng chỉ đặt được một quân hậu, ta xét từng hàng, lần lượt thử đặt quân hậu vào các cột.
• Kiểm tra xem vị trí hiện tại có hợp lệ hay không (tức là không có quân hậu nào khác đe dọa).
• Nếu vị trí hợp lệ, đặt quân hậu vào đó và gọi đệ quy để đặt thêm quân hậu tiếp theo
• Nếu không tìm thấy vị trí hợp lệ nào, quay lại và thử đặt quân hậu ở cột khác của hàng trước đó.

2. Ví dụ minh hoạ của bài toán

Cho N = 4, một trong số các cách sắp xếp đúng là:

3. Mã nguồn C++

4. Mã nguồn Java

5. Mã nguồn Python

6. Giải thích

• Hàm isSafe: Kiểm tra xem việc đặt quân hậu ở vị trí (row, col) có hợp lệ hay không. Thực thi bằng cách so sánh với các quân hậu đã đặt ở các hàng trước đó.
• Hàm đệ quy:
  • Nếu đã đặt đủ N quân hậu, thêm một giải pháp vào danh sách kết quả.
  • Lặp qua các cột của hàng hiện tại. Nếu vị trí hợp lệ thì đặt quân hậu vào đó và gọi đệ quy để đặt các quân hậu tiếp theo.
  • Sau khi gọi đệ quy, gỡ bỏ quân hậu để thử các khả năng khác (backtrack).