Гарвардський математик здебільшого розв’язав епічну шахову задачу 150-річної давності

Гарвардський математик здебільшого розв'язав епічну шахову задачу 150-річної давності

На перший погляд, шахи здаються простою грою: 64 окремі чорні або білі квадрати, по 16 фігур на кожній стороні, і два суперники, які прагнуть перемоги.

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

У липні 2021 року одну з таких задач було нарешті розв’язано — принаймні до певного моменту. Математик Майкл Сімкін з Гарвардського університету в Массачусетсі задумався над проблемою n ферзів, яка спантеличувала експертів з того часу, як її вперше вигадали в 1840-х роках.

Якщо ви розумієтеся на шахах, то знаєте, що ферзь – найсильніша фігура на дошці, здатна ходити на будь-яку кількість клітин у будь-якому напрямку. Проблема n ферзів ставить таке запитання: при певній кількості ферзів (n) скільки можливо розстановок, в яких ферзі знаходяться досить далеко один від одного, щоб жоден з них не міг взяти іншого?

Для восьми ферзів на стандартній дошці 8 x 8 відповідь дорівнює 92, хоча більшість є оберненими або відображеними варіантами всього 12 фундаментальних рішень.

Але як щодо 1000 ферзів на дошці розміром 1000 х 1000 клітин? Як щодо мільйона королев? Приблизне рішення Сімкіна проблеми: (0,143n)n – кількість ферзів, помножена на 0,143, зведена у ступінь n.

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

Сімкіну знадобилося майже п’ять років, щоб прийти до рівняння, використовуючи різні підходи та методи, а також кілька перешкод на шляху до вирішення. Зрештою математик зміг обчислити нижні та верхні межі можливих рішень, використовуючи різні методи, і виявив, що вони майже збігаються.

«Якби ви сказали мені, що я хочу, щоб ви розставили своїх ферзів на дошці таким-то і таким-то чином, я зміг би проаналізувати алгоритм і сказати вам, скільки існує рішень, що відповідають цьому обмеженню», — каже Сімкін. “Формально це зводить проблему до завдання оптимізації”.

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

Теоретично має бути можлива більш точна відповідь на загадку з n ферзями, але Сімкін підійшов тут ближче, ніж будь-коли раніше, і він щасливий передати завдання комусь іншому для подальшого вивчення.

Стаття Сімкіна про рішення задачі доступна на сервері препринтів arXiv.

Прокоментуйте: