Bài toán tám quân hậu có thể tổng quát hóa thành bài toán đặt n quân hậu trên bàn cờ n×n (n ≥ 4), bài toán không có nghiệm cho n=2,3.

Ở bài báo trước (tháng 7/2009) chúng tôi có đề cập tới “Bài toán 8 quân hậu và các vấn đề liên quan”. Đây là một bài toán quen thuộc nhưng có nhiều điều thú vị xung quanh. Trong bài báo này, chúng tôi xin đưa ra một vài lời giải của bài toán khi trong trường hợp n đặc biệt, đồng thời cũng đưa ra một cách để tìm lời giải với n là bất kỳ. Nếu chúng ta muốn tìm tất cả các nghiệm có thể, bài toán là khó khăn và phương pháp quay lui là phương pháp thường được biết đến. Trong bài toán 8 quân hậu, chúng ta có 92 nghiệm tất cả. Nếu chúng ta loại trừ các nghiệm đối xứng thi chỉ còn lại 12 nghiệm (nghiệm cơ bản)

1. Xây dựng một lời giải cho bài toán n quân hậu[wiki]

Có một giải thuật đơn giản tìm một lời giải cho bài toán nquân hậu với 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ụ

• 8 quân hậu (r = 8): 2, 4, 6, 8, 3, 1, 7, 5.
• 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.

Cụ thể ví dụ với n=8->r=8(vì 8 mod 12=8)

-Viết lần lượt các số chẵn từ 2 đến n: 2,4,6,8

-Bổ sung lần lượt các số lẻ từ 1 đến n vào cuối danh sách: 2,4,6,8,1,3,5,7

-n=8->đổi chỗ từng cặp các số lẻ: 2,4,6,8,3,1,7,5

-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.(Chú ý chỉ số tính từ 1)

2. Xây dựng một số lời giải cho các trường hợp đặc biệt của n

2.1. Khi n là số nguyên tố [bridge]

Nếu n là một số nguyên tố, một nghiệm dễ dàng được tìm bằng cách vẽ một đường thẳng trên mặt phẳng hữu hạn (n,n). Vì không có hai đường thẳng nào có thể giao nhau tại hai điểm phân biệt, một đường thẳng y=ax+b với hệ số a khác 1 và -1có thể cho một nghiệm. Trong đó b điều chỉnh từ 0.

Chúng ta dễ ràng tìm được 4*7=28 nghiệm bằng cách lần lượt thay thế a=2,3,4,5 và b=0,1,2,3,4,5,6 (Tại sao không để a,b tăng nữa?)

Tỷ lệ của các nghiệm phân tích được trên tổng số nghiệm cho một vài giá trị p nhỏ như sau:

p=5, 10/10, 100%

p=7, 28/40, 70%

p=11, 88/2680, 3,3%

Cho n=p.q, chúng ta có thể tạo một cách tìm ra mốt số lời giải của bài toán p quân hậu và q quân hậu. Bằng cách, mỗi một vị trí của bài toán p quân hậu được xem như một lớp các nghiệm của bài toán q quân hậu. Chúng ta có thể hoán đổi vai trò của p và q. Ví dụ n=35=5*7 ta có thể sinh 10*(40)^5 + 40*(10)^7 = 1424000000 nghiệm. Trong đó 10 là tổng số nghiệm bài toán 5 quân hậu và 40 là tổng số nghiệm của bài toán 7 quân hậu.

2.2 Khi n là số Fermat’s[Fermat]

Định lý Fermat's 4n+1phát biểu rằng mỗi số nguyên tố có dạng 4n+1 thì có thể được viết thành tổng bình phương hai số. Một lớp các nghiệm tương tự của bài toán n quân hậu được phân tích. Cho ví dụ, 13=2­­­­­²+3², đặt một quân hậu vào trung tâm bàn cờ cỡ 13x13. Từ vị trí trung tâm di chuyển sang ngang 2 ô, lên trên 3 ô và đặt quân hậu vào ô vuông thu được. Tiếp tục di chuyển và đăt các quân hậu lên bàn cờ theo cách này, đồng nhất cạnh trên với cạnh dưới cũng như cạnh trái với cạnh phải của bàn cờ.

2.3 Một số trường hợp khác

Để sinh một nghiệm cho một n tổng quát , cho mặt phẳng được điều chỉnh bởii=0, ..., n-1 và j=0, ..., n-1.

Khi n là số chẵn. Xem k là số tự nhiên dương, ta có các trường hợp

(1) Nếu n có dạng 6k hoặc 6k+4.

j = 2*i+1, với 0 <= i < n/2

j = 2*i mod n, với n/2 <= i < n

Ví dụ với n=6

(2) Nếu n là dạng 6k+2, 6k+4

j = (n/2 + 2i -1) mod n, với 0 <= i < n/2

j = (n/2 + 2i + 2) mod n, với n/2 <= i

Ví dụ với n=8

Khi n là số lẻ. Chúng ta có thể gắn một quân hậu ở vị trí (n-1, n-1). Chú ý rằng với n chẵn thì nghiệm của nó không chứa quân hậu nào ở vị trí “góc”.

Ví dụ với n=9

3. Kết luận

Như chúng tôi đã trình bày, hiện nay đã có thuật toán tìm ra một lời giải cho mọi trường hợp N (số quân hậu). Tuy nhiên, trong một số trường hợp khi N là số chẵn hay số lẻ chúng ta có thể có thêm lời giải. Đặc biệt trong trường hợp N là số nguyên tố ta có thể tìm được một số lời giải cho bài toán. Định lý Fermat cho số 4n+1 tưởng như chỉ mang tính chất thuần túy toán học nhưng nó lại được áp dụng để tìm ra nghiệm cho bài toán N quân hậu và cách xây dựng nghiệm thì thật là ấn tượng!

Tài liệu tham khảo

[bridge]http://bridges.canterbury.ac.nz/features/eight.html

[Fermat]http://demonstrations.wolfram.com/Fermats4n1TheoremAndTheNQueensProblem/

[wiki]http://en.wikipedia.org/wiki/Eight_queens_puzzle

Nguyễn Văn Hậu¹, Lưu Văn Ba² , Nguyễn Quang Sáng³

Khoa CNTT, Trường Đại học Sư Phạm Kỹ thuật Hưng Yên

nvhau66@gmail.com;balvpro@gmail.com; saobang88hy@gmail.com

School@net (Theo THNT)