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ó.
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 từ 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.
Ứng dụng miễn phí
Linkitty Nối hình Onet cổ điển
Nối hai hình giống nhau với tối đa hai lần rẽ, đua với đồng hồ. Màn chơi vô tận, thử thách mỗi ngày và gần 100 món đồ cho mèo con, thỏ con.
Ứng dụng miễn phí
Trikitty Ghép 3 hình dễ thương
Chạm ô trên bàn xếp nhiều lớp, đưa xuống khay 7 ô và xếp 3 hình giống nhau liền nhau để ăn. Màn nào cũng có lời giải.
Ứng dụng miễn phí
Lịch Vạn Niên Lịch âm dương Việt Nam
Xem ngày Dương lịch và Âm lịch cùng lúc, kèm can chi của năm, tháng, ngày. Đổi ngày Âm – Dương trong vài giây.
Bộ lạc bụng càng to càng quyến rũ ở Ethiopia
Sở hữu vòng hai khổng lồ luôn là niềm mơ ước của mỗi đứa trẻ ở bộ tộc Bodi và người sở hữu chiếc bụng to nhất sẽ được dân làng trọng vọng suốt phần đời còn lại.
Lý giải hiện tượng Mặt Trăng to hơn ở sát đường chân trời
Ảo ảnh quang học khiến Mặt Trăng trở nên khổng lồ khi ở sát đường chân trời là ảo giác nổi tiếng nhất thế giới mà chưa chuyên gia nào có thể đưa ra giải đáp chính xác.
Bí ẩn bức họa "Bữa tiệc cuối cùng"
Chuyên gia tin học chỉ ra rằng đằng sau bức "Bữa tiệc cuối cùng" còn có hai hình ảnh khác: Hình ảnh Chúa đang chúc phúc lành và hình ảnh một đứa trẻ nhờ hình phản chiếu của bức tranh trong
Xoáy nước là gì? Xoáy nước xuất hiện như thế nào?
Nước sông đang chảy xiết, khi tới trụ cầu thì bị cản, nên phải lùi lại sau. Nhưng phía sau lại là dòng nước đang cuồn cuộn chảy tới, kéo nó chảy theo.
Vì sao 5/5 Âm lịch được chọn là Tết Đoan Ngọ?
Tết Đoan Ngọ được xem là ngày Tết lớn thứ 2 trong năm chỉ sau Tết Nguyên Đán. Vậy tại sao, Tết Đoan Ngọ lại được tổ chức vào ngày 5/5 Âm lịch?
Quá trình "tịnh thân" thảm khốc của nữ thái giám - nhân vật bí ẩn trong lịch sử Trung Quốc
Với một quốc gia ngay từ thời cổ đại đã luôn có tư tưởng trọng nam khinh nữ, việc đưa những người phụ nữ vào cung để "tịnh thân" làm quan có lẽ là một điều ngoại lệ và khó hiểu.
