Giải được bài toán n quân hậu trên bàn cờ, trúng 1 triệu đô la tiền thưởng

Bạn nào muốn trở thành triệu phú đô la, hãy nhanh tay giải câu đố Queen's Puzzle - tìm cách xếp n quân hậu trên bàn cờ n x n ô bởi các nhà khoa học đã treo giải thưởng lên tới 1 triệu đô la cho ai giải được nó.
Giải được bài toán n quân hậu trên bàn cờ, trúng 1 triệu đô la tiền thưởng

Các nhà khoa học khẳng định ngay cả khi không cần hiều nhiều về luật chơi cờ cũng có thể tham gia, qua đó có thể hiểu được nó phức tạp tới mức độ nào. Trên thực tế, đây là một vấn đề toán học vô cùng phức tạp mà theo các nhà khoa học, việc tìm ra lời giải có thể mất tới hàng ngàn năm.

Chi tiết hơn xíu về thế cờ Queen's Puzzle. Nó được đưa ra hồi năm 1848 và câu đố 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 những quân hậu không thể ăn lẫn nhau, nói cách khác là tìm cách xếp sao cho không có quân hậu nào có thể di chuyển theo quy tắc cờ vua. Nếu bạn biết cờ vua thì không cần phải nói, quân hậu là quân cực kỳ mạnh với khả năng di chuyển 8 hướng với bất kỳ khoảng cách nào. Và chính sự tự do di chuyển của những quân hậu này đã khiến cho Queen's Puzzle trở nên cực kỳ phức tạp đối với các kỳ thủ lẫn nhà toán học.

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ói tới đây thì chắc chắn sẽ có bạn nhanh chóng tìm được một vài cách xếp những quân hậu để thỏa điều kiện bài toán. Không dễ ăn đâu, đọc tiếp nào.

Trên thực tế, có 92 cách để giải câu đố này, tạo thành nên 4,5 tỷ cách xếp 8 quân hậu trên bàn cờ. Đó mới chính là lý do tại sao các nhà toán học xưa giờ vẫn luôn đau đầu với bài toán hấp dẫn này. Và bài toán sẽ phức tạp hơn nữa nếu bạn mở rộng số ô trên bàn cờ và số quân hậu thay vì chỉ là 8 quân hậu trên bàn cờ 8 x 8 = 64 ô. Khi đó, bạn sẽ có những bài toán đặt 20 quân hậu trên bàn cờ 20 x 20 hoặc đặt 100 quân hậu trên bàn cờ 100 x 100 ô.

Khái quát hơn, Queen's Puzzle có thể mở rộng ra thành tìm cách xếp n quân hậu trên bàn cờ n x n ô. Với bài toán này thì theo các nhà nghiên cứu, n càng lớn (thí dụ như n = 1000) thì sẽ cực kỳ khó để tính toán ra các cách sắp xếp, ngay cả đối với các siêu máy tính cực mạnh. Chưa hết, bài toán sẽ càng khốc liệt hơn nữa nếu có thêm 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.

Nhà khoa học máy tính Ian Gent tại Đại học St Andrews, Anh Quốc cho biết: “Các nghiên cứu mới quan tâm tới bài toán n quân hậu và không chỉ về độ lớn của bàn cờ mà còn tính tới việc một số quân hậu đã được đặt sẵn. Và một khi có một số quân hậu được đặt sẵn trên bàn cờ n x n, liệu bạn sẽ tìm được lời giải mà vẫn không di chuyển bất kỳ quân hậu nào đặt sẵn?” Tóm lại chút xíu, đây mới chính là bài toán mà nếu giải được (tìm được lời giải cho bất cứ n nào) thì mới nhận được 1 triệu đô la.

Bởi thế, Gent và các nhà nghiên cứu khác khẳng định rằng chỉ cần tìm được một chương trình máy tính có thể giải được bài toán phức tạp nói trên một cách nhanh chóng thì phần mềm đó cũng sẽ đủ mạnh để giải bất cứ bài toán nào khác cũng có các biến tương tự mà hiện tại các máy tính ngày nay vẫn đang phải vật lộn tìm lời giải.

Gent khẳng định: “Nếu bạn có thể viết một chương trình máy tính có thể giỉa được bài toán n quân hậu một cách nhanh chóng, bạn sẽ có thể giải quyết được nhiều bài toán khác quan trọng hơn trong cuộc sống hàng ngày của chúng ta. Đó có thể đơn giản là cách xử lý một lượng lớn các nhóm bạn bè trên Facebook không biết nhau hoặc vấn đề lớn lao hơn như mã hóa những giao dịch trực tuyến.”

Đó cũng chính là lý do vì sao các nhà khoa học đã treo giải thưởng lên tới 1 triệu đô la cho ai viết được chương trình giải được bài toán n quân hậu nói trên. Gent giải thích thêm rằng người thắng giải chỉ cần hoặc chứng minh được rằng không có thuật toán nào giải được bài toán trong một thời gian hợp lý, hoặc phát triển được thuật toán có thể giải bài toán một cách nhanh chóng, nói theo ngôn ngữ toán học là thời gian đa thức.

Và gợi ý cho bạn nào muốn dấn thân kiếm 1 triệu đô la, Gent cho biết sơ rằng người nào giải được bài toán này phải là cực kỳ thông minh, rất rất may mắn và có lẽ phải có thạc sĩ khoa học máy tính mới có cơ hội giải. Tuy nhiên anh em cũng đừng quá nhụt chí bởi biết đâu, một cách tình cờ sẽ có thành viên Tinh tế giải được thì sao?

Tham khảo DT

TIN LIÊN QUAN

Một công ty bảo mật tuyên bố có thể hack mọi iPhone, lấy dữ liệu với tỷ lệ thành công 100%

DriveSavers, một công ty không mấy nổi tiếng trong lĩnh vực bảo mật, vừa tuyên bố đã nắm trong tay kỹ thuật bẻ khóa iPhone với tỷ lệ thành công 100%.

Một công ty bảo mật tuyên bố có thể bẻ khóa và lấy dữ liệu trên iPhone với tỉ lệ thành công 100%

Gạt ngoài tai những nỗ lực bảo mật iPhone đến từ Apple, các công ty bảo mật vẫn cố gắng thi nhau tìm cách truy cập dữ liệu trên những thiết bị iOS bị khóa mật khẩu. Gần đây nhất, một công ty bảo mật là DriveSavers đã tuyên bố có thể bẻ khóa và lấy

iPhone khóa mạng chao đảo vì sự cố SIM ghép

Việc các loại SIM ghép 4G không thể kích hoạt lên sóng iPhone khóa mạng khiến các mẫu iPhone này giảm giá cả triệu đồng.

"Phải xuất bản được những cuốn sách xứng tầm trở thành nhận thức chung của cả xã hội"

Trong thời gian tới, Bộ TTTT tiếp tục đẩy mạnh phát triển văn hóa đọc trong cộng đồng hướng tới xây dựng một xã hội học tập, một nét đẹp trong đời sống xã hội.

'Thuốc độc', 'thuốc giải' cho tài khoản Facebook giá 2-3 triệu tại VN

Mất từ 2-3 triệu đồng, người ta đã có thể khiến một tài khoản Facebook biến mất. Thủ đoạn này thường được dùng để 'thanh trừng' đối thủ trong kinh doanh hoặc trả thù cá nhân.

Google thêm tiền thưởng cho thử thách Lunar Xprize

Google vừa chính thức điều chỉnh cơ cấu cho giải thưởng Lunar Xprize, giúp tăng thêm động lực cho năm đội tham gia chế tạo tàu vũ trụ lên mặt trăng.

Bộ TT&TT tặng bằng khen cho lực lượng công an phá vụ án 3,5 triệu cuốn sách giáo khoa giả ở Hà Nội

Chiều 16/9/2021, Cục Xuất bản, In và Phát hành Bộ TTTT tổ chức buổi lễ trang trọng trao tặng bằng khen của Bộ trưởng Bộ Thông tin và Truyền thông TTTT cho các tập thể, cá nhân thuộc Cục Cảnh sát điều tra tội phạm về tham nhũng, kinh tế, buôn lậu

Australia tài trợ 4 dự án chuyển đổi số ở Việt Nam

Chính phủ Australia mới đây đã công bố khoản tài trợ gần 1,4 triệu Australia cho 4 dự án ứng dụng công nghệ cao trong lĩnh vực chuyển đổi số CĐS, với kỳ vọng sẽ tạo nên những tác động tích cực tại Việt Nam.

THỦ THUẬT HAY

Cách quấn dây chuột máy tính đẹp, gọn gàng

Cũng giống như các thiết bị khác nếu bạn không sắp xếp gọn gàng rất dễ dẫn đến tình trạng dây chuột bị rối, bị đứt và còn tệ hơn nó làm ảnh hưởng đến tuổi thọ con chuột đang sử dụng. hướng dẫn sau đây sẽ hướng dẫn bạn

3 cách chặn hình ảnh từ các trang web trên Google Chrome

Nếu Chrome chạy chậm vì mất quá nhiều thời gian để tải hình ảnh thì đây là cách để chặn hình ảnh trên trang web trong trình duyệt.

Cách tải video trên điện thoại lên Youtube

Youtube là một dịch vụ cho phép tải video cá nhân của bạn lên mạng Internet để chia sẻ với mọi người xung quanh. Bài viết này sẽ hướng dẫn các bạn cách tải video từ điện thoại của mình lên dịch vụ Youtube nhé.

Cách chặn những trang không mong muốn từ bộ định tuyến của bạn

Nếu muốn website nào đó đừng xuất hiện, kích thích trí tò mò của bản thân, bạn không cần chi tiền mua phần mềm quản lý mạng mà có thể sử dụng thiết lập của bộ định tuyến để chặn những website chưa được mã hóa. Trong

Hướng dẫn cách khắc phục lỗi 1132 trên Zoom

Zoom là một trong những phần mềm được sử dụng nhiều nhất hiện nay để học tập và làm việc online. Tuy nhiên, phần mềm này vẫn tồn tại một số lỗi nhỏ và nếu biết cách khắc phục sẽ giúp quá trình học tập và làm việc mượt

ĐÁNH GIÁ NHANH

Vsmart Active 1+ đối đầu Realme 2 Pro: Cùng mức giá, cùng cấu hình đâu là lựa chọn tốt hơn

Vsmart Active 1+ và Realme 2 là hai sản phẩm đáng quan tâm trong tầm giá 6,3 triệu đồng với cấu hình nổi bật và nhiều yếu tố hấp dẫn.

Đánh giá Lenovo Yoga 920: Sở hữu hàng loạt nâng cấp mới

Thừa hưởng từ Yoga 910, Lenovo Yoga 920 tiếp tục sở hữu thiết kế 2 trong 1 với phần bản lề dạng dây đồng hồ rất đẹp mắt. Sản phẩm được hoàn thiện từ khung nhôm chắc chắn, viền màn hình được làm rất mỏng nhưng cụm

Đánh giá Honda Winner: Mạnh mẽ hơn vẻ ngoài

Thiết kế phổ dụng, động cơ vận hành lý thú, cảm giác lái linh hoạt và nhiều đặc tính hướng tới người chơi chính là những ưu điểm của Honda Winner.