Британські дослідники запропонували мільйон доларів за рішення задачі про вісім ферзів»

0
119
Британські дослідники запропонували мільйон доларів за рішення задачі про вісім ферзів»

У світі шахів «завдання про вісім ферзів» відома з 1850 року. Умова її полягає в наступному: необхідно розставити 8 ферзів таким чином, щоб вони не мали можливості «напасти» один на одного в один хід. На думку фахівців, дана задача має багато спільного з програмуванням.

Дослідники з британського Університету Сент-Ендрюс під керівництвом професора Яна Гента запропонували програмістам знайти просте рішення цієї старовинної шахової головоломки. Завдання — написати програму, яка зможе вирішувати «Завдання про ферзів» для великих дощок з достатньою швидкістю. Переможця чекає солідний приз розміром 1 млн. доларів.

Причина такої високої нагороди проста — за розрахунками математиків, це завдання нездійсненне. Підраховано, що на 64-клітинній (8 х 8) дошці кількість можливих розташувань вісім ферзів дорівнює 4 426 165 368, а кількість «правильних» розташувань у відповідності з умовами завдання – всього 92. Однак, якщо дошка буде мати конфігурацію 1000 х 1000 клітин, комп’ютерні програми просто зависнуть, не осиливши гігантська кількість варіантів.

На думку професора Гента, якщо буде написана комп’ютерна програма, яка зможе вирішувати цю надзавдання з достатньою швидкістю, її можна буде адаптувати для вирішення багатьох важливих проблем — зокрема, для дешифрування найскладніших криптографічних алгоритмів.

Оцініть статтю

НАПИСАТИ ВІДПОВІДЬ

Please enter your comment!
Please enter your name here