• n-Queens Completion Problem — линейный алгоритм решения

      EricGrig


      Предисловие


      Я хотел бы начать предисловие со слов благодарности двум замечательным программистам из Одессы: Андрею Киперу (Lohica) и Тимуру Гиоргадзе (Luxoft), за независимую проверку полученных мною результатов, на начальном этапе исследования.

      1. Статья «Linear algorithm for solution n-Queens Completion Problem» была опубликована в (arXiv.org) в начале первого дня 2020 года. Изначально статья была написана на русском, поэтому здесь представлено базовое изложение, а там — перевод.
      2. Данная задача, и некоторые другие из множества NP-Complete (задача выполнимости булевых формул (3-SAT), задача о поиске максимальной клики, или клики заданного размера …) в разное время, входили в сферу моих интересов. Я искал алгоритмическое решение на основе различных вычислительных экспериментов, но конкретного успеха не было. Это было похоже на то, как человек пытается научиться подтянутся на турнике на одной руке. Результата нет, но каждый раз появляется надежда, что скоро все получится. Последний раз я решил, что следует подольше остановиться на задаче n-Queens Completion (как одной из представителей семейства) и попытаться что-то сделать. Здесь уместно вспомнить замечательный Одесский анекдот: «В переполненном автобусе, который вечером по ухабистой дороге возвращается в пригород, раздается голос женщины – Мужчина, если уж полностью на меня легли, так сделайте хоть что-нибудь».
      3. Исследование длилось достаточно долго – почти полтора года. С одной стороны, это связано с тем, что в процессе исследования, рассматривались и другие задачи, с другой – по ходу решения были сложные вопросы, без ответа на которые не удалось бы идти вперед. Перечислю некоторые из них:

        • В матрице решения n строк, в какой последовательности следует выбирать индекс строки, если число возможностей для такого выбора составляет n!

      Читать дальше →
    • One Billion Queens Problem Solution или, «Исследование закономерностей в списке решений задачи распределения n-Ферзей»

      Резюме


      Приводится описание закономерностей, которые были установлены в последовательном списке всех решений задачи о распределении n-Ферзей. Установлено, что:


      • Доля полных решений в общем списке всех решений уменьшается, с ростом значения n.
      • Полные решения распределены в последовательном списке всех решений таким образом, что с наибольшей вероятностью встречаются полные решения, расположенные в списке близко друг от друга.
      • Существует симметрия в порядке расположения полных решений в общем списке всех решений. Если в i-ой позиции от начала списка решение является полным, то и симметричное решение от конца списка, находящееся в позиции n-i+1 также является полным (правило симметричности решений).
      • Любые пары решений, как коротких так и полных, расположенных симметрично в списке всех решений, являются комплементарными – сумма индексов позиций соответствующих строк является постоянной величиной и равна n+1 (правило комплементарности решений). Это говорит о том, что только первая половина списка всех полных решений является «уникальной», любое полное решение из второй половины списка можно получить на основе правила комплементарности. Следствием этого правила является тот факт, что для любого значения n, количество полных решений, всегда будет четным числом.
      Читать дальше →