На первый взгляд, шахматы кажутся простой игрой: поле на 64 квадратов, два набора по 8 фигур с каждой стороны и два соперника, стремящихся к смерти чужого короля. Если же копнуть чуть глубже и посмотреть на игру с академической точки зрения, то игра предлагает невероятно сложные возможности, ставя перед шахматными теоретиками и математиками задачи, которые могут оставаться нерешенными десятилетиями или даже столетиями.
В июле 2021 года одна из таких задач была наконец решена — по крайней мере, получен приблизительный ответ. Математик Майкл Симкин из Гарвардского университета в Массачусетсе решил проблему, которая не давала покоя учёным с тех пор, как впервые возникла полтора века назад:
Если бы вы сказали мне, что я хочу, чтобы вы расставили своих ферзей на доске таким-то и таким-то образом, то я смог бы проанализировать алгоритм и сказать, сколько существует решений, соответствующих этому ограничению. В формальных терминах это сводит проблему к проблеме оптимизации, — говорит Симкин.
Задача n-ферзей
Давайте немного углубимся в контекст. Если вы разбираетесь в шахматах, то знаете, что ферзь — самая опасная фигура на доске, способная перемещаться на любое количество клеток в любом направлении. Из этого вытекает задача n-ферзей, которая звучит так: при определенном количестве ферзей (n), сколько существует вариантов расстановки, при которых ферзи находятся достаточно далеко друг от друга, чтобы ни один из них не мог взять другого?
Для восьми ферзей на стандартной доске 8×8 ответ известен — 92, хотя большинство из них — повернутые или отраженные варианты 12 основных решений. Но что будет, если взять тысячу ферзей и поместить их на доску размером 1 000×1 000 квадратов? А если поставить миллион ферзей?
Симкину потребовалось почти пять лет, чтобы вывести своё решение-уравнение. Он перепробовал различные подходы и методы, преодолел кучу препятствий и подробно законспектировал своё решение в 51-страничной статье. В конечном счёте математик смог вычислить нижнюю и верхнюю границы возможных решений и обнаружил, что они почти совпадают.
Приблизительное решение задачи Симкина выглядит так: (0,143n)n
Переводим с математического: чтобы получить искомое число комбинаций, нужно умножить число ферзей на 0,143 и возведести в степень n.
Полученное решение ещё может быть улучшено?
Если вы увлекаетесь математикой и вас заинтересовала задача n-ферзей, то у нас хорошие новости: вполне возможно, что есть более точное решение. Симкин подошел к этому ближе, чем кто-либо до него, но на момент написания статьи он «устал» и рад передать задачу кому-нибудь другому для дальнейшего изучения.
А тут ещё есть, над чем поработать. По мере увеличения размеров доски и количества ферзей исследование показало, что ферзи имеют тенденцию собираться по бокам доски. В центре ферзей меньше, так как там они более подвержены атаке. Знание этой детали позволяет применять более взвешенный подход к задаче и в будущем (возможно, при помощи квантовых компьютеров или нейросетей) получить ещё более точное решение этой проблемы.