Гарвардский математик решил шахматную задачу 150-летней давности

Ферзь — самая сильная фигура на шахматной доске. В отличие от всех других фигур, он может перемещаться на любое количество клеток по вертикали, горизонтали или диагонали.

Теперь рассмотрим такую задачу для ферзя: если поместить восемь из них на стандартную доску размером восемь на восемь клеток, сколькими способами их можно будет расположить так, чтобы ни одна из них не могла атаковать другую? Оказывается, таких способов 92.

Но что, если вы разместите еще большее количество ферзей на шахматной доске того же относительного размера, скажем, 1000 ферзей на шахматной доске 1000 на 1000 квадратов или даже миллион ферзей на доске аналогичного размера?

Первоначальная версия математической задачи с n ферзями впервые появилась в немецком шахматном журнале в 1848 году как задача с восемью ферзями, а правильный ответ появился пару лет спустя. Затем, в 1869 году, всплыла более обширная версия задачи, которая оставалась без ответа до конца прошлого года, когда гарвардский математик дал почти окончательный ответ.

Майкл Симкин, научный сотрудник Центра математических наук и приложений, подсчитал, что существует около (0,143n)ⁿ способов размещения ферзей, чтобы ни один из них не атаковал друг друга на гигантских шахматных досках размером n на n.

Окончательное уравнение Симкина не дает точного ответа, а вместо этого просто говорит, что эта цифра настолько близка к фактическому числу, насколько это возможно прямо сейчас. Число 0,143 представляющее средний уровень неопределенности возможного результата переменной, умножается на любое значение n, а затем возводится в степень n, чтобы получить ответ.

Например, на очень большой шахматной доске с миллионом ферзей 0,143 умножается на один миллион, и получается около 143 000. Затем эта цифра будет возведена в миллионную степень, что означает, что она умножается сама на себя столько раз. Окончательный ответ представляет собой цифру из пяти миллионов цифр.

Майкл Симкин смог вывести это уравнение, поняв лежащую в основе закономерность распределения большого количества ферзей на этих огромных шахматных досках — независимо от того, будут ли они сосредоточены в середине или по краям, — а затем применив хорошо известную схему, математические методы и алгоритмы.

«Если бы вы сказали мне, что я хочу, чтобы вы расставили своих ферзей на доске таким-то и таким-то образом, я бы смог проанализировать алгоритм и сказать вам, сколько существует решений, соответствующих этому ограничению», — сказал Майкл Симкин. «Формально это сводит проблему к задаче оптимизации».

Сосредоточив внимание на местах, которые имеют больше шансов быть занятыми, ученый вычислил, сколько ферзей будет в каждой части доски, и вывел формулу для получения допустимого количества конфигураций. Вычисления привели к тому, что известно как нижняя граница — минимальное количество возможных конфигураций.

Получив это число, Симкин применил стратегию, известную как метод энтропии, чтобы найти верхнюю границу, то есть максимальное число возможных конфигураций.

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

Майкл Симкин работал над проблемой n ферзей почти пять лет. Он говорит, что лично он плохой шахматист, но стремится улучшить свою игру.

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

«Я думаю, что лично я могу на некоторое время покончить с проблемой n ферзей не потому, что с ней больше нечего делать, а просто потому, что я ​​готов двигаться дальше в моей жизни», — сказал он.