TRONG MỘT CHUYÊN MỤC KỲ TRƯỚC, CHÚNG TA ĐÃ ĐƯỢC TÌM HIỂU VỀ BÀI TOÁN “QUÂN MÃ ĐI TUẦN”, KHÁM PHÁ NHỮNG CÔNG THỨC TOÁN HỌC VÀ LẬP TRÌNH TRÊN BÀN CỜ VUA. HÔM NAY, CHÚNG TA SẼ TIẾP TỤC TÌM HIỂU MỘT CÂU ĐỐ KHÁC, CŨNG NẰM TRÊN BÀN CỜ QUỐC TẾ, NHƯNG LÀ VỚI QUÂN CỜ QUYỀN LỰC NHẤT: QUÂN HẬU.

I – Bài toán

Trên một bàn cờ vua 8\times 8, đặt tám quân hậu (không phân biệt màu sắc) sao cho không có quân hậu nào có thể “ăn” được quân hậu khác, hay nói cách khác, không có một cặp hai quân hậu nào cùng nằm trên một hàng, một cột hoặc một đường chéo. Bài toán có thể được tổng quát hóa thành n con hậu trên bàn cờ vuông n\times n với n=1 hoặc n\geq 4.

Bài toán được đưa ra lần đầu tiên bởi kỳ thủ Max Bezzel (1848). Sau đó 2 năm, Franz Nauck đã đưa ra lời giải đầu tiên, cùng với đó tổng quát bài toán lên n quân hậu. Nhiều nhà toán học tên tuổi, như Carl Gauss và Georg Cantor đã nghiên cứu và khám phá sâu hơn về vấn đề này. Bài toán cũng đã được nhà khoa học Edgar Djikstra sử dụng để minh họa cho phương pháp lập trình cấu trúc trên máy tính.

Bạn đọc có thể thử giải quyết bài toán trên trang web http://eightqueen.becher-sundstroem.de/

II – Giải quyết bài toán

Về cơ bản, bài toán tám quân hậu trong một chương trình máy tính có thể phải xử lý với một lượng rất lớn thông tin (có tất cả C_{64}^8 cách đặt 8 quân hậu lên bàn cờ). Tuy vậy, ta có thể đưa ra điều kiện 8 quân hậu phải nằm trên 8 hàng hoặc 8 cột khác nhau trên bàn cờ, ta có thể giảm được số khả năng về 8! (tương ứng 40.320 khả năng), sau đó kiểm tra các nước đi chéo.

Chúng ta có thể tương đối dễ dàng tự thiết kế ra một cách sắp xếp 8 quân hậu trên bàn cờ để thỏa yêu cầu bài toán. Sau đây là một cách giải tiêu biểu, cũng là cách giải duy nhất mang tính đối xứng qua trục ngang và trục dọc:

Người ta đã tìm ra tất cả là 92 cách giải quyết bài toán này trên bàn cờ 8\times 8. Tuy nhiên, nếu chỉ xét các trường hợp tổng quát (hay, nói cách khác, xem 2 trường hợp có thể cùng nhận được bằng cách xoay bàn cờ hoặc dùng phép đối xứng là như nhau), thì trên bàn cờ có tất cả là 12 cách giải. Trong đó, chỉ có cách giải đối xứng đã biểu diễn ở trên là có 3 cách giải tương tự, các trường hợp tổng quát khác đều có thể tạo ra thêm 7 cách giải tương đương, vì vậy tổng số cách sắp xếp là 11 \times 8 + 1 \times 4 = 92.

Bảng sau đây biểu diễn số cách giải có thể cũng như số trường hợp tổng quát cho một số trường hợp của n. Một điều đặc biệt ở đây là, trường hợp n=5 có số cách giải nhiều hơn so với n=6.

III – Một phương pháp xây dựng lời giải

Thực tế, các thuật toán sử dụng để tìm ra lời giải cho bài toán quân hậu với nlà bé, với n lớn hơn như n=20, số lượng trường hợp sẽ khiến việc tìm kiếm lời giải vô cùng rắc rối (20! = 2,433x{10^{18}}). Vì vậy, ta có thể xây dựng một phương pháp tường minh xác định lời giải bằng công thức như sau:

  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, \cdots.
  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ụ:

  • 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.

IV – Các bài toán liên quan

  • Năm 2004, trên tạp chí cờ vua Chessvariants đã có một cuộc thi nhỏ để kỷ niệm 9 năm ra đời, đó là bài toán với 9 quân hậu trên bàn cờ 8\times 8. Ta dễ dàng nhận thấy việc đặt 9 quân hậu lên để thỏa yêu cầu là không thể, vì vậy người ta cho sử dụng thêm một số lượng quân tốt nhất định, đặt trên bàn cờ, sao cho 9 quân hậu không thể ăn lẫn nhau. Câu hỏi là cần ít nhất bao nhiêu quân tốt, và chúng ta có thể sắp xếp nó trên bàn cờ như thế nào? Bài toán sau đó đã được trả lời, và chỉ cần sử dụng đúng một quân tốt để sắp xếp lời giải hợp lý (như hình dưới).

  • Thay quân hậu bằng các quân cờ khác, trên một bàn cờ 8\times 8, ta có thể đặt tối đa 32 quân mã / 14 quân tượng / 16 quân vua / 8 quân xe sao cho không có quân nào có thể ăn lẫn nhau. Chúng ta cũng có thể tìm ra lời giải cho các trường hợp này tương đối dễ dàng, ví dụ như: đặt 32 quân mã vào 32 ô cùng màu (đen hoặc trắng) trên bàn cờ, khi đó vì quân mã di chuyển từ màu này đến màu khác nên không quân nào có thể ăn lẫn nhau.
  • Một bài toán khác là tìm số quân hậu ít nhất đặt lên bàn cờ để chúng có thể “đe dọa” toàn bộ bàn cờ. Với bàn cờ 8\times 8, chứng minh được ta cần ít nhất 5 quân hậu để đạt được điều kiện trên. Dưới đây là một ví dụ.

TÀI LIỆU THAM KHẢO