Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Saturday September 02 2017, @09:04AM   Printer-friendly
from the simple!=easy dept.

Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers to find a solution to a "simple" chess puzzle which could, in fact, take thousands of years to solve and net a $1M prize. Computer Scientist Professor Ian Gent and his colleagues, at the University of St Andrews, believe any program capable of solving the famous "Queens Puzzle" efficiently, would be so powerful, it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet.

Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard chessboard so that no two queens could attack each other. This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal. Although the problem has been solved by human beings, once the chess board increases to a large size no computer program can solve it.

The team found that once the chess board reached 1000 squares by 1000, computer progams could no longer cope with the vast number of options and sunk into a potentially eternal struggle akin to the fictional "super computer" Deep Thought in Douglas Adams' Hitchhiker's Guide to the Galaxy, which took seven and a half million years to provide an answer to the meaning of everything.

https://phys.org/news/2017-09-simple-chess-puzzle-key-1m.html

[Abstract]: "Complexity of n-Queens Completion"

[Source]: https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php

Any takers for this challenge?


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by JoeMerchant on Saturday September 02 2017, @01:03PM (3 children)

    by JoeMerchant (3937) on Saturday September 02 2017, @01:03PM (#562911)

    Potentially of interest: How the Scotsmen framed the discussion:

    http://www.jair.org/media/5512/live-5512-10126-jair.pdf [jair.org]

    --
    🌻🌻 [google.com]
    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2  
  • (Score: 1, Funny) by Anonymous Coward on Saturday September 02 2017, @02:47PM (2 children)

    by Anonymous Coward on Saturday September 02 2017, @02:47PM (#562928)

    Potentially of interest: How the Scotsmen framed the discussion:

    Cute, you think that as they're from St. Andrews they're Scottish.

    It was one of those places (back in the 80's at least) where, if you heard a student with a Scottish accent you got 100 points, or 1000 points if it wasn't a Morningside or Kelvinside (both real or 'derivative') or (shudders at the memory) some unholy bastard child of both of these.

    It used to packed with the English and USians, current 'diversity' figures only indicate that something like 56% of the student population are 'UK' with no further breakdown than that (so I suspect nothing has changed much), next biggest group Usians approaching 15%.

    Further up the coast, Dundee Uni was worse, 'twas the place that anyone from south of the border who couldn't get into any of the English Unis ended up...(bottom of the old UCCA clearing list allegedly)

    Still, I, for one, can't complain about this, as it led to many boozy hours experimenting with the various industrial strength scrumpies and obscure English bitters imported nort of the border especially to cater for said Sassenachs. (Word of advice: never never go out boozing with medical students, I thought I was a serious piss-artist (Scottish, so goes with the territory for a large percentage of the populace) until I was drunk under the table several nights by an English lass who has now been a GP for over 30 years, hollow legs the capacity of Loch Ness that one...).

    Shit, have come over all nostalgic, must dig out some of the old photos and slides...(remembers the content of some of them)...well, maybe not..

       

    • (Score: 2) by JoeMerchant on Saturday September 02 2017, @10:06PM

      by JoeMerchant (3937) on Saturday September 02 2017, @10:06PM (#563033)

      Yeah, O.K. - the conquered territory and all... I'm one to talk - we've got the "batwing eyebrows" and a fair amount of red hair in the family, but our ancestors left Scotland to Tennessee in the 1800s as a method to pay off some intractable debt.... Makes some sad sense that the Uni would be overrun with outlanders.

      --
      🌻🌻 [google.com]
    • (Score: 2) by turgid on Sunday September 03 2017, @11:12AM

      by turgid (4318) Subscriber Badge on Sunday September 03 2017, @11:12AM (#563116) Journal

      Cute, you think that as they're from St. Andrews they're Scottish.

      I know what you mean. Fife really is the pits.