Tiếp tục series về giải thuật đệ quy , mình giới thiệu các bạn về bài toán n quân hậu (n Queens). Đối với bạn đã từng chơi cờ vua thì chắc các bạn cũng hình dung ra bài toán như thế nào và cũng biết cách giải quyết vấn đề đó trên bàn cờ, hôm nay mình sẽ giải quyết nó bằng ngôn ngữ lập trình. Cụ thể là thuật toán quay lui. Giới thiệu đôi chút về bài toán: Cho bàn cờ kích thước nxn và n con hậu, hãy tìm cách đặt n con hậu trên bàn cờ sao cho n con hậu không ăn được nhau, quân hậu trong bàn cờ vua có thể đi thẳng, ngang, chéo trên khắp bàn cờ nhé!. Hình bên dưới là một trường hợp bàn cờ vua kích thước 8x8 và 8 con hậu được đặt vào vị trí thỏa mãn bài toán mà thuật giải tìm được (hình ảnh được lấy từ Wikipedia ). +expand source //bài toán n quân hậu //lưu ý hàng, cột bắt đầu từ 0 đến n-1 void Queen( int a[], int n, int r) //mảng a[] để lưu giá trị...
Nhận xét
Đăng nhận xét