Bàn luận về bài toán “8 hậu”

[kiemkhach123]

Bài toán 8 quân hậu thì có 92 lời giải! và dùng giải thuật quay lui là hiệu quả nhất!

cũng không hẳn là như vậy. Quay lui thử sai có cái lợi và cũng có cái hại của nó. Cái lợi là ở chỗ nó có thể tìm được 100% các lời giải. cái hại là ở chỗ chạy chậm + tốn ram (kể cả khi chúng ta chỉ tìm 1 lời giải, nó vẫn chậm).
Với bài toán N hậu, nhiều khi chúng ta chỉ cần tìm ra 1 lời giải đúng nhưng phải tìm thật nhanh.Để đáp ứng yêu cầu đó thì có 1 phương pháp đơn giản như sau:

Ký hiệu quân hậu đứng ở ô nằm trên hàng thứ i của lời giải là Q[i,j]. Các chỉ số dòng cột đánh từ trên xuống dưới, trái sang phải theo cách đánh số trong ma trận). Trong một ma trân vuông:

* các phần tử nằm trên cùng hàng có chỉ số hàng bằng nhau;
* các phần tử nằm trên cùng cột có chỉ số cột bằng nhau;
* các phần tử nằm trên cùng một đường chéo song song với đường chéo chính có hiệu chỉ số hàng với chỉ số cột bằng nhau;
* các phần tử nằm trên cùng một đường chéo song song với đường chéo phụ có tổng chỉ số hàng với chỉ số cột bằng nhau;

Vì thế ta gọi các đường chéo song song với đường chéo chính là đường chéo trừ (hay hiệu), các đường chéo song song với đường chéo phụ là đường chéo cộng (hay tổng).

Do đó, mỗi lời giải có thể được biểu diễn bởi dãy Q[1,i1],Q[2,i2],...,Q[n,in],thỏa mãn các điều kiện:

* Các chỉ số cột i1, i2,..., in đôi một khác nhau, hay chúng lập thành một hoán vị của các số 1, 2,.., n.
* Tổng chỉ số dòng và cột của các quân hậu 1+i1, 2+i2,..., n+in đôi một khác nhau;
* Hiệu chỉ số dòng và cột của các quân hậu 1-i1, 2-i2,...,n-in đôi một khác nhau.

Chẳng hạn lời 1 lời giải cho N = 8 được biểu diễn bới dãy ô (1 ,4),(2, 7), (3, 3), (4, 8), (5,2), (6,5), (7,1), (8,6). Ta có thể kiểm tra các điều kiện trên trong bảng:
i 1 2 3 4 5 6 7 8
j 4 7 3 8 2 5 1 6
i+j 5 9 6 12 7 11 8 14
i-j -3 -5 0 -4 3 1 6 2

Có một giải thuật đơn giản tìm một lời giải cho bài toán n quân hậu với n = 1 hoặc n ≥ 4:

1. Chia n cho 12 lấy số dư r. (r= 8 với bài toán tám quân hậu).
2. Viết lần lượt các số chẵn từ 2 đến n.
3. Nếu số dư r là 3 hoặc 9, chuyển 2 xuống cuối danh sách.
4. Bổ sung lần lượt các số lẻ từ 1 đến n vào cuối danh sách, nhưng nếu r là 8, đổi chỗ từng cặp nghĩa là được 3, 1, 7, 5, 11, 9, ….
5. Nếu r = 2, đổi chỗ 1 và 3, sau đó chuyển 5 xuống cuối danh sách.
6. Nếu r = 3 hoặc 9, chuyển 1 và 3 xuống cuối danh sách.
7. Lấy danh sách trên làm danh sách chỉ số cột, ghép vào danh sách chỉ số dòng theo thứ tự tự nhiên ta được một lời giải của bài toán.

Sau đây là một số ví dụ

* 14 quân hậu (r = 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
* 15 quân hậu (r = 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
* 20 quân hậu (r= 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.

[lehuydung]

anh oi ! em down không được
gui cho e voi traitimbang_sbtt@yahoo.com.vn
thank