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

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

bởi ngoctran2 | 11:47 | Blog | Thuật toán

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à:

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

3. Mã nguồn C++

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

4. Mã nguồn Java

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

5. Mã nguồn Python

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

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).

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

0 Lời bình

Gửi Lời bình

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

BÀI VIẾT LIÊN QUAN

BẠN MUỐN HỌC LẬP TRÌNH?

GỌI NGAY

098 953 44 58

Đăng ký tư vấn lộ trình học lập trình

Đăng ký tư vấn, định hướng lộ trình học và giải đáp các thắc mắc về ngành nghề – Miễn phí – Online.

2 + 1 =

TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM
TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM