Bài toán bàn cờ

Một bài toán về bàn cờ
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ô trong 2 cách có thể (chỉ cần tô một ô là xác định được màu của tất cả các ô còn lại, vì mỗi ô chỉ có thể là màu đen hoặc trắng nên cũng chỉ có 2 cách tô màu cho toàn bàn cờ, nói chung bàn cờ được tô thế nào cũng không quá quan trọng do những điều sắp được nói sau đây).


Sau khi đã tô màu cho tất cả các ô trên bàn cờ theo phương pháp trên, ta có thể rút ra một nhận xét: “các con tượng được đặt trên các ô màu đen sẽ không thể khống chế các con tượng nằm trên các ô màu trắng và ngược lại các con tượng được đặt trên các ô màu trắng cũng không thể khống chế các con tượng nằm trên các ô màu đen”. Nhận xét này gợi ý cho chúng ta một phương pháp giải bài toán con tượng. Đó là coi tập các ô trắng và tập các ô đen trên bàn cờ là 2 bàn cờ con độc lập với nhau. Sau đó, ta tính số các thế cờ trên từng bàn cờ con đó rồi tổ hợp các kết quả với nhau thành công thức cuối cùng. Cách tính có thể được trình bày rõ ràng như sau: Gọi DN(i), TN(i) (i=0, …, K) tương ứng là số các thế cờ chỉ bao gồm i con tượng trên bàn cờ các ô đen và bàn cờ các ô trắng của một bàn cờ vuông NxN và thỏa mãn không có hai con tượng nào có thể khống chế nhau. Như vậy, số các thế cờ cần tìm của bài toán 2 là:


Với S là tổng số các thế cờ cần tính trên bàn cờ NxN. Vấn đề còn lại giờ đây là tìm ra công thức tính TN(i) và DN(j). Vẫn là bàn cờ được tô màu ở trên, nhưng chúng ta điền thêm các con số vào