Bài toán tám quân hậu

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ.

Bài toán tám quân hậu là bài toán đặt tám quân hậu trê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 đượ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.

Bài toán này cũng được ứng dụng trong trò chơi máy tính The 7th Guest vào những năm 1990.

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,i₁],Q[2,i₂],...,Q[n, i_n],thỏa mãn các điều kiện:

• Các chỉ số cột i₁, i₂,..., i_n đô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+i₁, 2+i₂,..., n+i_n đôi một khác nhau;
• Hiệu chỉ số dòng và cột của các quân hậu 1-i₁, 2-i₂,...,n-i_n đôi một khác nhau.

Chẳng hạn lời giải cho trong hình trên 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.

Bài toán tám quân hậu có 12 lời giải khác nhau. Nếu không phân biệt các lời giải là ảnh của nhau qua phép đối xứng, phép quay bàn cờ thì chúng chỉ có 12 lời giải đơn vị như biểu diễn dưới đây:

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 1	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 2	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 3
a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 4	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 5	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 6
a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 7	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 8	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 9
a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 10	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 11	a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h Lời giải 12

Ta có bảng sau đây cho n quân hậu, cả (dãy số A002562 trong bảng OEIS) và (dãy số A000170 trong bảng OEIS).

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	..	23	24	25	26	27
số lời giải (các lời giải đối xứng chỉ tính 1 lần)	1	0	0	1	2	1	6	12	46	92	341	1.787	9.233	45.752	285.053	..	3.029.242.658.210	28.439.272.956.934	275.986.683.743.434	2.789.712.466.510.289	29.363.791.967.678.199
số lời giải	1	0	0	2	10	4	40	92	352	724	2.680	14.200	73.712	365.596	2.279.184	..	24.233.937.684.440	227.514.171.973.736	2.207.893.435.808.352	22.317.699.616.364.044	234.907.967.154.122.528

Lưu ý rằng bài toán với 6 quân hậu có ít lời giải hơn bài toán với 5 quân hậu. Hiện nay chưa có công thức về số lượng chính xác lời giải.

Trong giải thuật này, mỗi lời giải được ký hiệu bằng một mảng solution[1..n], trong đó solution[i]= j là cột mà quân hậu ở hàng thứ i đứng. Theo tính chất số học của các ô trên bàn cờ n x n, các ô trên các đường chéo cộng chứa ô (i, j) đều có tổng chỉ số hàng với chỉ số cột bằng i+j. Tổng này nhận các giá trị từ 2 đến 2n nên ta đánh số các đường chéo này từ 1 đến 2n-1. Như vậy các ô trên đường chéo cộng thứ nhất có tổng chỉ số dòng và cột là 2, các ô trên đường chéo thứ k có tổng ấy là k+1. Ta dùng một mảng Boolean Ok_plus[1..2n-1] để ký hiệu trạng thái đã có quân hậu nào trên đường chéo cộng thứ k chưa, nghĩa là Ok_plus[k]=True nếu đã có một quân hậu đứng chiếm giữ đường chéo cộng thứ k. Tương tự, các ô trên một đường chéo trừ có hiệu như nhau. Hiệu này nhận giá trị từ 1-n đến n- 1. Đánh số từ 1 đến 2n-1 từ đường chéo có hiệu chỉ số dòng trừ chỉ số cột là 1-n đến đường chéo có hiệu ấy bằng n-1. Khi đó đường chéo trừ thứ k có hiệu chỉ số dòng trừ chỉ số cột là k-n. Ta cũng dùng mảng ok_minus[1..2n-1] để chỉ trạng thái của các đường chéo này.

Giải thuật này cố gắng đặt quân hậu ở dòng thứ i vào cột nào đó, bắt đầu từ dòng thứ nhất (luôn có thể đặt được). Nếu ở dòng thứ i ta đặt quân hậu vào cột thứ j, thì nó khống chế tất cả các ô trong cột thứ j, đường chéo cộng thứ i+j-1, đường chéo trừ thứ i-j+n. Nếu có thể đặt được quân hậu ở dòng i và i = n ta có một lời giải. Nếu đặt được và i < n ta tiếp tục cố gắng đặt quân hậu tiếp theo vào dòng thứ i+1. Nếu không đặt được, ta quay lại nhấc quân hậu ở dòng thứ i-1 và tìm phương án tiếp theo của dòng thứ i-1.

• Nhận xét: trong hai lời giải ở hình bên các vị trí của quân hậu trên bàn cờ đứng theo vị trí nước đi của quân ngựa

procedure Try_row(i)
  for j = 1 to n do
  if not ok_row(i) and not ok_col(j) and not ok_plus(i+j-1) and not ok_minus(i-j+n) then
    solution(i) = j
    ok_col(j) = true
    ok_plus(i + j - 1) = true
    ok_minus(i - j + n) = true
    if i < n then
      try_row(i + 1)
    else print_solution()
  ok_row(i) = false
  ok_col(j) = false
  ok_plus(i + j - 1) = false
  ok_minus(i - j + n) = false

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_row(1):

procedure n_queen(n);
  call Try_row(1);

Ta minh họa quá trình tìm kiếm lời giải cho bài toán n hậu với n = 4 trong hình bên. Ở trạng thái xuất phát, trên dòng 1 có 4 lựa chọn cho quân hậu: quân hậu thứ nhất có thể đứng ở các cột 1, 2, 3, 4. Nếu lựa chọn ô (1, 1), ở dòng thứ hai chỉ còn hai lựa chọn là cột 3 và cột 4. Nếu lựa chọn cột 3, trên dòng thứ 3 sẽ không còn ô nào không bị khống chế (ô (3, 1) và (3, 3) bị khống chế bởi (1, 1), ô (2, 3) và (3, 4) bị khống chế bởi (2, 3). Ta loại bỏ phương án chọn ô (2, 3) này và xét tiếp phương án chọn ô (2, 4). Khi lựa chọn ô (2, 4) ta cũng chỉ đặt thêm được một quân hậu ở dòng thứ ba. Dòng thứ tư lại không thể đặt bất kỳ quân hậu nào. Do đó ta lùi lại dòng thứ nhất, xét khả năng tiếp theo (1, 2), ta lần lượt được dãy các ô (1, 2), (2, 4), (3, 1), (4, 3). Tiếp tục với ô (1, 3), (1, 4). Chỉ có hai đường đi từ gốc tới lá với độ dài 4 nên bài toán 4 hậu chỉ có 2 lời giải thể hiện trên cây bằng các đường đi màu xanh lục.

• Bài toán mã đi tuần

• An Applet simulating the random-greedy solution for the n-queen problem Lưu trữ 2007-10-06 tại Wayback Machine
• MathWorld article
• Solutions to the 8-Queens Problem
• Walter Koster's N-Queens Page Lưu trữ 2006-10-14 tại Wayback Machine
• Durango Bill's N-Queens Page
• On-line Guide to Constraint Programming
• n-Queens in C++; Implementation & analysis of several heuristics to speed up solving the n-queens problem Lưu trữ 2007-09-28 tại Wayback Machine