Хто хоче заробити 1$млн своїм розумом? - налітай! :)

[jack74]

Вчені дають $1 млн за вирішення старовинної шахової задачі

Цитувати

Вчені з британського Сент-Ендрюського університету запропонували $1 млн за розв'язання старовинної шахової задачі під назвою "Завдання про вісім ферзів"

Про це повідомляється на сайті університету.

Задачу сформулювали в середині дев'ятнадцятого сторіччя.

Її суть у тому, що необхідно розставити вісім ферзів таким чином, щоб жоден з них не потрапляв під удар іншого.

Складність полягає у тому, що ця фігура б'є всі клітини, розташовані по вертикалях, горизонталях і обох діагоналях.

Наразі відомо 12 унікальних рішень.

Її вирішення на стандартній дошці в 64 клітини знайшли у 1850 році. Однак задача ускладнюється із збільшенням розмірів поля і кількості фігур.

При збільшенні розміру дошки до 1000 на 1000 клітин комп'ютерні програми, які намагаються вирішити завдання, припиняють працювати.

На думку професора Яна Гента, автор алгоритму швидкого рішення цієї задачі зможе адаптувати свою програму для інших задач, зокрема і для дешифрування кодів в інтернеті.

 

Оригінал з сайту університету:

Спойлер

“Simple” chess puzzle holds key to $1m prize

Thursday 31 August 2017

There has been some confusion about the $1m prize offered by the Clay Mathematics Institute in America. Professor Ian Gent has written some comments about this point which were quoted by the Clay Maths Institute in a news item about this work, which might clarify matters: http://claymath.org/events/news/8-queens-puzzle.

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.

In a paper published in the Journal of Artificial Intelligence Research today, the team conclude the rewards to be reaped by such a program would be immense, not least in financial terms with firms rushing to use it to offer technological solutions, and also a $1m prize offered by the Clay Mathematics Institute in America.

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.

Professor Gent and his colleagues, Senior Research Fellow Dr Peter Nightingale and Reader Dr Christopher Jefferson, all of the School of Computer Science at the University, first became intrigued by the puzzle after a friend challenged Professor Gent to solve it on Facebook. 

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.

Professsor Gent said: “If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily. 

“This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other, or very important ones like cracking the codes that keep all our online transactions safe.”

The reason these problems are so difficult for computer programs, is that there are so many options to consider that it can take many years.  This is due to a process of “backtracking” – an algorithm used in programming where every possible option is considered and then “backed away” from until the correct solution is found.

Dr Nightingale said: “However, this is all theoretical. In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that – for all practical purposes – it can’t be done.”

Dr Jefferson added: “There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly so the rewards are high.” 

Chess has long provided the source for puzzles such as the traditional fable of the servant who, when asked to choose a reward by his king, asked for one grain of rice to be placed on the first square of a standard 8x8 chessboard, doubled in the next and so on until it was found there was not enough rice in the entire world.

The fable indicates the huge numbers involved when using just a standard sized chess board. When the board size increases the numbers become vast.

The paper (Complexity of n-Queens Completion) by (Ian P. Gent, Christopher Jefferson and Peter Nightingale) is published in the (31 August 2017) issue of (Journal of Artificial Intelligence Research), available via http://jair.org/papers/paper5512.html. DOI: doi:10.1613/jair.5512

Image caption: Professor Ian Gent, and Dr Peter Nightingale attempt the puzzle with the giant chess set at Falkland Palace.

 

Наскільки я зрозумів суть, то 1млн призу надається за написання програми чи алгоритму для вирішення цієї головоломки при будь-якій кількості клітинок дошки

Так що вперед!

[AnimaNoir]

Чоловік просто забув пароль від архіву:)

[Serpent]

І в продовження теми, як швидко заробити $1,000,000. У США Фонд Джеймса Ренді пропонує вищезазначену суму тому, хто зможе підтвердити експериментально і довести існування паранормальних явищ, різноманітних надзвичайних здібностей (напр. лозоходство, спілкування з померлими, телекінез, ітд), ну і інших приколів в такому роді. На даний момент премію ще ніхто не отримав, хоча бажаючі були. Я знаю на борді багато "віруючих" у такі речі, так що вперед за мільйоном. Хтозна, можливо будете першими. )))