Bài toán bàn cờ trong Pascal

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ờ đó.