Max Home IndustryПроблема размещения восьми ферзей на шахматной доске, чтобы ни один ферзь не атаковал другого, является решенной задачей, как и размещение n ферзей на доске размером nxn. Однако, если вы поместите несколько ферзей на доску и попросите завершить, тогда проблема будет NP завершена.
Задача 8 ферзей довольно старая, и я впервые встретил ее не как шахматист, а как часть чтения «Заметок о структурном программировании» Дейкстры. Он использовался в качестве примера того, как рекурсивное отслеживание с возвратом может быть использовано для решения проблемы намного проще, чем любой другой подход. Я не могу сказать, что много думал об этом с тех пор, не считая использования его в качестве продвинутого примера рекурсии.
Если вы никогда не пробовали решать задачу 8 ферзей, попробуйте — используйте шахматную доску и 8 пешек, как если бы они были ферзями. Как вы понимаете, все начинается сложно, а по мере добавления ферзей становится все хуже. Это причина того, что популярна другая версия задачи — головоломка завершения n ферзей, в которую уже были помещены некоторые ферзи.
Симметричное решение
Новая статья Иэна Гента, Питера Найтингейла и Кристофера Джефферсона, всех из Школы компьютерных наук Университета Сент-Эндрюс, является результатом того, что друг попросил профессора Гента решить ее на Facebook. В нем, и это 34 страницы, так что будьте осторожны, доказано, что проблема завершения n ферзей — это NP Complete и #P Complete.
Напомним, NP — это набор проблем, которые трудно решить, но для которых легко проверить предлагаемое решение. Ясно, что завершение n ферзей легко проверить, если я дам вам решение, но опыт подсказывает, что решение найти сложно. Проблема NP Complete — это проблема, в которой, если вы можете найти способ решить ее быстро, то есть за полиномиальное время, вы можете решить все проблемы за полиномиальное время, и вы доказали, что P = NP, что было бы большим делом, потому что большинство наших криптография зависит от P ≠ NP, не говоря уже о премии в один миллион долларов от Института математики Клэя.
Класс сложности #P — это набор проблем, связанных с NP, который просто спрашивает, сколько существует решений. В случае n ферзей вопрос состоит в том, сколько решений существует для любого n, и это явно так же сложно, как и сама проблема NP. Что касается NP Complete, проблема #P Complete — это проблема, если вы можете решить ее за полиномиальное время, то вы можете решить все проблемы в #P за полиномиальное время.
Учитывая размер пространства, которое вам нужно найти, чтобы найти решение, эти результаты могут вас не удивить. Однако количество решений для n ферзей известно только n = 27, а количество решений больше 2.34 * 10 ^ 17. Вопрос в том, насколько сложно их решить на практике. Чтобы ответить на этот вопрос, были реализованы три различных решателя для трех различных вариантов основных задач. Обычно задачи NP Complete показывают «фазовый переход» от решаемого к неразрешимому при увеличении n.
«Мы представили генераторы для жестких случайных примеров задач Blocked n-Queens и Excluded Diagonals, показали, что эта жесткость сохраняется в трех решателях, использующих очень разные технологии, и что жесткость связана с фазовым переходом в разрешимости. Естественная модель для Похоже, что завершение n-Queens не генерирует последовательно трудные экземпляры. Мы также показали, что необходимо проявлять осторожность в методах генерации, чтобы избежать ошибок, которые можно найти в существующих тестах производительности. Наши эксперименты поднимают много интересных вопросов для будущих исследований. К ним относятся асимптотика масштабирование перехода в задачах «Заблокированные n ферзей» и «Исключенные диагонали». Интересная открытая проблема — найти прямой генератор жестких случайных экземпляров для завершения n ферзей, который работает путем случайного размещения ферзей на шахматной доске без использования редукций ».
Если вы никогда не задумывались об этом раньше. Идея о том, что разные генераторы примеров могут создавать простые или сложные примеры, интригует.