Đã giải được câu đố hóc búa 150 tuổi trong cờ vua

Câu đố này đã hơn 150 năm tuổi. Nhưng nó chỉ là phiên bản đầu tiên của câu đố n-hậu mà Michael Simkin, nghiên cứu sinh sau tiến sĩ tại Trung tâm Khoa học và Ứng dụng Toán học của Đại học Harvard, vừa tìm ra câu trả lời và công bố trong một bài báo đăng vào tháng Bảy.

Thay vì chỉ tìm ra số cách đặt 8 quân hậu trên một bàn cờ vua tiêu chuẩn 8x8 (sẽ có 92 cách), bài toán n-hậu là: có bao nhiêu cách để xếp n quân hậu trên bàn cờ n x n. Có thể là 23 quân hậu trên bàn cờ 23x23 - hoặc 1.050 quân trên bàn cờ 1.050x1.050, hoặc bất kỳ số quân hậu nào trên bàn cờ có kích thước tương ứng.

Simkin chứng minh rằng, với những bàn cờ khổng lồ có số lượng quân hậu lớn thì có khoảng (0,143n)^n cách sắp xếp. Vì vậy, trên một bàn cờ 1 triệu x 1 triệu, số cách sắp xếp 1 triệu quân hậu không tấn công lẫn nhau là khoảng 1 và năm triệu số 0 đằng sau.

Câu đố ban đầu trên bàn cờ 8x8 lần đầu tiên xuất hiện trên một tạp chí cờ vua của Đức vào năm 1848. Đến năm 1869, câu đố n-hậu xuất hiện. Kể từ đó, các nhà toán học chưa giải được câu đố này một cách có hệ thống. Các nhà nghiên cứu trước đây đã sử dụng mô phỏng máy tính để tìm ra kết quả (kết quả tìm ra tương đương với của Simkin), nhưng Simkin là người đầu tiên chứng minh được một công thức tính. “Về cơ bản, Simkin đã tìm ra đáp án một cách sắc sảo hơn nhiều so với bất kỳ ai trước đây," Sean Eberhard, nghiên cứu sinh sau tiến sĩ tại Đại học Cambridge, cho biết.

Một rào cản để giải quyết câu đố n-hậu là không có cách nào để đơn giản hóa nó. Ngay cả trên một bàn cờ nhỏ, số cách sắp xếp các quân hậu có thể rất lớn. Trên một bảng lớn hơn, số cách trở nên lớn đến kinh ngạc. Trong những tình huống như thế này, các nhà toán học thường cố gắng tìm một mẫu số hoặc cấu trúc cơ bản, cho phép họ chia nhỏ phép tính thành các phần nhỏ dễ xử lý hơn. Nhưng vấn đề n-hậu dường như không có bất kỳ cách đơn giản hóa nào.

Nguyên nhân là không phải tất cả các ô trên bàn cờ đều tạo ra giá trị như nhau, khi đặt một quân hậu vào ô đó.

Hãy tưởng tượng lại câu đố 8x8. Từ ô mà nó đang đứng, quân hậu có thể tấn công bất kỳ ô nào trong hàng ngang, cột dọc hoặc hai đường chéo. Nếu đặt quân hậu đầu tiên vào một ô trung tâm (các ô E4, E5, D4, D5), nó sẽ tấn công tổng cộng 27 ô, và những quân hậu tiếp theo không thể đứng vào 27 ô này. Nhưng nếu đặt quân hậu đầu tiên vào ô rìa bàn cờ, nó chỉ tấn công được tổng cộng 21 ô, vì các đường chéo với ô rìa sẽ ngắn hơn so với đường chéo đi qua các ô trung tâm. Nói cách khác, ô trung tâm và các ô ở rìa là khác nhau - do đó, bàn cờ không có một cấu trúc đối xứng để có thể đơn giản hóa câu đố.

Sự thiếu cấu trúc này là lý do tại sao khi Simkin bắt đầu thử giải câu đố n-hậu, anh đã thử trên một bàn cờ đối xứng. Trong phiên bản sửa đổi này, bàn cờ đượcuốn cong thành hình dạng như một hình xuyến - khối hình học được tạo ra bằng cách quay một đường tròn quanh một trục. Nếu quân cờ đi hết một bên bàn cờ, nó sẽ vòng lên ở bên còn lại. Tất cả các đường chéo trên bàn cờ hình xuyến cùng độ dài và mọi quân hậu dù đứng ở đâu có thể tấn công cùng một số lượng ô: 27.

Trên bàn cờ đối xứng, Simkin sử dụng một kỹ thuật gọi là thuật toán tham lam. Thuật toán bắt đầu đầu bằng việc đặt ngẫu nhiên một quân hậu, sau đó tiếp tục đặt các quân thứ 2, thứ 3 cho đến thứ n vào các ô bất kỳ, chỉ với một điều kiện là ô đó chưa bị tấn công. Nhưng cũng vì có sự đối xứng, mỗi quân hậu trên bàn cờ hình xuyến tấn công được quá nhiều ô, trong khi đó trên bàn cờ tiêu chuẩn, hầu hết các quân hậu tấn công ít hơn 27 ô. Vì thế trên bàn cờ hình xuyến, thuật toán đi vào ngõ cụt khi không thể tìm được chỗ đứng cho các quân hậu cuối cùng để đáp ứng yêu cầu n quân hậu trên bàn cờ n x n.

Khi áp dụng thuật toán này sang bàn cờ tiêu chuẩn, Simkin nhận thấy, nó có thể xếp đến khi đủ yêu cầu n quân hậu, nếu về sau điều chỉnh một số quân đã đặt từ đầu, hoặc nhấc một quân hậu ra để có các ô không bị tấn công và đặt hai quân khác vào. Từ thuật toán này, Simkin đã tìm ra công thức tính số lượng cách sắp xếp tối thiểu cho câu đố n-hậu.

Nhưng thuật toán tham lam ngẫu nhiên chỉ phù hợp nhất cho các bài toán có tính đối xứng, vì nó coi các ô vuông ở giữa hay rìa đều có giá trị như nhau. Trong khi Simkin phát hiện ra rằng các quân hậu trong câu đố n-hậu có nhiều khả năng đứng ở một số ô vuông nhất định so với những ô vuông khác. Bởi vì quân hậu ở giữa bàn cờ tấn công nhiều ô trống nhất, nên hầu hết các cách xếp quân đều có nhiều quân hậu ở phía rìa bàn cờ hơn là ở trung tâm. Khi một bàn cờ lớn hơn 100x100, Simkin nhận thấy, hiệu ứng sắp xếp vị trí này bắt đầu lấn át các cách xếp quân khác. Hầu hết tất cả các cách xếp đều có các quân hậu phân bố theo một cách cụ thể: ít quân hậu hơn ở khu vực giữa bàn cờ và nhiều quân hơn ở rìa. Simkin đã tính ra điểm trọng số để gán cho mỗi ô vuông, và thuật toán sẽ không xếp quân ngẫu nhiên mà ưu tiên lần lượt các ô có điểm từ cao hơn đến thấp hơn.

Từ kết quả sắp xếp này, cùng với điểm trọng số, Simkin tính toán số lượng cách xếp tối đa, dựa trên số lượng ô không bị tấn công sau khi thêm một quân hậu mới. Giá trị tối đa này gần như trùng khớp với giá trị tối thiểu mà Simkin tìm được, cho thấy công thức của anh đã gần như xác định được số cách xếp quân cho câu đố n-hậu.

Các nhà toán học có thể sẽ tiếp tục giải quyết vấn đề này - cố gắng thu nhỏ giới hạn trên và dưới của số cách xếp để tìm ra đáp án chính xác, mặc dù kết quả của Simkin gần như đã giải đáp bí ẩn đằng sau câu đố. Simkin nói: “Điều thú vị là các phương pháp. Chúng tôi không ngừng tìm cách làm cho các công cụ của mình trở nên mạnh mẽ hơn." Ngoài ra, nhiều vấn đề còn bỏ ngỏ khác trong lĩnh vực tổ hợp có thể được hưởng lợi từ các ý tưởng trong các nghiên cứu này.