Một bài toán về bàn cờ
Đặng Chiến Công
Bài toán 1: Trên bàn cờ Quốc tế 8x8, cho 8 con hậu. Mỗi con hậu có thể khống chế (ăn)
được tất cả các con hậu khác nằm trên cùng hàng, cùng cột, hoặc trên hai đường chéo đi
qua vị trí của nó. Viết chương trình tính số các thế cờ chỉ gồm 8 con hậu trên bàn cờ sao
cho không có hai con hậu nào có thể khống chế (ăn) được nhau.
Bài toán trên chính là bài toán con hậu nổi tiếng. Đây là một bài toán kinh điển và lời giải
kinh điển của nó là thuật toán duyệt bằng phương pháp quay lui. Vì vậy nếu theo phương
pháp này, bài toán con hậu khó có thể giải được với những dữ liệu lớn (bàn cờ kích thước
lớn hơn, số con hậu nhiều hơn) vì độ phức tạp tính toán của thuật giải là một hàm số mũ.
Tuy nhiên, bài báo này không có ý định tìm ra lời giải ưu việt cho bài toán con hậu (đây là
bài toán khó khăn thực sự) mà thay vào đó, chúng ta sẽ nghiên cứu một bài toán tương tự,
đơn giản hơn nhưng cũng không kém phần thú vị, đó là bài toán:
Bài toán 2: Trên bàn cờ vua, con tượng chỉ có thể di chuyển theo đường chéo và hai con
tượng có thể khống chế (ăn) nhau nếu chúng nằm trên đường di chuyển của nhau. Trong
hình sau, hình vuông tô đậm thể hiện các vị trí mà con tượng B1. Quân B1 và B2 khống
chế (ăn) nhau, quân B1 và B3 không khống chế (ăn) nhau. Cho một bàn cờ kích thước
NxN. Hãy tính số các thế cờ chỉ bao gồm K con tượng mà không có con tượng nào có thể
khống chế nhau. (N, K là các số tự nhiên cho trước).
Bài toán 1 gọi là bài toán con hậu, bài toán 2 tạm gọi là bài toán con tượng. Dễ thấy con
tượng có vùng “phủ sóng” hạn chế hơn con hậu. Con tượng chỉ có khả năng khống chế các
quân cờ khác nằm trên cùng đường chéo với nó trong khi con hậu còn khống chế được cả
thêm các quân nằm trên cùng hàng, cùng cột. Do đó, một cách hiển nhiên thì bài toán con
tượng cũng có thể giải tương tự như bài toán con hậu bằng thuật toán quay lui. Tuy nhiên,
ở đây chúng ta sẽ nghiên cứu một phương pháp khác để tính số thế cờ mà đề bài yêu cầu.
Chúng ta sẽ cố gắng xây dựng một công thức tính số thế cờ đó.
I. Xây dựng công thức tính số cách sắp đặt các con tượng.
Giả sử chúng ta đang phải làm việc với một bàn cờ vuông kích thước NxN. Một bàn cờ
vuông bình thường thì bao giờ mỗi ô trên đó cũng được tô bằng 2 màu: đen hoặc trắng
(hoặc bằng cặp màu nào đó). Phương pháp tô theo cách sau: nếu một ô màu đen/trắng thì
các các ô kề cạnh với nó sẽ có màu trắng/đen. Thí dụ theo hình vẽ dưới là một cách tô

dụ ta có đường chéo số 0, số 1, -1,...
Gọi F[m, k] (m, k ≥ 0) là số các thế cờ chỉ gồm k con tượng (hay số cách sắp đặt k con
tượng) trên các ô thuộc các đường chéo số
của bàn cờ vuông NxN, sao cho không có hai con tượng nào có thể khống chế nhau (hay
trên mỗi đường chéo, kể cả xuôi và ngược, chỉ có tối đa một con tượng).
Ví dụ, với bàn cờ 8x8 như hình vẽ trên, F[2, 4] là số cách sắp đặt 4 con tượng trên các ô
thuộc các đường chéo -6, -4, -2, 2, 4, 6 sao cho không có hai con tượng nào có thể khống
chế nhau.
Theo công thức trên, ta cũng thấy nếu đường chéo 0 được tô màu đen thì T
N
(i) = F[0,i] và
D
N
(i) = F[1, i], thay vào biểu thức (1) ta có:
Nếu ta tô màu ngược lại thì S vẫn có dạng như trên vì (hiển nhiên) S không phụ thuộc vào
cách ta tô màu. Công thức trên đã gợi ý cho chúng ta đường lối rõ ràng hơn trong việc tìm
S. Công việc duy nhất còn lại là tính các F[0, i] và F[1, j] hay nói một cách tổng quát hơn
là ta phải đi tính F[m, k] với các số m và k cho trước.
Khi đối mặt với các công thức kiểu dạng F[m, k], phương án đầu tiên mà những người làm
toán tin kinh nghiệm sẽ thường nghĩ đến là phương pháp tính truy hồi. Và quả như vậy,
chúng ta sẽ tính công thức này theo công thức tính truy hồi.
Phương pháp tính truy hồi, xét về một khía cạnh nào đó thì cũng rất giống phương pháp
chứng minh quy nạp toán học. Do đó, bước đầu tiên, ta sẽ giả sử chúng ta đã tính được tất
cả các F[i, j] với i = m+1, m+2,..., N-1 và j =0, 1,..., k. Và ta sẽ phải tính F[m, k] từ những
công công thức đã đã tính được trước đó. Thực sự thì để tính F[m, k], điều giả sử của ta ở
trên là hơi thừa. Thực tế, giả thiết chỉ cần đã tính được F[m+2, k], F[m+2, k-1] và F[m+2,
k-2] là đủ.
Như đã nói ở trên, F[m, k] là số cách sắp đặt các con tượng hay là số các thế cờ (thỏa mãn
các điều kiện của ta). Do đó, đối tượng mà ta quan tâm ở công thức F[m, k] là số các thế
cờ, hay cụ thể là số các thế cờ gồm k quân tượng được sắt đặt trên các đường chéo ±m, ±

Cụ thể với m = 0 thì TH3 và TH4 không tính vì ta chỉ có một hàng 0 nên chỉ đặt được 1
con tượng. Trường hợp đặc biệt thứ 2 là k = 1, khi đó ta chỉ có thể đặt tối đa 1 con tượng
lên hai đường chéo m và –m, nên TH4 sẽ không được tính. Nhóm các trường hợp đặc biệt
còn lại là các trường hợp rất đơn giản mà ta có thể đưa ngay ra giá trị F[m, k] mà không
cần tính toán nhiều. Tóm lại ta sẽ có các công thức tính F[m, k] cho từng trường hợp sau:
Nếu k = 0: F[m,0] = 1 với m >=0
Nếu m = N-1: F[N-1,1] =2; F[N-1,k] = 0 với k > 1
Nếu m = N-2: F[N-2,1] = 4, F[N-2,2] = 2, F[N-2, k] = 0 với k>2
Nếu m = 0: F[m,k] = F[m+2,k] + (N – m – k+1)*F[m+2,k-1]
Nếu k = 1: F[m,k] = F[m+2,k] + (N – m – k+1)*2*F[m+2,k-1]
Còn lại ta tính F[m, k] theo công thức (3).
II. Thuật toán – chương trình.
Về thuật toán có lẽ chúng ta không cần phải nói nhiều nữa. Ở đây tôi xin đưa ra một
chương trình viết bằng C++ để minh họa. Chương trình này có thể chạy với các bộ dữ liệu
n và k ở trong khoảng xung quanh 12, một tính với các bộ số lớn hơn ta phải thêm phần
tính toán với số lớn.
III. Kết luận
Như vậy chúng ta đã giải quyết xong bài toán con tượng. Có thể nói bài toán con tượng này
đã được giải quyết khá trọn vẹn. Nhờ có công thức tính mà bài toán con tượng đã trở nên
“khả thi” hơn rất nhiều so với bài toán con hậu. Theo những ý tưởng từ bài toán con tượng
trên, tôi cũng đã thử cải tiến phương pháp quay lui cho bài toán con hậu nhưng cho đến
nay vẫn chưa thu được thành tựu nào đáng kể. Thực sự bài toán con hậu là một bài toán rất
khó, nhưng rất mong có bạn nào đó sau khi đọc xong lời giải bài toán con tượng này có thể
nghĩ ra được phương pháp có tính đột phá chẳng hạn? Chúc các bạn thành công.