Cờ vua là trò chơi trí tuệ, đối kháng giữa hai người. Bàn cờ vua có kích thước 8*8. Các dòng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô nằm ở hàng i, cột j được gọi là ô (i, j). Các đường chéo chính được đánh số từ -7 đến 7, ô thứ (i, j) sẽ nằm ở đường chéo chính thứ i-j. Các đường chéo phụ được đánh số từ 2 đến 16, ô thứ (i, j) sẽ nằm ở đường chéo phụ thứ i+j.
Bạn đang xem: Bài toán 8 quân hậu
Quân hậu trong cờ vua là quân cờ mạnh nhất. Nó có thể khống chế các quân cờ khác trong cùng hàng ngang, hàng dọc hay đường chéo chính, chéo phụ với nó. Ví dụ như trong hình dưới, quân hậu có thể khống chế các ô ở hàng 5, cột 5, đường chéo chính thứ 0, đường chéo phụ thứ 9.
Bài toán đặt ra là tìm tất cả các cách đặt 8 quân hậu lên bàn cờ sao cho không có hai quân hậu nào có thể khống chế nhau (nói cách khác, không có hai quân hậu nào ở cùng một hàng ngang, hàng dọc, đường chéo chính hay đường chéo phụ). Hình dưới là một ví dụ về cách đặt quân hậu thỏa bài toán trên.
1) Hướng giải quyết:
Trước hết, ta nhận thấy rằng, chỉ có thể đặt tối đa một quân hậu vào một hàng (Nếu có 2 quân trở lên thì chúng sẽ khống chế nhau). Chúng ta cần đặt 8 quân hậu, tức là mỗi hàng, chúng ta cần đặt đúng một quân. Như vậy, Gọi dãy số a1, a2, … a8, với ai = j nghĩa là quân hậu nằm ở hàng i được đặt ở cột j. Quân cờ thứ i sẽ có vị trí (i, ai). Ta cần tìm dãy số như trên thỏa:
Không có hai quân hậu nào ở cùng một cột, nghĩa là các phần tử ai khác nhau từng đôi một. Nói cách khác, dãy số a1, a2, … a8 là một hoán vị có độ dài bằng 8.Không có hai quân hậu nào ở cùng một đường chéo chính. Ta biết rằng hai quân cờ (x1, y1) và (x2, y2) nằm ở cùng một đường chéo chính khi x1 – y1 = x2 – y2.Không có hai quân hậu nào ở cùng một đường chéo phụ. Ta biết rằng hai quân cờ (x1, y1) và (x2, y2) nằm ở cùng một đường chéo phụ khi x1 + y1 = x2 + y2 .2) Thuật toán:
a) Cách 1: Đệ quy quay lui
Ta có thể giải quyết bài toán trên bằng thuật toán đệ quy quay lui. Ta sẽ sử dụng các mảng c, dc, dp với ý nghĩa như sau:
c = true nghĩa là chưa có quân hậu nào ở cột thứ i.dc = true nghĩa là chưa có quân hậu nào ở đường chéo chính thứ idp = true nghĩa là chưa có quân hậu nào ở đường chéo phụ thứ iDo trong c++, mảng luôn bắt đầu từ 0, nên ta sẽ xem quân cờ ở (i, j) sẽ ở đường chéo chính thứ i-j+8 (thay vì i-j) để tránh tràn mảng.
Số lượng dãy sinh ra: 88
#include bool c<9>, dc<20>, dp<20>;int a<9>;void _try (int i) { if (i > 8) { for(int j = 1; j
b) Cách 2: Sinh dãy 8-phân:
Ta cũng có thể sinh toàn bộ dãy 8-phân độ dài 8, với chữ số thứ i có thể có giá trị từ 1 -> 8, và kiểm tra xem dãy nhị phân đó là một cách đặt thỏa yêu cầu đề bài hay không bằng cách sử dụng ba mảng c, dp, dc với ý nghĩa như trên.Số lượng dãy sinh ra: 88 (Thực chất cách này giống với cách 1).Xem thêm: Sinh Năm 2018 Mệnh Gì? Tuổi Con Gì? Hợp Màu Nào? Hướng Nào Hợp?
using namespace std;#include bool c<9>, dc<20>, dp<20>;int a<9>;void _generate(int i) { if (i > 8) { memset(c, true, sizeof(c)); memset(dc, true, sizeof(dc)); memset(dp, true, sizeof(dp)); for (int j = 1; j