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

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

Khoa học, 7/9/17. Trả lời: 166, lượt xem: 57,614.

ndminhduc ndminhduc

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

Thảo luận trong 'Khoa học' bắt đầu bởi ndminhduc, 7/9/17. Trả lời: 166, Xem: 57614.

Chia sẻ

  1. ndminhduc

    ndminhduc FONS VITÆ ERVDITIO POSIDENTIS

    Tham gia:
    24/7/13
    Được thích:
    33,092
    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.

    Đang tải 8_quan_hau_Tinhte.png…
    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. 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
     

    Chia sẻ

    #1 ndminhduc, 7/9/17
    Sửa lần cuối: 7/9/17
    Ngô Đức Lương, nakheel, 74K1-181818 người khác thích nội dung này.
  2. phong_hue

    phong_hue Thành viên

    Tham gia:
    14/1/09
    Được thích:
    294
    Mình nghĩ người giải được chẳng phải là thành viên Tinh Tế đâu vì mấy anh em TT dạo này bận tranh cãi đủ thứ lấy thời gian đâu mà giải toán :D
     
    anhlanguoibanthan, mainasus, gb.vudong32 người khác thích nội dung này.
    1. Ngô Đức Lương

      Tham gia:
      16/10/17
      Được thích:
      1
      Ngô Đức Lương @phong_hue Mình giải được rồi bạn ạ
       
  3. donghungx

    donghungx Thành viên

    Tham gia:
    10/5/08
    Được thích:
    140
    Các nhà khoa học là khoa học nào, ông nào tổ chức nào đứng ra tài trợ với trao thưởng, nhỡ giải xong nó bảo: Tôi nói thế bao giờ, cứ đùa thì sao :D
     
    1. binhminh1977

      binhminh1977 Thành viên

      Tham gia:
      6/6/07
      Được thích:
      520
      binhminh1977 @donghungx Bác cứ suy bụng ta ra bụng người khác không.
       
    2. gamewalker

      gamewalker Thành viên

      Tham gia:
      2/11/09
      Được thích:
      4,086
      gamewalker @donghungx bác mà giải đc cái này bảo đảm bác nói gì cả thế giới toán-tin đều cuối đầu răm rắp nghe theo. PvsNP problem đó bác. Ko phải tầm thường đâu. Đừng nói 1tr$, bác đòi 1 tỷ cũng có vẻ khả thi đó.
       
      1
      aduckuba thích nội dung này.
    3. kaichuan

      kaichuan Thành viên

      Tham gia:
      15/12/11
      Được thích:
      736
    4. Ngô Đức Lương

      Tham gia:
      16/10/17
      Được thích:
      1
      Ngô Đức Lương @anhhoang02 Mình giải được rồi tìm ai để chứng minh à bn
       
  4. louisntt

    louisntt Thành viên

    Tham gia:
    6/1/10
    Được thích:
    122
    Đúng là đọc đoạn đầu 8*8 thì nghĩ nó cũng tương tự như trò Sodoku giải ô số thôi.
    Đọc tiếp e bị chóng mặt, hoa mắt quá! :((
     
    vuphong1001 thích nội dung này.
    1. phamnamha93

      phamnamha93 Thành viên

      Tham gia:
      11/6/12
      Được thích:
      77
      phamnamha93 @louisntt Nếu mình ko sai thì nó cũng gần tương tự như sudoku. Có điều bây giờ tính cả hàng chéo. Nguyên lý là vậy nhưng để tìm ra công thức hay thuật toán giải với điều kiện cho trước là n bất kỳ thì bó tay. Nhưng n kiểu j cũng phải >3 Mới giải đc
       
    2. pink23

      pink23 Thành viên

      Tham gia:
      10/8/13
      Được thích:
      12
      pink23 @phamnamha93 Giải cái này quan trọng là nghĩ ra đc 1 phương trình, hàm số thoả mãn yêu cầu thôi. Có những bài toán trong đa lĩnh vực cả ngàn năm k giải đc cuối cùng cũng xong bởi 1 phương trình của 1 thần đồng nào đó
       
  5. 2Tek.vn

    2Tek.vn Thành viên

    Tham gia:
    14/8/15
    Được thích:
    139
    Vét cạn mà chơi thôi, biết sao giờ :D
     
    1. TqTTpT

      TqTTpT Thành viên

      Tham gia:
      21/2/10
      Được thích:
      299
      TqTTpT @2Tek.vn ông chạy vét cạn mà n to to tí thì ông sống mấy kiếp cũng chưa chạy xong :))
       
    2. mualarung_1982

      mualarung_1982 Thành viên

      Tham gia:
      19/3/09
      Được thích:
      234
      mualarung_1982 @2Tek.vn cho mấy vòng for đơn giản lồng nhau máy nó đã è cổ lên chạy rồi, ở đó mà vét cạn :)
       
    3. hacrot3000

      hacrot3000 Thành viên

      Tham gia:
      15/3/12
      Được thích:
      204
      hacrot3000 @2Tek.vn Mỗi 8 con hậu thôi mà dùng vét cạn đã mệt mỏi rồi, đằng này số lượng trường hợp cần thử nhiều hơn hàng tỷ tỷ tỷ lần thì có mà cạn mấy kiếp người cũng chưa ra :D
       
  6. hongphong141

    hongphong141 Thành viên

    Tham gia:
    24/11/10
    Được thích:
    243
    hahaha, không hi vọng, siêu máy tính còn thua mà
     
    1. mualarung_1982

      mualarung_1982 Thành viên

      Tham gia:
      19/3/09
      Được thích:
      234
      mualarung_1982 @hongphong141 Con người hơn máy tính chổ đó, máy tính nó chạy theo thuật toán được lập trình sẵn, mà con người đưa ra được thuật toán tối ưu hay không là chuyện khác, chứ thời gian vét cạn cả tỉ năm thì máy nào chạy cho nổi. Thời còn đi học, thầy có hỏi cả lớp một câu, tại sao máy tính tính được cả triệu phép tính một giây mà vẫn thua con người, trong khi trong một giây đó con người không thể tính được nhiều nước, đó là do máy tính tính được nhiều nước, nhưng nó không thể biết được nuớc đi nào tối ưu, vậy nên hongphong141 cố gắng lên :)
       
      #17 mualarung_1982, 7/9/17
      Sửa lần cuối: 7/9/17
      6
    2. DuongHoangKhang

      DuongHoangKhang Thành viên

      Tham gia:
      6/5/16
      Được thích:
      64
      DuongHoangKhang @mualarung_1982 Giờ AI nó wính cờ ăn con người rồi bác ạ! nó chính thức hơn rồi đấy
       
      3
      xấu-là-cái-tội, swordman2609mualarung_1982 thích nội dung này.
    3. Ác Ôn Nông Thôn

      Ác Ôn Nông Thôn Thành viên

      Tham gia:
      26/7/17
      Được thích:
      65
      Ác Ôn Nông Thôn @DuongHoangKhang người ta nói rõ như thế mà còn không hiểu, máy móc chỉ là công cụ dĩ nhiên nó phải hiệu quả thì con người mới bỏ công sức tạo ra nó, nó tập hợp tất cả tinh hoa trong đó con người thua là điều tất nhiên, nhưng nó có thể sáng tạo như con người được không.
       
    4. DuongHoangKhang

      DuongHoangKhang Thành viên

      Tham gia:
      6/5/16
      Được thích:
      64
      DuongHoangKhang @Ác Ôn Nông Thôn Cho tui hỏi bác có đọc hết cmt của bác trước chưa? Nếu chưa đọc hết thì đọc dùm nha, còn nếu đọc hết rồi thì lên google search cái thuật toán mà AI đánh cờ nó sử dụng á, bác nghĩ với những cái cơ bản mà nó có thể ăn được kiện tướng cờ số 1 thế giới à...
       
  7. aduckuba

    aduckuba Thành viên

    Tham gia:
    5/2/17
    Được thích:
    298
    K biết bài này ra đời tự bao giờ
    Aduckuba sign
     
    #7 aduckuba, 7/9/17
    Sửa lần cuối: 7/9/17
    1. vicktorbui

      vicktorbui Thành viên

      Tham gia:
      26/10/09
      Được thích:
      781
      vicktorbui @aduckuba Rảnh thì làm việc khác có ý nghĩa đi. Đừng có hạ nhục người khác kiểu thế. Nếu ghét ổng thì tìm lí lẽ thuyết phục mà tranh biện. Toàn làm trò mèo
       
      5
      Không Giới Hạn, lendras, mckplez2 người khác thích nội dung này.
  8. Nokfev

    Nokfev Thành viên

    Tham gia:
    26/11/11
    Được thích:
    13,613
    Tính số TS với PTS của Việt Nam trong vài năm tới có khi còn khó hơn :D
     
  9. authien9x

    authien9x Thành viên

    Tham gia:
    20/8/10
    Được thích:
    136
    AI sẽ trả lời đáp án trên :v
     
    aduckuba thích nội dung này.
    1. anhhoang02

      anhhoang02 Thành viên

      Tham gia:
      3/11/08
      Được thích:
      379
      anhhoang02 @authien9x Em sợ treo máy.
       
      1
      aduckuba thích nội dung này.
  10. Hổ Báo Cáo Chồn

    Hổ Báo Cáo Chồn Thành viên

    Tham gia:
    3/1/15
    Được thích:
    2,223
    Bài nào của ông tướng @ndminhduc này cũng phải có cái gì đó chém gió linh tinh, không có trong bài viết gốc.
    Bàn cờ 8x8 mà ra 4,5 tỷ cách xếp thì tôi cũng đến quỳ lậy tế sống ông
     
    #11 Hổ Báo Cáo Chồn, 7/9/17
    Sửa lần cuối: 7/9/17
    vietdevelop, tuanandy, Google [bot]4 người khác thích nội dung này.
    1. Nguoitreucho

      Nguoitreucho Thành viên

      Tham gia:
      23/6/17
      Được thích:
      384
      Nguoitreucho @casperpas Chia thêm giai thừa 8 nữa thým à, về nhà mà thể hiện
       
    2. casperpas

      casperpas Thành viên

      Tham gia:
      27/2/09
      Được thích:
      54
      casperpas @Nguoitreucho tag bài kia chứ sao tag bài tui hả thím =)))
       
    3. sieu_nhan

      sieu_nhan Thành viên

      Tham gia:
      27/3/11
      Được thích:
      2,681
      sieu_nhan @magicboy_pt123 Ko. Đang tính sắp xếp ngẫu nhiên là. Nhưng mình tính sai. Phải là 64C8 = 4,5 tỷ mới đúng. Mình tính 64P8 là sai
      Và trong 4,5 tỷ cách đó có 92 cách xếp thoả mãn
       
      1
      magicboy_pt123 thích nội dung này.
    4. snowdkny

      snowdkny Thành viên

      Tham gia:
      15/5/12
      Được thích:
      35
      snowdkny @Hổ Báo Cáo Chồn Tội vãi :))
       
  11. daivannguyen

    daivannguyen Thành viên

    Tham gia:
    17/11/13
    Được thích:
    7
    Đang giải nhưng tinh tế viết sai cái j đó nên ko giải tiếp được. Huhu
     
  12. thanhmpys

    thanhmpys Thành viên

    Tham gia:
    24/7/14
    Được thích:
    46
    Thôi giải lao đủ rồi, lam việc tiếp thôi!
     
    Trí Constantineblackeye09 thích nội dung này.
  13. kungfu9999

    kungfu9999 Thành viên

    Tham gia:
    3/5/12
    Được thích:
    1,491
    Đừng ảo tưởng giỏi hơn nhà khoa học;)
     
  14. dinhcongtan

    dinhcongtan Thành viên

    Tham gia:
    14/1/10
    Được thích:
    1
    1 Triệu đô có 22 tỷ hà,mà kêu giải bài toán trên vừa đau đầu nhức óc mà lâu nữa,để mình ra mua tờ vietlott giá trị hôm nay đang gần 40 tỷ xem ra còn dể ăn hơn hiiii
     
    1. hd79

      hd79 Thành viên

      Tham gia:
      6/6/14
      Được thích:
      558
      hd79 @dinhcongtan Ở VN kiếm tầm tiền đấy quá dễ. Làm chổi đót, nuôi lợn, chạy xe ôm ...vừa nhanh, vừa nhàn có ngay số tiền đó
       
      4
      trieuluu, thang_1234, kaichuan1 người khác thích nội dung này.
    2. datmacom

      datmacom Thành viên

      Tham gia:
      13/10/09
      Được thích:
      342
      datmacom @hd79 Sau này có khi còn chạy grap cũng nên :))
       
      2
      traihanammystogann0 thích nội dung này.
  15. casperpas

    casperpas Thành viên

    Tham gia:
    27/2/09
    Được thích:
    54
    hồi đi học thầy giáo dạy tin học có đố mình câu này. 20 năm rồi chưa giải đc =))))
     
    Zoro21, quanghuy0604kixx thích nội dung này.
  16. nhatha

    nhatha Thành viên

    Tham gia:
    9/10/06
    Được thích:
    102
    Cái này thì poa tay rồi
     
  17. phamtrieu.it

    phamtrieu.it Thành viên

    Tham gia:
    13/4/12
    Được thích:
    34
    Dạy thằng alpha go nó học chơi rồi nó giải cho =))
     
    unsigup thích nội dung này.
    1. iamcuong

      iamcuong Thành viên

      Tham gia:
      28/7/09
      Được thích:
      588
      iamcuong @phamtrieu.it Cùng ý kiến :3 Để bọn AI nó học rồi nó giải cho.
       
      1
      aduckuba thích nội dung này.
    2. Juztapose

      Juztapose Thành viên

      Tham gia:
      31/10/10
      Được thích:
      155
      Juztapose @phamtrieu.it alpha go xài monte carlo search tree, nó "có thể" giải 1 trường hợp hiện tại bằng tìm đường đi tốt nhất chứ nó không thể giải được tất cả các trường hợp.
       
      3
      mystogann0, kixxtunglinh10a2 thích nội dung này.
  18. Yugi_pro_IT

    Yugi_pro_IT Thành viên

    Tham gia:
    3/4/11
    Được thích:
    300
    Đã giải xong, 1 triệu đô của t đâu
     
  19. heobanhki

    heobanhki Thành viên

    Tham gia:
    29/1/08
    Được thích:
    4,908
    Hỏi 500 ace Tinhte máy tính casio fx 570 huyền thoại có giải nổi bài toán này không? Nếu không thì mình thua rồi vì nó là cái siêu máy tính mạnh nhất mình từng có :D
    Đang tải fx_570vn_plus_2.u3059.d20170710.t094456.761933.jpg…
     
    trieuluu, Capetown, Anh Dung Do1 người khác thích nội dung này.
  20. casperpas

    casperpas Thành viên

    Tham gia:
    27/2/09
    Được thích:
    54
    có 64C8 cách xếp quân hậu lên bàn cờ, nhưng chỉ có 92 cách để k có con nào ăn đc nhau.
     
    ndminhduc thích nội dung này.

Chia sẻ

Đang tải...