Phần thưởng 1 triệu USD cho ai giải được bài toán khiến máy tính cũng phải “bó tay” này

Bất kỳ ai giải được bài toán, tìm cách xếp n quân hậu trên bàn cờ n x n ô sẽ được trao giải thưởng 1 triệu USD. Đây là một bài toán vô cùng phức tạp, để tìm ra lời giải có thể mất tới hàng ngàn năm.

• Đáp án câu đố đơn giản nhưng gây nhiều tranh cãi nhất!
• Những bài toán gây tranh cãi "đố bạn giải được"
• Cùng nhau thử sức với bài toán 33x33 bằng bao nhiêu?

Năm 1848, câu đố “hoàn thiện n quân hậu” được đưa ra và chỉ đơn giản là tìm cách xếp 8 quân hậu nằm trên bàn cờ 8 x 8 sao cho các quân hậu không thể ăn lẫn nhau, có nghĩa là không có quân hậu nào có thể di chuyển theo quy tắc cờ vua. Đây là một điều vô cùng khó khăn và phức tạp bởi trong môn cờ vua, quân hậu có thể di chuyển 8 hướng với bất kỳ khoảng cách nào.

Với bài toán ở trên bàn cờ 8 x 8, chắc chắn nhiều bạn sẽ có thể tìm ra một vài cách giải thỏa mãn điều kiện trên. Thực tế, bài toán này có tất cả 92 cách giải được đưa ra từ 4.426.165.368 cách đặt quân hậu khác nhau.

Một trong các cách sắp xếp đối với bài toán 8 quân hậu trên bàn cờ 8 x 8​.

Nếu số quân hậu và số ô trên bàn cờ tăng lên bài toán sẽ càng phức tạp hơn. Ví dụ với 27 quân hậu trên bàn cờ 27 x 27 ô, thì tổng số giải pháp khả thi sẽ là 2.34*10^17 – con số lên tới triệu tỉ.

Bây giờ ta có bài toán tìm cách xếp n quân hậu trên bàn cờ nxn ô, n càng lớn càng khó tìm ra cách giải.

Cụ thể với n = 1000 và trên bàn cờ 1000 x 1000 ô thì theo các nhà nhà nghiên cứu tại Đại học St Andrews bài toán này cực kỳ khó để tìm ra lời giải ngay cả với các siêu máy tính cực mạnh. Còn nếu bài toán có thêm một yêu cầu: một số con hậu được đặt cố định sẵn trên bàn cờ, không thể di chuyển thì không biết đến bao giờ bài toán mới có lời giải. Và đây mới chính là bài toán mà nhà khoa học máy tính Ian Gent và các nhà nghiên cứu tại Đại học St Andrews, Anh Quốc đã treo giải thưởng 1 triệu USD cho bất kỳ ai tìm được một chương trình máy tính có thể giải được.

Theo Gent, nếu một chương trình máy tính có thể giải được bài toán n quân hậu một cách nhanh chóng và chính xác thì nó cũng có thể giải bất cứ bài toán có các biến tương tự mà hiện các siêu máy tính vẫn đang loay hoay tìm lời giải.

Nghiên cứu mới được công bố trên Tạp chí Nghiên cứu Trí tuệ Nhân tạo cho biết, nếu như bài toán này có n = 1.000 quân hậu, thì AI sẽ “bó tay” hoàn toàn trước số lượng phép thử vô tận.