Завдання про вісім ферзів: напиши комп’ютерну програму і отримай мільйон. Доларів.

Видео Новости Общество Технологии

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

  «Це королева, вона ходить як завгодно», — кинув репліку кардинал Рішельє під час гри в шахи з д’Артаньяном. І хоча цитата прозвучала двоїсто, втім, дійсно — ферзь ходить на будь-яке поле по вертикалі, горизонталі та діагоналі, на будь-які відстані.

Задача, яку у 1848 році придумав шахіст Макс Беццель, звучить так:

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

Франц Наук першим знайшов рішення задачі у 1850 році, граючи на стандартній дошці
в 64 клітини. Німецький математик, механік і фізик Карл Гаусс знайшов 72 варіанти можливої ​​розстановки фігур: різні комбінації 8 ферзів досягалися за допомогою цікавого прийому — повороту дошки на 90, 180 і 270 градусів відповідно. Однак, із збільшенням розмірів поля і кількості фігур задача ускладнюється.  При збільшенні розміру дошки до 1000 на 1000 клітин комп’ютерні програми, які намагаються вирішити завдання, припиняють працювати.

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

На думку професора Яна Гента, автор алгоритму швидкого рішення цієї задачі зможе адаптувати свою програму для інших задач, зокрема і для дешифрування кодів в інтернеті. Коштувати така програма буде чимало (чому б і не 1 мільйон доларів?),  і покупці на неї завжди знайдуться.  Загальна кількість можливих  варіантів — 92. Оригінальних рішень 12. Універсальних — жодного.

І наостанок: головоломка з ферзями являє собою форму математичної проблеми з області комп’ютерної науки і описана як «NP-complete». Це цікава тема, оскільки, якщо знайти одне ефективне рішення для однієї NP-повної задачі, це може бути використано для вирішення всіх NP-повних задач.

 

 

  •  
  •  
  •