Bài toán quân hậu có thể được phát biểu như sau:

Bài toán tám quân hậu là bài toán đặt tám quân hậutrên bàn cờ vua kích thước 8×8 sao cho không có quân hậu nào có thể "ăn" được quân hậu khác, hay nói khác đi không quân hậu nào có để di chuyển theo quy tắc cờ vua. Mầu của các quân hậu không có ý nghĩa trong bài toán này. Như vậy, lời giải của bài toán là một cách xếp tám quân hậu trên bàn cờ sao cho không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đường chéo. 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. [wiki].

1.Một số ứng dụng

Bài toán giống như là một trò chơi, tuy nhiên đáng ngạc nhiên là có một số ứng dụng thực tế cho các vấn đề như cách tổ chứclưu trữ bộ nhớ song song, kiểm tra các mạch tích hợp lớn (VLSI - Very Large Scale Integration), kiểm soát tắc ngẽn giao thông, ngăn chặn deadlock. Vấn đề này cũng được áp dụng trong nhiều vấn đề thực tế mà các nghiệm liên quan tới sự hoán vị, trong đó có rất nhiều. Một trong những vấn đề như vậy là bài toán người du lịch (travelling salesperson problem). Bìa toán cũng được coi là một chương trình “hello world” của các bài toán thỏa mãn ràng buộc (Constraint Satisfaction Problem) [Norvig],...

2.Những giải thuật xung quanh bài toán

Điểm hấp dẫn của bài toán N-quân hậu là nó dễ dàng mô tả nhưng lại không dễ đề giải nó một cách hiệu quả. Kích cỡ nghiệm của không gian nghiệm có độ phức tạp hàm mũ N^N. Đây là một sự bùng nổ về tổ hợp, gây khó khăn trong quá trình giải quyết.

Về mặt thuật toán, nếu tách riêng bài toán này, thì nó không thực sự quá quan trọng. Tuy nhiên, bài toán thường được coi như là một phép thử cho các phương pháp tối ưu - có rất nhiều các giải pháp cho vấn đề này trên trang web, nhưng chỉ có số ít là cho lời giải trong thời gian nhanh. Cũng chính vì sự lý thú của bài toán mà trong ngành khoa học máy tính nó được nghiên cứu rất đa dạng với nhiều thuật toán kỹ thuật tìm kiếm được sử dụng để tăng tốc độ cho bài toán: tìm kiếm quay lui (backtracking), nhánh cận (Branch and Bound), tìm kiếm theo chiều sâu với Heuristic [shel], thuật toán tiến hóa (Genetic Programming) [jes] hay dùng mạng nơron [jace]...

Hơn thế nữa, trong khi giải bài toán này, người ta còn gặp một loạt các vấn đề đã được toán học quan tâm từ lâu như hình vuông kỳ ảo (magic squares), hình vuông Latin (Latin squares)...

Có khoảng 320 bài viết về bài toán N-quân hậu, điều này đủ nói lên sự thu hút rất lớn của bài toán tưởng như nhỏ này.

Cũng trong quá trình giải người ta thấy rằng trong tất cả các nghiệm của bài toán có rất nhiều nghiệm “thừa” (có thể suy ra từ các nghiệm khác bằng các phép đối xứng, quay hay kết hợp cả hai), chính vì vậy người ta tìm cách loại bỏ nó để tăng hiệu quả chương trình (chúng tôi sẽ trở về vấn đề này trong một bài khác)

Cũng trong quá trình giải bài toán N-quân hậu, người ta cũng nghĩ ra một vài biến thể của bài toán: (i) tìm số quân hậu tối thiểu mà có thể khống chế tất cả các ô trong bàn cờ; (ii) bài toán 3-D N-quân hậu; (iii) Bài toán 9 quân hậu (được mở rộng thành bài toán N+K queens);(iv) Bài toán m quân hậu, m quân mã trên bàn cờ NxN (nếu có dịp chúng tôi cũng mong mở rộng thêm những vấn đề này).

Số nguyên tố vẫn luôn được coi là một loại số rất kỳ lạ, điều này lại được chứng minh một lần nữa trong bài toán N-quân hậu. Vơi N là số nguyên tố, sẽ có nghiệm với cách giải riêng cho bài toán (chúng tôi sẽ trở về vấn đề này trong một bài khác)

Với mong muốn bổ sung thêm những điều thú vị xung quanh bài toán này, chúng tôi sẽ viết một số bài về chủ đề này. Trong bài đầu tiên này, chúng tôi sẽ có những phần sau: 1. Lịch sử bài toán N-quân hậu

3.Lịch sử [wiki]

Bài toán được đưa ra vào 1848 bởi kỳ thủ Max Bezzel, và sau đó nhiều nhà toán học , trong đó có Gauss và Georg Cantor, có các công trình về bài toán này và tổng quát nó thành bài toán xếp hậu. Các lời giải đầu tiên được đưa ra bởi Franz Nauck năm 1850. Nauck cũng đã tổng quát bài toán thành bài toán n quân hậu. Năm 1874, S. Gunther đưa ra phương pháp tìm lời giải bằng cách sử dụng định thức, và J.W.L. Glaisher hoàn chỉnh phương pháp này.

Edsger Dijkstra đã sử dụng vấn đề này năm 1972 để minh họa sức mạnh của những gì ông gọi là cấu trúc chương trình. Ông cũng mô tả chi tiết về thuật toán quay lui – theo chiều sâu.

Định lý: Với N > 3, có ít nhất một nghiệm cho bài toán N-quân hậu.

Định lý này được chứng minh lần đầu bới Ahrens năm 1910. Sau đó Hoffman, Loessi, và Moorenăm 1969. (Mathematics Magazine, March-April 1969, 66-72.)

I-Cách giải

1. Cách lưu trữ và giải bài toán

* Ta thấy khi đặt 1 quân hậu vào một ô ở hàng i cột j trên bàn cờ, nó sẽ chiếm dụng kiểm soát trên:

- Hàng ngang i.

- Cột dọc j.

- 1 Đường chéo song song với đường chéo chính.

- 1 Đường chéo song song với đường chéo phụ

* Nhận xét:

- Với đường chéo song song với đường chéo chính đi qua ô ở hàng i và cột j luôn có cùng hiệu (i-j).

- Với đường chéo song song với đường chéo phụ đi qua ô ở hàng i và cột j luôn có cùng tổng (i + j)

- Với một bàn cờ cỡ NxN ta có:

§ Chỉ số đường chéo chính chạy từ -(n-1)...(n-1)

§ Chỉ số đường chéo phụ chạy từ 2...2n

* Do vậy khi đặt quân hậu vào một ô ở hàng i và cột j chúng ta có thể dùng các mảng boolean để đánh dấu các hàng, cột mà nó chiếm dụng như:

- h[i] = true;// Hàng i đã bị chiếm.

- c[j] = true;// Cột j đã bị chiếm.

- cc[i-j] = true;// Chéo chính i - j đã bị chiếm

- cp[i+j] = true;// Chéo phụ i + j đã bị chiếm.

* Do vậy để đặt 1 quân hậu vào một ô ở hàng i, cột j bất kỳ chúng ta chỉ cần kiểm tra xem hàng i, cột j và hai đường chéo đã bị chiếm dụng chưa.

* Lần lượt đặt thử con hậu vào các vị trí:

- Đặt con hậu đầu tiên ở vị trí cột 1, hàng 1

- Nếu được đặt con hậu tiếp theo vào các ô ở cột tiếp sao cho không bị ăn cứ như vậy theo cho đến đến khi đủ số con hậu cần.

- Nếu không được quay lại bước trước và dịch chuyển quân hậu trước đó sang ô tiếp theo.

* Ví dụ với với n = 4 cách diễn tả tìm ra một nghiệm có thể diễn tả như sau:

2. Bằng đệ quy thử sai quay lui

Chúng ta xem mã chương trình

Procedure Try (i)

For j=1 to n do

If not h(j) And not c(i) And not cc(i-j) And not cp(i+j) then

{

solution(i)=j;

If i

c(i)=true;

h(j)= true;

cc(i-j)=true;

cp(i+j)=true;

try_col(i+1)

c(i)=false;

h(j)=false;

cc(i-j)=false;

cp(i+j)=false;

ELSE print_solution();

}

Thủ tục tìm tất cả các lời giải của bài toán n hậu chỉ bao gồm một lời gọi Try (1):Call Try_col(1);

3. Chương trình tham khảo (được cài đặt bằng Java)

3.1Giải bằng đệ quy thử sai quay lui:

NQueen.java

import java.util.*;

publicclass NQueen {

staticbooleanc [], h [],cc[], cp[];

staticintn, x[],soCach = 0;

publicstaticvoid Try(int i){

for(int j = 1; j<=n; ++j){

if(!h[j] && !c[i] &&!cc[j-i+n]&&!cp[i+ j]){

x[i] = j;

if(i<n){

h[j] = true;

c[i] = true;

cc[j-i+n] = true;

cp[i + j] = true;

Try(i+1);

h[j] = false;

c[i] = false;

cc[j-i+n] = false;

cp[i + j] = false;

}else{

++soCach;

System.out.print("Cach " + soCach + ": ");

for(int l = 1; l<x.length; ++l)

System.out.print(x[l] + " ");

System.out.println();

}

}

}

}

publicstaticvoid main(String[] args) {

Scanner keyIn = new Scanner(System.in);

System.out.print("Nhap n = ");

n = keyIn.nextInt();

c= newboolean[n+1];

h = newboolean [n+1];

cc = newboolean[2*n + 1];//-n..n; 0 ..2n

cp =newboolean [2*n+1]; //2 .. 2n

x = newint [n+1];

Try(1);

}

}

3.2Giải bằng khử đệ quy:

Ở đây, chương trình dùng một Stack để lưu trữ các quân hậu được lưu lần lượt theo cột.

NQueenKDQ.java

import java.util.Scanner;

import java.util.Stack;

publicclass NQueenKDQ {

staticbooleanh[], cc[], cp[];

staticintn, x[], soCach = 0;

static Stack sta;

staticvoid TimKQ() {

int cot = 1, hang = 1;

boolean boDatDuoc = false;

sta.push(hang);

while (true) {

// Duyet qua cac cot tim dap an

boDatDuoc= false;

if (cot <= n) {

for (int i = hang; i <= n; ++i) {

// Duyet qua cac hang cua tung cot

if (!h[i] && !cc[i - cot + n] && !cp[i + cot]) {

x[cot] = i; //Dat quan hau vao cot, hang thu i

h[i] = true;

boDatDuoc = true;

cc[i - cot + n] = true;

cp[i + cot] = true;

sta.push(i);

hang = 1;

cot += 1; // Chuyen sang cot tiep theo

break;

}

}

} else {

++soCach;

System.out.print("Cach " + soCach + ": ");

for(int l = 1; l<x.length; ++l)

System.out.print(x[l] + " ");

System.out.println();

}

if(!boDatDuoc){

//Quay lui

cot -=1;

hang = sta.pop();

h[hang] = false;

cc[hang - cot + n] = false;

cp[hang + cot] = false;

hang +=1;

}

if(cot ==1 && hang>n){

break;

}

}

}

publicstaticvoid main(String[] args) {

Scanner keyIn = new Scanner(System.in);

System.out.print("Nhap n = ");

n = keyIn.nextInt();

h = newboolean[n + 1];

cc = newboolean[2 * n + 1];// -n..n; 0 ..2n

cp = newboolean[2 * n + 1]; // 2 .. 2n

x = newint[n + 1];

sta = new Stack();

TimKQ();

}

}

II-Kết luận

Chúng tôi mong muốn sẽ trao đổi thêm một số bài báo về bài toán này, trong số báo này, chúng tôi chỉ tập trung vào việc giới thiệu bài toán và giải nó với cách đơn giản nhất: bằng cả Đệ qui và Khử đệ qui.

Ở các bài sau, chúng tôi sẽ nói về: một số kỹ thuật loại bỏ đối xứng nhằm tăng quá trình tìm kiếm nghiệm, bài toán N+K queens, và trong trường hợp N là số nguyên tố.

Chúng tôi mong rằng người đọc sẽ thấy được điều thú vị đối với bài toán này.

Nguyễn Văn Hậu, Lê Công Thành
Khoa CNTT, Trường Đại học Sư Phạm Kỹ thuật Hưng Yên
nvhau66@gmail.com; thanhlct@gmail.com

Tài liệu tham khảo

[jes]“Using Genetic Programming To Solve The n QueensProblem”, Jesper Goos, November 10, 2005.

[jace]“A neural network designed to solve the N-Queens Problem”, Jacek Mandziuk and Bohdan Macukow, http://www.mini.pw.edu.pl/~ mandziuk

[index] http://www.liacs.nl/~kosters/nqueens/index.html

[Norvig] Artificial Intelligence: A Modern Approach, Stuart Russell and Peter Norvig, Prentice Hall, 2nd Edition, 2002.

[shel]“Common Search Strategies and Heuristics With Respect to the N-Queens Problem”, CS504 Term Project, Sheldon Dealy, December 10, 2004

[Fermat]http://vi.wikipedia.org/wiki/B%C3%A0i_to%C3%A1n_Fermat

[wiki]http://vi.wikipedia.org/wiki/B%C3%A0i_to%C3%A1n_t%C3%A1m_qu%C3%A2n_h%E1%BA%ADu

School@net