Математики определили сложность задачи о ферзях

Математики из Школы Компьютерных Наук Сент-Эндрюсского университета доказали, что известная проблема дополнения позиции до n ферзей при заданных положениях m ферзей (m < n) одновременно является NP-полной и #P-полной. Также ученые провели эмпирический анализ проблемы и предложили новый критерий для оценки работы искусственного интеллекта. Статья опубликована в Journal of Artificial Intelligence Research.

Задача о n ферзях — широко известная задача о расстановке n шахматных ферзей на доске n × n так, чтобы ни в одной колонке, ряду или диагонали не стояло двух фигур. Задача была сформулирована в 1848 году шахматным композитором Максом Беззелем для n = 8, и уже два года спустя Франц Наук (Franz Nauck) опубликовал первое решение. Он же в дальнейшем расширил ее на случай произвольных n. Задача привлекала интерес многих известных математиков, включая Гаусса (который, кстати, по словам авторов статьи, допустил ошибку в ее анализе). На этой задаче в 1958 году впервые был реализован поиск с возвратом, и с тех пор она используется как пример или бенчмарк (критерий качества) во многих работах по искусственному интеллекту. Однако надежность этого бенчмарка часто критикуется, и ученые ищут более обоснованные критерии для оценки работы ИИ.

Существуют различные вариации задачи о ферзях. Например, «заблокированные» ферзи (Blocked n-Queens), когда запрещается ставить фигуры на некоторые клетки доски. Или задача с исключенными диагоналями, в которой допускается, чтобы два ферзя стояли на одной диагонали. Известна также задача на завершение позиции, когда требуется дополнить заданную неатакующую комбинацию из m ферзей (m < n). Как показали математики в своей статье, все эти задачи являются #P- и NP-полными. Тем не менее, вопрос о NP-полноте оригинальной проблемы n ферзей остается открытым. Пока что было доказано, что эта задача лежит вне класса #P.

В теории алгоритмов класс NP — класс задач, для которых можно достаточно быстро (за полиномиальное время от входных данных) проверить предполагаемое решение на верность на машине Тьюринга. Класс #P — множество проблем, решением которых является количество успешных способов вычислений для некоторой недетерминированной машины Тьюринга, также работающей за полиномиальное время. Например, задача нахождения числа путей между двумя заданными вершинами в графе принадлежит #P. Проблема называется NP-полной (#P-полной), если к ней можно свести любую другую задачу из класса NP (#P) за полиномиальное время. Известной #P-полной задачей является вычисление перманента матрицы.

Доказательство того, что задача о завершении позиции является #P-полной и NP-полной, математики выполнили следующим образом. Сначала они определили последовательность из пяти задач, первой из которых являлась проблема дополнения неатакующего набора m ферзей до n, а последней — вариант задачи выполнимости булевых формул (Boolean Satisfiability, SAT), с задачей с исключенными диагоналями в качестве промежуточного шага. Затем математики доказали, что последняя проблема является #P- и NP-полной, и выполнили последовательность полиномиальных сведений от последней задачи к первой. Кроме того, эти сведе́ния были «экономными» (parsimonious), то есть количество решений сведенной проблемы равнялось количеству решений сводимой, что одновременно доказывает NP- и #P-полноту задачи о ферзях. Ученые отмечают, что доказать NP-полноту саму по себе практически так же сложно.

Также математики задались вопросом, насколько сложны для решения на практике задачи о завершении позиции, «заблокированных» ферзях и исключенных диагоналях, коль скоро они являются NP-сложными. Для этого они сконструировали три решающих устройства, работающих по разным технологиям: решатель со специальной целью, решатель SAT и решатель с ограничениями. Генерируя различные конфигурации, математики искали фазовые переходы между разрешимыми и неразрешимыми задачами для разных классов проблем и разных решающих устройств. Оказалось, что для задачи с заблокированными клетками и задачи на завершение позиции, как и для многих NP-полных проблем, существуют фазовые переходы, связанные со сложными для решения случаями. В то же время естественный генератор для проблемы n ферзей не создавал последовательно сложные примеры.

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

Задача n ферзей активно исследуется математиками. Только за последние полвека было опубликовано несколько десятков работ, посвященных этой теме, причем как минимум шесть из них имеют более четырехсот цитирований на Google Scholar. Последовательность чисел различных возможных расстановок ферзей на доске n × n имеет номер A000170 в онлайн-энциклопедии целочисленных последовательностей. На данный момент рассчитаны значения вплоть до n = 27.

Недавно мы писали, как французский математик решил другую известную задачу — задачу о замощении плоскости выпуклыми многоугольниками.

Дмитрий Трунин